算法在移動(dòng)端開發(fā)中用到的并不多但是在面試時(shí)面試官為了試探你的水平經(jīng)常會問到。這塊在大學(xué)的時(shí)候數(shù)據(jù)結(jié)構(gòu)那門課中講的挺多的妙黍，各種排序悴侵，查找算法的時(shí)間復(fù)雜度，當(dāng)時(shí)理解的不夠好所以再來學(xué)習(xí)下拭嫁。
一個(gè)程序執(zhí)行的的時(shí)間是需要通過上機(jī)來確定的而且你取決于你的CPU的運(yùn)算能力可免，時(shí)間復(fù)雜度只是在算法中進(jìn)行的橫向?qū)Ρ?/code>不代表具體的時(shí)間。
1噩凹、時(shí)間頻度：一個(gè)算法中的語句執(zhí)行次數(shù)稱為語句頻度或時(shí)間頻度記作：T(N)
int test(void) {
printf("Hello, World!\n"); // 需要執(zhí)行 1 次
return 0; // 需要執(zhí)行 1 次
}
這個(gè)test類的時(shí)間頻度為T(2)
int aFunc(int n) {
for(int i = 0; i<n; i++) { // 需要執(zhí)行 (n + 1) 次
printf("Hello, World!\n"); // 需要執(zhí)行 n 次
}
return 0; // 需要執(zhí)行 1 次
}
這個(gè)時(shí)間頻度為n+1+n+1也就是T(2n+2)
時(shí)間頻度這個(gè)概念還是比較好理解的就是數(shù)一下當(dāng)前程序所有的語句每一句語句加起來一共執(zhí)行了多少次巴元。
開始引入時(shí)間復(fù)雜度的概念
存在常數(shù) c 和函數(shù) f(N)，使得當(dāng) N >= c 時(shí) T(N) <= f(N)驮宴，表示為 T(n) = O(f(n)) 逮刨。
如圖：
直線為T(n)=2n+2,曲線為f(n)=n^2
對圖中的兩條線進(jìn)行解釋：當(dāng)n=2是T(n)=f(n)則稱這個(gè)使f(n)=T(n)的這個(gè)n值2為C，當(dāng)n>C時(shí)f(n)的增長速度永遠(yuǎn)大于T(n)也就是f(n)是T(n)的上界堵泽。則可以表示為 T(n) = O(f(n))修己。
時(shí)間復(fù)雜度怎么計(jì)算：
本文開始的兩個(gè)例子：
1、T(n)=2則f(n)=2所以可以推算出O(f(n))=O(2)(這樣表示并不正確下面會解釋)
2迎罗、T(n)=2n+2所以可以推算出O(f(n))=O(2n+2)(這樣表示并不正確下面會解釋)
上面的這兩個(gè)例子的表示方法為什么不不正確的呢睬愤？從時(shí)間復(fù)雜度的定義可以看出來大O的表示法是一個(gè)極值或者說是一個(gè)不準(zhǔn)確的值它只是表示了T(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ù)厢岂。
從這三條規(guī)律可以得出第一個(gè)應(yīng)該是O(1)光督，第二個(gè)應(yīng)該是O(2n)，當(dāng)然還有l(wèi)ogn,n^2等算法塔粒，可以參考皇叔的博客
