算法—算法的时间空间复杂度
文章图片
1. 事后分析法
缺点：不同的数据规模，不同的机器下算法运行的时间不同，无法做到计算运行时间
2. 事前分析法
2.1 大O时间复杂度
渐进时间复杂度 随着n的增长，程序运行时间跟随n变化的趋势
2.1.1 几个原则
去掉常数项
2(n^2) =n^2
一段代码取时间复杂度最高的
test(n) {
//时间复杂度n^3
for(int i = 0;
i < n ;
i++){
for(int i = 0;
i < n ;
i++){
for(int i = 0;
i < n ;
i++){
print(n);
}
}
}
//时间复杂度n^2
for(int i = 0;
i < n ;
i++){
for(int i = 0;
i < n ;
i++){
print(n);
}
}
//时间复杂度n
for(int i = 0;
i < n ;
i++){
print(n);
}
}这段代码的时间复杂度为n^3+n^2+n
当n足够大时，n^2和n与n^3相比太小，可以忽略不计
2.1.2 常见复杂度
o(1)
i = i + 1;
o(n)
test(n){
for(int i = 0 ;
i < n;
i++){
print(i);
}
}o(n^2)
test(n){
for(int i = 0 ;
i < n;
i++){
print(i);
for(int j = 0 ;
j < n;
j++){
print(i);
}
}
}o(log2n)
PS:如果ax =N（a>0，且a≠1），那么数x叫做以a为底N的对数，记作x=logaN，读作以a为底N的，其中a叫做对数的底数，N叫做真数。
test(n) {
int i = 1;
while (i <= n) {
i = 2 * i;
}
}随着循环次数的增加，i的值变化如下
文章图片
根据对数函数的公式 2的i次方等于n,i等于log2n
【算法—算法的时间空间复杂度】
文章图片
2.2 最好情况时间复杂度 数据比较有序的情况的时间复杂度
2.3 最坏情况时间复杂度 数据完全无序
3. 空间复杂度 与n无关的代码空间复杂度可以忽略
空间复杂度O(n)
test(n) {
//在内存中开辟了一个长度为n的数组
List array=List(n);
print(array.length);
}
文章图片
文章图片
推荐阅读
- 热闹中的孤独
- JAVA（抽象类与接口的区别&重载与重写&内存泄漏）
- 放屁有这三个特征的，请注意啦！这说明你的身体毒素太多
- 一个人的旅行，三亚
- 急于表达——往往欲速则不达
- 布丽吉特，人生绝对的赢家
- 慢慢的美丽
- 尽力
- 一个小故事，我的思考。
- 家乡的那条小河