我去年給自己定了個(gè)今年存款3萬(wàn)塊的小目標(biāo)，掐指一算，現(xiàn)在還差5萬(wàn)。

又是定小目標(biāo)的時(shí)間，2018年余額只有2天了，我參加了簡(jiǎn)書(shū)的堅(jiān)持寫(xiě)作60天以上的活動(dòng)，也算是激勵(lì)自己吧。第一部分將跟大家分享算法與數(shù)據(jù)結(jié)構(gòu)相關(guān)的知識(shí)，共同學(xué)習(xí)。廢說(shuō)少話，day1開(kāi)始。

概念

算法的時(shí)間復(fù)雜度是表示算法所消耗時(shí)間大小的量度，通常使用大O表示法來(lái)建立數(shù)學(xué)模型，即O(f(n))，隨著n的數(shù)值增大，O(f(n))的數(shù)值增長(zhǎng)的越慢就越是時(shí)間復(fù)雜度低的算法

大O階推導(dǎo)

大O表示法的關(guān)鍵在O里面的階，推導(dǎo)大O階的步驟：

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

例子

常數(shù)階

var a = 1, b = 1; //運(yùn)行一次
var sum = a + b; //運(yùn)行一次

運(yùn)行了2次，按照推導(dǎo)方法，“2”是常數(shù)，應(yīng)該用"1"來(lái)取代；然后就沒(méi)有出現(xiàn)階項(xiàng)，所以忽略后面兩個(gè)推導(dǎo)步驟。所以這里的時(shí)間復(fù)雜度為O(1)。

線性階

for(var i = 0; i < 2*n+3; i++){ //執(zhí)行了2*n+3次
  sum +=n;
}

執(zhí)行次數(shù)為2n+3，按照第一步推導(dǎo)為2n+1; 按照第二步推導(dǎo)修改為2n（為什么呢？因?yàn)閚=n¹, 1=n⁰, 所以n的為最高階項(xiàng)）；第三條，2n應(yīng)該除以常數(shù)2；所以這里的時(shí)間復(fù)雜度為O(n)。

對(duì)數(shù)階

var cout = 1;
while(cout < n){
  cout = cout * 2; 
}

假設(shè)循環(huán)次數(shù)為x, 則次表達(dá)式成立：2^x = n, 及x = log₂n, 時(shí)間復(fù)雜度為O(logn)。

平方階

  for(var i=0;i<n;i++){   
      for(var j=0;j<n;j++){
         //時(shí)間復(fù)雜度O(1)的語(yǔ)句
      }
  }

假設(shè)循環(huán)次數(shù)為n²，時(shí)間復(fù)雜度為O(n^2)

時(shí)間復(fù)雜度的比較

常見(jiàn)的時(shí)間復(fù)雜度所耗費(fèi)的時(shí)間大小關(guān)系：
O(1 )< O(logn) < O(n) < O(n*logn) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)

感謝閱讀！歡迎關(guān)注！持續(xù)更新中...