常見時(shí)間復(fù)雜度

O(1) ----常數(shù)階

用常數(shù)1來取代運(yùn)行時(shí)間中所有加法常數(shù)

temp=a;
a=b;
b=temp;

單條操作頻度是1，即使又成千上萬條操作，也是一個(gè)較大常數(shù)，這一類時(shí)間復(fù)雜度是O(1)

O(N) 線性階

sum=0;
for(int i=0;i<n;i++){
    sum++;
}

第一行頻度是1，第二行頻度是n，第三行平度是n，所以f(n0=n+n=1=2n+1;
根據(jù)守則，只要高階項(xiàng)，不要低接項(xiàng)，常數(shù)項(xiàng)是1，去除高階項(xiàng)的系數(shù)。
所以時(shí)間復(fù)雜度O(n)。

O（log2N) --對數(shù)階

首先什么是對數(shù)：

image

image

當(dāng)a=10時(shí)稱作常用對數(shù)，當(dāng)a=e時(shí)稱作自然對數(shù)

void (){
   int number=1;
   int n=100;
   while(number <n){
        number =number*2;
        printf("number is %d",number);
   }
}
假設(shè)n為100，number =1，小于100則退出循環(huán)
第一次循環(huán)，number=2,2^1
第二次循環(huán)，number=4,2^2
第三次循環(huán)，number =8,2^3
第次循環(huán)， number =2^x

2^x=n，則 x=log?n,因此它的時(shí)間復(fù)雜度是O(logn)

O(nlongn)-線性對數(shù)階

logN(logN沒寫底數(shù)默認(rèn)是log2N)

O(n^2) 平方階

void  square(){
    for(int i=0;i<n;i++){ //執(zhí)行了N次
         for (int j=0;j<n;j++){  //執(zhí)行了N次
                printf("squre");
         }
    }
}

時(shí)間復(fù)雜度：n*n = n^2 = O(n^2)

算法比較
O(1)<O(logn)<O(n)<O(nlogn)<O(n2)<O(n3)<O(2n)//2的n方<O(n!)<O(nn)//n的n方

image.png

常見函數(shù)增長曲線，對數(shù)階是比較好的算法，隨著x增長，曲線緩慢增長