--------------------------------

Author ： ShawnDong

updateDate ：2019.5.31

Blog ： ShawnDong98.github.io

--------------------------------

緒論

程序 = 數(shù)據(jù)結(jié)構(gòu) + 算法

物理結(jié)構(gòu)：順序存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)

邏輯結(jié)構(gòu)：線性結(jié)構(gòu)(順序表、鏈表)和非線性結(jié)構(gòu)(樹、圖)

算法的特性： 輸入、輸出、有窮性、確定性、可行性
算法設(shè)計的要求：正確性、可讀性、健壯性、時間效率高和存儲量低

時間復(fù)雜度和空間復(fù)雜度

時間復(fù)雜度

推導(dǎo)大O階方法

• 用常數(shù)1取代運行時間中所有的加法常數(shù)
• 修改后的運行次數(shù)函數(shù)中，只保留最高項
• 如果最高項存在且不是1，則去除與這個項相乘的常數(shù)
• 得到最后的結(jié)果就是大O階

線性階
一般含有非嵌套循環(huán)涉及線性階，線性階就是隨著問題規(guī)模n的擴大，對應(yīng)計算次數(shù)呈直線增長

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

平方階

int i, j, n = 100, sum = 0;
for(i=0; i<n; i++){
  for(j=0; i<n; i++){
    printf("I'm here...\n");
  }
}

int i, j, n = 100, sum = 0;
for(i=0; i<n; i++){
  for(j=i; i<n; i++){
    printf("I'm here...\n");
  }
}

由于當(dāng)i=0時，內(nèi)循環(huán)執(zhí)行了n次，當(dāng)i=1時，內(nèi)循環(huán)執(zhí)行了n-1次...當(dāng)i=n-1時，內(nèi)循環(huán)執(zhí)行1次，所以總的執(zhí)行次數(shù)應(yīng)該是：
用推導(dǎo)大O的攻略，第一條忽略，因為沒有常數(shù)相加。第二條只保留最高項，所以n/2這項去掉。第三條，去除與最高項相乘的常數(shù)，最終得到

對數(shù)階

int i = 1, n = 100;
while(i<n){
  i = i * 2;
}

• 由于每次i*2之后，就舉例n更近一步，假設(shè)有x個2相乘后大于或等于n，則會退出循環(huán)。
• 于是由得到， 所以這個循環(huán)的時間復(fù)雜度為

函數(shù)調(diào)用的時間復(fù)雜度分析

void function(int count){
  printf("%d", count);
}

int main(){
  int n=0, i=0, j=0;
  n++; //1
  function(n); //n
  for(i=0; i<n; i++){  //n^2
    function(i);
  }
  for(i=0; i<n; i++){ //n^2
    for(j=i; j<n; j++){
      printf("%d", j);
    }
  }  
}

常見的時間復(fù)雜度

常見的時間復(fù)雜度

常用的時間復(fù)雜度所耗費的時間從小到大依次是：