時間複雜度如何計算?
程序中的時間複雜度是怎麼計算的？
算法複雜度的介紹，見百科：
baike.baidu.com/view/7527.htm
時間複雜度
時間頻度
一個算法執行所耗費的時間，從理論上是不能算出來的，必須上機運行測試才能知道。但我們不可能也沒有必要對每個算法都上機測試，只需知道哪個算法花費的時間多，哪個算法花費的時間少就可以了。並且一個算法花費的時間與算法中語句的執行次數成正比例，哪個算法中語句執行次數多，它花費時間就多。一個算法中的語句執行次數稱為語句頻度或時間頻度。記為T(n)。
計算方法
1. 一般情況下，算法的基本操作重複執行的次數是模塊n的某一個函數f（n），因此，算法的時間複雜度記做：T（n）=O（f（n））
分析：隨著模塊n的增大，算法執行的時間的增長率和f（n）的增長率成正比，所以f（n）越小，算法的時間複雜度越低，算法的效率越高。
2. 在計算時間複雜度的時候，先找出算法的基本操作，然後根據相應的各語句確定它的執行次數，再找出T（n）的同數量級（它的同數量級有以下：1，Log2n ，n ，nLog2n ，n的平方，n的三次方，2的n次方，n！），找出後，f（n）=該數量級，若T(n)/f(n)求極限可得到一常數c，則時間複雜度T（n）=O（f（n））
例：算法：
for（i=1;i<=n;++i）
{
for(j=1;j<=n;++j)
{
c[ i ][ j ]=0; //該步驟屬於基本操作 ，執行次數：n的平方 次
for(k=1;k<=n;++k)
c[ i ][ j ]+=a[ i ][ k ]*b[ k ][ j ]; //該步驟屬於基本操作 ，執行次數：n的三次方 次
}
}
則有 T（n）= n的平方+n的三次方，根據上面括號裡的同數量級，我們可以確定 n的三次方 為T（n）的同數量級
則有f（n）= n的三次方，然後根據T（n）/f（n）求極限可得到常數c
則該算法的 時間複雜度：T（n）=O（n^3） 注：n^3即是n的3次方。
3.在pascal中比較容易理解，容易計算的方法是：看看有幾重for循環，只有一重則時間複雜度為O（n）,二重則為O（n^2），依此類推，如果有二分則為O(logn)，二分例如快速冪、二分查找，如果一個for循環套一個二分，那麼時間複雜度則為O(nlogn)。
分類
按數量級遞增排列，常見的時間複雜度有：
常數階O(1),對數階O(log2n),線性階O(n),
線性對數階O(nlog2n),平方階O(n^2)，立方階O(n^3),...，
k次方階O(n^k), 指數階O(2^n) 。隨著問題規模n的不斷增大，上述時間複雜度不斷增大，算法的執行效率越低。
關於對其的理解
《數據結構（C語言版）》------嚴蔚敏 吳偉民編著 第15頁有句話"整個算法的執行時間與基本操作重複執行的次數成正比。"
基本操作重複執行的次數是問題規模n的某個函數f(n)，於是算法的時間量度可以記為：T(n) = O( f(n) )
如果按照這麼推斷，T(n)應該表示的是算法的時間量度，也就是算法執行的時間。
而該頁對“語句頻度”也有定義：指的是該語句重複執行的次數。
如果是基本操作所在語句重複執行的次數，那麼就該是f(n)。
上邊的n都表示的問題規......
如何計算算法的時間複雜度
求解算法的時間複雜度的具體步驟是： ⑴找出算法中的基本語句； 算法中執行次數最多的那條語句就是基本語句，通常是最內層循環的循環體。 ⑵計算基本語句的執行次數的數量級； 只需計算基本語句執行次數的數量級，這就意味著只要保證基本語句執行次數的函數中的最高次冪正確即可，可以忽略所有低次冪和最高次冪的係數。這樣能夠簡化算法分析，並且使注意力集中在最重要的一點上：增長率。 ⑶用大Ο記號表示算法的時間性能。 將基本語句執行次數的數量級放入大Ο記號中。 如果算法中包含嵌套的循環，則基本語句通常是最內層的循環體，如果算法中包含並列的循環，則將並列循環的時間複雜度相加。例如： for(i=1;i<=n;i++) x++; for(i=1;i<=n;i++) for(j=1;j<=n;j++) x++; 第一個for循環的時間複雜度為Ο(n)，第二個for循環的時間複雜度為Ο(n2)，則整個算法的時間複雜度為Ο(n+n2)=Ο(n2)。 常見的算法時間複雜度由小到大依次為： Ο(1)＜Ο(log2n)＜Ο(n)＜Ο(nlog2n)＜Ο(n2)＜Ο(n3)＜…＜Ο(2n)＜Ο(n!)Ο(1)表示基本語句的執行次數是一個常數，一般來說，只要算法中不存在循環語句，其時間複雜度就是Ο(1)。Ο(log2n)、Ο(n)、Ο(nlog2n)、Ο(n2)和Ο(n3)稱為多項式時間，而Ο(2n)和Ο(n!)稱為指數時間。計算機科學家普遍認為前者是有效算法，把這類問題稱為P類問題，而把後者稱為NP問題。這隻能基本的計算時間複雜度，具體的運行還會與硬件有關。
如何計算算法的時間複雜度和空間複雜度
是說明一個程序根據其數據n的規模大小 所使用的大致時間和空間
說白了 就是表示 如果隨著n的增長 時間或空間會以什麼樣的方式進行增長
例
for(int i = 0; i < n;++i)
;
這個循環執行n次 所以時間複雜度是O(n)
for(int i = 0; i< n;++i)
{
for(int j = 0; j< n;++j)
;
}
這嵌套的兩個循環 而且都執行n次
那麼它的時間複雜度就是 O(n^2)
時間複雜度只能大概的表示所用的時間
而一些基本步驟 所運行的時間不同 我們無法計算 所以省略
如
for(int i = 0;i < n;++i)
a = b;
和
for(int i = 0;i < n;++i)
;
這個運行的時間當然是第二個快 但是他們的時間複雜度都是 O(n)
判斷時間複雜度看循環
C語言算法的時間複雜度如何計算啊？
看看這個 每個循環都和上一層循環的參數有關。 所以要用地推公式： 設i(n)表示第一層循環的i為n時的循環次數，注意到他的下一層循環次數剛好就是n，分別是0,1,2...n-1 所以，把每一層循環設一個函數分別為：j(n),k(n),t(n) 則有 i(n)=j(0)+...+j(n-1) j(n)=k(0)+...+k(n-1) k(n)=t(0)+...+t(n-1) i(0)=j(0)=k(0)=0 t(n)=1 而總循環數是i(0)+i(1)...+i(n-1) 可以根據遞推條件得出準確值 所以算法複雜度是O(i(0)+i(1)...+i(n-1))
記得采納啊
如何計算時間複雜度
如何計算時間複雜度
定義：如果一個問題的規模是n，解這一問題的某一算法所需要的時間為T(n)，它是n的某一函數 T(n)稱為這一算法的“時間複雜性”。
當輸入量n逐漸加大時，時間複雜性的極限情形稱為算法的“漸近時間複雜性”。
我們常用大O表示法表示時間複雜性，注意它是某一個算法的時間複雜性。大O表示只是說有上界，由定義如果f(n)=O(n)，那顯然成立f(n)=O(n^2)，它給你一個上界，但並不是上確界，但人們在表示的時候一般都習慣表示前者。
此外，一個問題本身也有它的複雜性，如果某個算法的複雜性到達了這個問題複雜性的下界，那就稱這樣的算法是最佳算法。
“大 O記法”：在這種描述中使用的基本參數是 n，即問題實例的規模，把複雜性或運行時間表達為n的函數。這裡的“O”表示量級 (order)，比如說“二分檢索是 O(logn)的”,也就是說它需要“通過logn量級的步驟去檢索一個規模為n的數組”記法 O ( f(n) )表示當 n增大時，運行時間至多將以正比於 f(n)的速度增長。
這種漸進估計對算法的理論分析和大致比較是非常有價值的，但在實踐中細節也可能造成差異。例如，一個低附加代價的O(n2)算法在n較小的情況下可能比一個高附加代價的 O(nlogn)算法運行得更快。當然，隨著n足夠大以後，具有較慢上升函數的算法必然工作得更快。
O(1)
Temp=i;i=j;j=temp;
以 上三條單個語句的頻度均為1，該程序段的執行時間是一個與問題規模n無關的常數。算法的時間複雜度為常數階，記作T(n)=O(1)。如果算法的執行時 間不隨著問題規模n的增加而增長，即使算法中有上千條語句，其執行時間也不過是一個較大的常數。此類算法的時間複雜度是O(1)。
O(n^2)
2.1. 交換i和j的內容
sum=0； （一次）
for(i=1;i<=n;i++) （n次 ）
for(j=1;j<=n;j++) （n^2次 ）
sum++； （n^2次 ）
解：T(n)=2n^2+n+1 =O(n^2)
2.2.
for (i=1;i
{
y=y+1; ①
for (j=0;j<=(2*n);j++)
x++; ②
}
解： 語句1的頻度是n-1
語句2的頻度是(n-1)*(2n+1)=2n^2-n-1
f(n)=2n^2-n-1+(n-1)=2n^2-2
該程序的時間複雜度T(n)=O(n^2).
O(n)
2.3.
a=0;
b=1; ①
for (i=1;i<=n;i++) ②
{
s=a+b; ③
b=a; ④
a=s; ⑤
}
解： 語句1的頻度：2,
語句2的頻度： n,
語句3的頻度： n-1,......
請問遞歸算法的時間複雜度如何計算呢?
遞歸算法的時間複雜度分析 收藏
在算法分析中，當一個算法中包含遞歸調用時，其時間複雜度的分析會轉化為一個遞歸方程求解。實際上，這個問題是數學上求解漸近階的問題，而遞歸方程的形式多種多樣，其求解方法也是不一而足，比較常用的有以下四種方法：
(1)代入法(Substitution Method)
代入法的基本步驟是先推測遞歸方程的顯式解，然後用數學歸納法來驗證該解是否合理。
(2)迭代法(Iteration Method)
迭代法的基本步驟是迭代地展開遞歸方程的右端，使之成為一個非遞歸的和式，然後通過對和式的估計來達到對方程左端即方程的解的估計。
(3)套用公式法(Master Method)
這個方法針對形如“T(n) = aT(n/b) + f(n)”的遞歸方程。這種遞歸方程是分治法的時間複雜性所滿足的遞歸關係，即一個規模為n的問題被分成規模均為n/b的a個子問題，遞歸地求解這a個子問題，然後通過對這a個子間題的解的綜合，得到原問題的解。
(4)差分方程法(Difference Formula Method)
可以將某些遞歸方程看成差分方程，通過解差分方程的方法來解遞歸方程，然後對解作出漸近階估計。
下面就以上方法給出一些例子說明。
一、代入法
大整數乘法計算時間的遞歸方程為：T(n) = 4T(n/2) + O(n)，其中T(1) = O(1)，我們猜測一個解T(n) = O(n2 )，根據符號O的定義，對n>n0，有T(n) < cn2 - eO(2n)（注意，這裡減去O(2n)，因其是低階項，不會影響到n足夠大時的漸近性），把這個解代入遞歸方程，得到：
T(n) = 4T(n/2) + O(n)
≤ 4c(n/2)2 - eO(2n/2)) + O(n)
= cn2 - eO(n) + O(n)
≤ cn2
其中，c為正常數，e取1，上式符合 T(n)≤cn2 的定義，則可認為O(n2 )是T(n)的一個解，再用數學歸納法加以證明。
二、迭代法
某算法的計算時間為：T(n) = 3T(n/4) + O(n)，其中T(1) = O(1)，迭代兩次可將右端展開為：
T(n) = 3T(n/4) + O(n)
= O(n) + 3( O(n/4) + 3T(n/42 ) )
= O(n) + 3( O(n/4) + 3( O(n/42 ) + 3T(n/43 ) ) )
從上式可以看出，這是一個遞歸方程，我們可以寫出迭代i次後的方程：
T(n) = O(n) + 3( O(n/4) + 3( O(n/42 ) + ... + 3( n/4i + 3T(n/4i+1 ) ) ) )
當n/4i+1 =1時，T(n/4i+1 )=1，則
T(n) = n + (3/4) + (32 /42 )n + ... + (3i &......
什麼是算法的時間複雜度?
時間複雜度表面的意思就是代碼花費的時間，但是一般使用這個概念的時候，更注重的是隨著數據量增長，代碼執行時間的增長情況。一般認為一個基本的運算為一次運行算，例如加減乘除判斷等等
例1和例2時間複雜度都可以簡單認為是o(N)，一般用時間複雜度的時候要取一個下限即可，不用那麼精確，可能你認為例1是o(2N)而例2是o(n)，但實際上這兩者對於時間複雜度的作用來說罰區別，前面已經說了，時間複雜度關注的是數據量的增長導致的時間增長情況，o(2N)和o(n)在數據量增加一倍的時候，時間開銷都是增加一倍（線性增長）。
又例如兩重循環的時間複雜度是o(N的平方)，N擴大一倍，時間複雜度就擴大4倍。所以時間複雜度主要是研究增長的問題，一般效率較好的算法要控制在o(N)或者o(log2N)
如何計算平均時間複雜度
計算方法
1. 一般情況下，算法的基本操作重複執行的次數是模塊n的某一個函數f(n)，因此，算法的時間複雜度記做：T(n)=O(f(n))
分析：隨著模塊n的增大，算法執行的時間的增長率和 f(n) 的增長率成正比，所以 f(n) 越小，算法的時間複雜度越低，算法的效率越高。
2. 在計算時間複雜度的時候，先找出算法的基本操作，然後根據相應的各語句確定它的執行次數，再找出 T(n) 的同數量級（它的同數量級有以下：1，log(2)n，n，n log(2)n ，n的平方，n的三次方，2的n次方，n!），找出後，f(n) = 該數量級，若 T(n)/f(n) 求極限可得到一常數c，則時間複雜度T(n) = O(f(n))
例：算法：
1
2
3
4
5
6
7
8
9
for(i=1;i<=n;++i)
{
for(j=1;j<=n;++j)
{
c[i][j]=0;//該步驟屬於基本操作執行次數：n的平方次
for(k=1;k<=n;++k)
c[i][j]+=a[i][k]*b[k][j];//該步驟屬於基本操作執行次數：n的三次方次
}
}
則有 T(n) = n 的平方+n的三次方，根據上面括號裡的同數量級，我們可以確定 n的三次方 為T（n）的同數量級
則有 f(n) = n的三次方，然後根據 T(n)/f(n) 求極限可得到常數c
則該算法的時間複雜度：T(n) = O(n^3) 注：n^3即是n的3次方。
3.在pascal中比較容易理解，容易計算的方法是：看看有幾重for循環，只有一重則時間複雜度為O(n)，二重則為O(n^2)，依此類推，如果有二分則為O(logn)，二分例如快速冪、二分查找，如果一個for循環套一個二分，那麼時間複雜度則為O(nlogn)。