小編最近在學習如何計算一個算法的時間複雜度。
為什麼學習計算一個算法的時間複雜度呢？
因為需要比較兩個算法的好壞需要有一個統一的評判标準。
可能各位第一反應是兩個算法求解同一個執行個體，在求解結果相同的情況下，哪個算法所用的時間越短，這個算法就越好。但是，實際情況是現在不同計算機之間的硬體差距較大，有可能硬體好的計算機運作品質低的代碼所用的時間比硬體差的計算機運作品質高的代碼所用的時間短，是以僅靠時間來判斷算法品質高低顯然不可行。
為此，在求解結果相近的情況下，如果要比較兩個算法的優劣，則需要比較兩個算法的時間複雜度。
算法時間複雜度的概念是什麼呢？别急，且聽小編慢慢道來。
其實各位在編寫程式時也一定發現循環嵌套越多的程式，那麼運作時間就會越慢。我們以三個求和的程式為例，下面三個程式都是求10000行10000列元素都為1的矩陣所有元素之和：
a=0;
b=ones(1e4,1e4);
for i=1:1e4
for j=1:1e4
a=a+b(i,j);
end
end
這個程式運作的時間為5.7秒
a=0;
b=ones(1e4,1e4);
for i=1:1e4
a=a+sum(b(i,:));
end
這個程式運作的時間為1.9秒
b=ones(1e4,1e4);
a=sum(b(:));
這個程式運作的時間為0.4秒
很容易發現第一個程式為2層循環嵌套，第二個程式為1層循環嵌套，第三個程式無循環嵌套。可見求解同樣一個問題，循環嵌套層數越多求解時間越長。
我們再仔細觀察一下：
第一個程式
a=a+b(i,j);
這行代碼共運作10000*10000次
第二個程式
a=a+sum(b(i,:));
這行代碼共運作10000次
第三個程式
a=sum(b(:));
這行代碼隻運作一次
其實大家也可以發現，程式中某一行代碼運作的次數越多，則運作的時間就越長，是以可以将算法的時間複雜度與程式總的運作次數關聯起來。程式的運作次數用f(n)表示，比如說上面三個程式如果是求n行n列元素都為1的矩陣的所有元素之和，
那麼第一個程式執行的次數各行代碼的運作次數如下：
a=0; %運作1次
b=ones(n,n); %運作1次
for i=1:n %運作n+1次
for j=1:n %運作n*(n+1)次
a=a+b(i,j); %運作n*n次
end
end
則f(n)=1+1+(n+1)+n*(n+1)+n*n=2n^2+2n+3
第二個程式執行的次數各行代碼的運作次數如下：
a=0; %運作1次
b=ones(n,n); %運作1次
for i=1:n %運作n+1次
a=a+sum(b(i,:)); %運作n次
end
則f(n)=1+1+(n+1)+n=2n+3
第三個程式執行的次數各行代碼的運作次數如下：
b=ones(n,n); %運作1次
a=sum(b(:)); %運作1次
則f(n)=1+1=2
當n趨于無窮大時，第一個程式的f(n)趨于2n^2，第二個程式的f(n)趨于2n，第三個程式的f(n)依然為2。
至此，給出算法時間複雜度和程式運作次數之間的關系。一個算法的時間複雜度就用這種當n趨近于無窮大時f(n)趨近的值進行表示，算法的時間複雜度用O(n)表示，是以第一個程式的O(n)=n^2，為什麼把2去掉了，因為為了便于表示，雖然n^2前的系數2對整體值産生些影響，但如果把系數2去掉也不會影響整體的趨勢。同理，第二個程式的O(n)=n，第二個程式的O(n)=1。
下面再給出一個程式，讓大家求一下這個程式的時間複雜度。
a=0;
for i=1:2:n
a=a+i;
end
實際上求的是1至n之間所有奇數的和。
不難計算出這個程式的時間複雜度O(n)=log2(n)約等于log(n)，當n很大時以2為底和以10為底的值相差不大。
最後把常見算法的時間複雜度從小到達排序
O(1)常數階<O(logn)對數階<O(n)線性階<O(nlogn)<O(n^2)平方階<O(n^3)立方階
參考
- 清晰的了解算法中的時間複雜度？ - 蔡先生的回答 - 知乎 https://www.zhihu.com/question/20196775/answer/154922935
微網誌：随心390
長按識别二維碼關注我們