我去年給自己定了個(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ō)少話(huà)，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)乳蛾。
線(xiàn)性階
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)閚=n1, 1=n0, 所以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á)式成立：2x = n, 及x = log2n, 時(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ù)為n2绩衷，時(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ù)更新中...
