算法時間復雜度

要判斷算法的好壞，可以從時間方面進行分析。算法運行的越快，所用的時間越短則算法越好。但是同一個算法在不同的平臺上的運行時間不同。那么又該如何進行評判呢？我們采用時間復雜度進行衡量。

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

個人理解:由于不同的機器指令執行的速度不一樣，而我們的代碼又常常是跑在多臺不同機器上的，為了找出與機器無關但又可以說明代碼效率的量標，于是就選擇時間復雜度只與代碼的執行次數有關，即:T(N)。一般情況下，隨著N不斷增大，T(N)增長緩慢的算法時間復雜度越低，算法越好。

2.如何分析一個算法的時間復雜度：

• 順序結構，時間復雜度等于每步相加；選擇分支結構，時間復雜度等于最大時間復雜度的那個分支；循環結構，時間復雜度每個循環體相乘
• 用常數1取代運行時間中的所有加法常數；只保留階數最高的那一項；高階項前面的系數可以直接用1替代。

時間復雜度為O(1)

int a = 1 , b = 3 , sum = 0;  //執行1次
sum = a + b;   //執行1次
cout<<"the sum is :"<<sum<<endl; //執行1次     // 1+1+1 = 3 --> O(1)

時間復雜度為O(N)

//執行N次   
for(i=0;i<=n;i++){printf("the data is %d\n",i)    
}    //  N * 1 = N   --->   O(N)

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

//執行N次   
for(j=0;j<=n;j++){    //執行N次for(i=0;i<=n;i++){   //執行N次printf("the data is %d\n",i)  }  
}                        //N * N = N^2  ----->   O(N^2)

時間復雜度為O(logN)

//執行N/2次   
while(i<n){count<<"the data is :<<i<<endl;i = i*2;   
}                     

常用的時間復雜度所耗費的時間從小到大依次是：
O(1)<O(logn)<O(n)<O(nlogn)<O(n^2)<O(n3)<O(2^n)<O(n!)<O(nn)

3.最壞情況：

• 最壞情況運行時間是一種保證，那就是運行時間將不會再壞了。一般在沒有特殊說明的情況下，都是指最壞時間復雜度。

4.平均情況

• 平均運行時間是所有情況中最有意義的，因為它是期望的運行時間。

5.遞歸算法的時間復雜度的計算

• 在算法的分析中，當一個算法中包含遞歸調用時，其時間復雜度的分析會轉化成為一個遞歸方程的求解。而對遞歸方程的求解，方法多種多樣，目前主流的方法：代入法，迭代法，公式法，母函數法，差分方程法。