算法时间复杂度

算法时间复杂度可以认为就是代码需要循环的次数O(n)

例题
1.下面算法的时间复杂度是多少

for(int i=1;i<n;i=i*2){
  System.out.print(""+i);
}

我们可以从循环结束的条件开始入手
很明显是当i=n(或者i>n)时，这时候我们假设x次循环后达到条件，即 $i*2^x=n$ ,
转换一下： $2^x=n/i$ ,
由于i的初始值是1，所以这里只要算出 $2^x=n$ 中的表达式就是算法的时间复杂度，那就是
$x=log(n)$ 。

2.下面算法的时间复杂度是多少

for(int i=1;i<Math.pow(2,n);i++){
  System.out.print(""+i);
}

Math.pow(int x ,int y);//输出x的y次幂也就是 $x^y$
这里循环的终止条件就是 $i=2^n$ ,所以，代码循环次数就是 $2^n$ ,即算法的时间复杂度为O( $2^n$ )

3.下面算法的时间复杂度是多少

for(int i=1;i<factorial(n);i++){
  System.out.print(""+i);
}

factorial(n)返回n的阶乘，所以终止条件就是i= $n!$ ,算法复杂度为O( $n!$ )

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次执行 $2^n$ 次，所以总的计算次数是等比数列的前n项和的次数，数据公式 $Sn=(1-q^n)/(1-q)$ ，q为公比。所以，取最高次该归算法时间复杂度为 $O(q^n)$ ,这里q为2.即算法复杂度O( $2^n$ )。
P·S:当高阶与低阶混合的时候，只取高阶的复杂度