算法時(shí)間復(fù)雜度可以認(rèn)為就是代碼需要循環(huán)的次數(shù)O(n)

例題
1.下面算法的時(shí)間復(fù)雜度是多少

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

我們可以從循環(huán)結(jié)束的條件開始入手
很明顯是當(dāng)i=n(或者i>n)時(shí)，這時(shí)候我們假設(shè)x次循環(huán)后達(dá)到條件，即,
轉(zhuǎn)換一下：,
由于i的初始值是1，所以這里只要算出中的表達(dá)式就是算法的時(shí)間復(fù)雜度，那就是
。

2.下面算法的時(shí)間復(fù)雜度是多少

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

Math.pow(int x ,int y);//輸出x的y次冪也就是
這里循環(huán)的終止條件就是,所以，代碼循環(huán)次數(shù)就是,即算法的時(shí)間復(fù)雜度為O()

3.下面算法的時(shí)間復(fù)雜度是多少

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

factorial(n)返回n的階乘，所以終止條件就是i=,算法復(fù)雜度為O()

4.遞歸算法時(shí)間復(fù)雜度
斐波那契數(shù)列1，1，2，3，5，8，13，21...
函數(shù)：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);
}

暴力假設(shè)，第一次計(jì)算2次，第二次執(zhí)行4次，第三次執(zhí)行8次...第n次執(zhí)行次，所以總的計(jì)算次數(shù)是等比數(shù)列的前n項(xiàng)和的次數(shù)，數(shù)據(jù)公式，q為公比。所以，取最高次該歸算法時(shí)間復(fù)雜度為,這里q為2.即算法復(fù)雜度O()。
P·S:當(dāng)高階與低階混合的時(shí)候，只取高階的復(fù)雜度

常見類型算法時(shí)間復(fù)雜度：

image.png

證明過程相當(dāng)復(fù)雜，我也不清楚,有興趣的同學(xué)可以去研究一下，我們應(yīng)付面試只知道結(jié)果就好了
1.二叉樹查找O(log n)
2.二叉遍歷O(n)
3.排序的查找或者二維矩陣的查找O(n)
4.快排，歸并排等O(n·log n)