算法时间复杂度

算法时间复杂度可以认为就是代码需要循环的次数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

证明过程相当复杂，我也不清楚,有兴趣的同学可以去研究一下，我们应付面试只知道结果就好了
1.二叉树查找O(log n)
2.二叉遍历O(n)
3.排序的查找或者二维矩阵的查找O(n)
4.快排，归并排等O(n·log n)