演算法效率的度量方法:

演算法采用的策略，方案
編譯產生的代碼質量
問題的輸入規模
機器執行指令的速度

　　由此可見，拋開這些與計算機硬體、軟體有關的因素，一個程式的運行時間依賴于演算法的好壞和問題的輸入規模

　　我們研究演算法的復雜度，側重的是研究演算法隨著輸入規模擴大增長量的一個抽象，而不是精確的定位需要執行多少次

　　我們不關心語言、環境等，只關心它所實作的演算法，
　　我們在分析一個演算法的運行時間時，重要的是把基本操作的數量和輸入模式關聯起來

　　當n=1是，A演算法不如B演算法，隨著n的增長，A演算法反超B演算法，總體來說A比B演算法更優秀

　函式的漸近增長：給定兩個函式f(n)和g(n)，如果存在一個整數N，使得對于所有的n>N,f(n)總是比g(n)大，那么我們說f(n)的增長漸近快于g(n)

演算法時間復雜度

定義：在進行演算法分析時，陳述句總的執行次數T(n)是關于問題規模n的函式，進而分析T(n)隨n的變化情況并確定T(n)的數量級，演算法的時間復雜度，也就是演算法時間度量，記作T(n) = O(f(n))，它表示隨問題規模n的增大，演算法執行時間的增長率和f(n)的增長率相同，稱作演算法的漸近時間復雜度，簡稱時間復雜度，其中f(n)是問題規模n的某個函式，（關鍵點：執行次數==時間）

如何分析一個演算法的時間復雜度

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

常數階：

int sum=0,n=100;
printf("Hello World!");
printf("Hello World!");
printf("Hello World!");
printf("Hello World!");
printf("Hello World!");
printf("Hello World!");
printf("Hello World!");
printf("Hello World!");
sum = (1+n)*n/2;

時間復雜度不是O(8)，而是O(1)

線性階：一般含有非嵌套回圈涉及線性階，線性階就是隨著問題規模n的擴大，對應的計算次數呈直線增長

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

時間復雜度為O(n)

平方階：N次嵌套回圈

int i,j,n=100;
for(i=1;i<=n;i++)
{    for(j=0;j<n;j++)
    {
        printf("Hello，World");
    }
}

時間復雜度為O(n^N)

對數階：

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

每次i*2就距離n更近一步，所以由2^x = n得到x = log₂n,所以這個回圈的時間復雜度為O(logn)

函式呼叫的時間復雜度分析

1 int i,j; 2 for(i=0;i<n;i++){ 3 function(i); 4 ) 5 6 void function(int count){ 7 printf("%d",count); 8 }// function函式的時間復雜度是O(1),所以整體的時間復雜度就是回圈的次數O(n)

1 int i,j; 2 for(i=0;i<n;i++){ 3 function(i); 4 ) 5 6 void function(int count){ 7 int j; 8 for(j=count;j<n;j++){ 9 printf("%d",j); 10 } 11 }//function內部的回圈次數隨著count的增加(接近n)而減少，所以根據游戲攻略演算法的時間復雜度為O(n²)

思考：

n++;//   　　　　　　　　　　　　　　1
function(n);//　　　　　　　　　　　n²
for(i=0;i<n;i++)//　　　　　　　　 n²
{
    function(n);
}
for(i=0;i<n;i++)//　　　　　　　　 n²
{
    for(j=i;j<n;j++)
    {
        printf("%d\n",j);
    }
}

答案：上述代碼的時間復雜度為O(n^2)

常見的時間復雜度

耗費的時間從小到大：

O(1) < O(logn) < O(n) < O(nlogn) < O(n²) < O(n³) < O(2ⁿ) < O(n!) < O(nⁿ)

最壞情況和平均情況

平均運行時間是期望的運行時間
最壞運行時間是一種保證，在應用中，這是一種最重要的需求，通常除非特別指定，我們提到的運行時間都是指最壞情況的運行時間

演算法的空間復雜度

首先我們要明白，我們在寫代碼時，完全可以用空間來換取時間，

舉個例子：判斷某一年是否為閏年

　　我們可以實作要給演算法，每給一個年份，都會通過演算法計算得到是否是閏年的結果，
　　另一種演算法就是，建立一個陣列，將所有年份按下標的數字對應，如果是閏年，則此陣列元素對應的值為1，否則為0.

　　決議：對比兩個演算法，第一種演算法很明顯節約空間，但是每一次查詢都需要進行運算，而第二種演算法，雖然在記憶體中存了幾千個陣列，但是每次查詢只需要一次索引即可，

這就是典型的空間換時間，

　　演算法的空間復雜度通過計算演算法所需的存盤空間實作，演算法的空間復雜度的計算公式為：S(n)=O(f(n)),其中，n為問題的規模，F(n)為陳述句關于n所存盤空間的函式，

　　通常，我們都是用“時間復雜度”來指運行時間的需求，是用“空間復雜度”指空間需求

　　當直接要求我們求“復雜度”時，通常是指時間復雜度

顯然，對時間復雜度的追求更屬于演算法的潮流QAQ

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/199898.html

標籤：其他

上一篇：資料結構-希爾排序法

下一篇：眾數的演算法分析

資料結構與演算法（二）：時間復雜度和空間復雜度

演算法效率的度量方法:

演算法時間復雜度

演算法的空間復雜度