算法时间复杂度可以认为就是代码需要循环的次数O(n)
例题
1.下面算法的时间复杂度是多少
for(int i=1;i<n;i=i*2){
System.out.print(""+i);
}
我们可以从循环结束的条件开始入手
很明显是当i=n(或者i>n)时，这时候我们假设x次循环后达到条件，即,
转换一下：,
由于i的初始值是1，所以这里只要算出中的表达式就是算法的时间复杂度，那就是
。
2.下面算法的时间复杂度是多少
for(int i=1;i<Math.pow(2,n);i++){
System.out.print(""+i);
}
Math.pow(int x ,int y);//输出x的y次幂也就是
这里循环的终止条件就是,所以，代码循环次数就是
,即算法的时间复杂度为O(
)
3.下面算法的时间复杂度是多少
for(int i=1;i<factorial(n);i++){
System.out.print(""+i);
}
factorial(n)返回n的阶乘，所以终止条件就是i=,算法复杂度为O(
)
4.递归算法时间复杂度
斐波那契数列1，1，2，3，5，8，13，21...
函数：f(n)=f(n-1)+f(n-2);
代码:
public int fun(int n){
if(n==0||n==1){
return n;
}
return fun(n-1)+fun(n-2);
}
暴力假设，第一次计算2次，第二次执行4次，第三次执行8次...第n次执行次，所以总的计算次数是等比数列的前n项和的次数，数据公式
，q为公比。所以，取最高次该归算法时间复杂度为
,这里q为2.即算法复杂度O(
)。
P·S:当高阶与低阶混合的时候，只取高阶的复杂度
常见类型算法时间复杂度：
![]()
image.png
image.png
证明过程相当复杂，我也不清楚,有兴趣的同学可以去研究一下，我们应付面试只知道结果就好了
1.二叉树查找O(log n)
2.二叉遍历O(n)
3.排序的查找或者二维矩阵的查找O(n)
4.快排，归并排等O(n·log n)
