這個函式的時間復雜度（大 O）是多少？以及如何計算？
我認為是 O(N^3) 但我不確定。
int DAA(int n){
int i, j, k, x = 0;
for(i=1; i <= n; i ){
for(j=1; j <= i*i; j ){
if(j % i == 0){
for(k=1; k <= j; k ){
x = 10;
}
}
}
}
return x;
}
uj5u.com熱心網友回復：
復雜性是 O(n^4)
但不是因為你盲目地放棄了未使用的迭代。
這是因為當您考慮所有指令時，O(n n^3 n^4)=O(n^4)
int DAA(int n){
int x = 0;
for(int i=1; i <= n; i ) // O(n)
for(int j=1; j <= i*i; j ) // O(1 2 ...n^2) = O(n^3)
if(j % i == 0) // O(n^3) same as loop j
for(int k=1; k <= j; k ) // O(n^4), see below
x = 10; // O(n^4) same as loop k
return x;
}
條件內回圈的復雜性
回圈k只執行 when j%i==0，即{i, i*2, i*3 ... i*i}
所以對于最內層回圈執行的情況，演算法是有效的
int DAA(int n){
int x = 0;
for(int i=1; i <= n; i ) // O(n)
for(int t=1; t <= i; t ) // O(1 2 ... n) = O(n^2)
for(int k=1; k <= t*i; k ) // O(n^4)
x = 10;
return x;
}
為什么簡單地洗掉未使用的迭代不起作用？
讓我們說現在
int DAA(int n){
int x = 0;
for(int i=1; i <= n; i ) // O(n)
for(int j=1; j <= i*i; j ) // O(1 2 ... n^2) = O(n^3)
if(j == i)
for(int k=1; k <= j; k )
x = 10; // oops! this only run O(n^2) time
return x;
}
// if(j==i*log(n)) also cause loop k becomes O((n^2)log(n))
// or, well, if(false) :P
雖然最里面的指令只是運行O(n^2)時。程式實際上做了if(j==i)（和j ，j<=i*i）O(n^3)時間，這使得整個演算法O(n^3)
uj5u.com熱心網友回復：
如果您擺脫無所作為的迭代，時間復雜度會更容易計算。除非j是 的倍數，否則中間回圈不會做任何事情i。因此，我們可以強制j為倍數i并消除該if陳述句，這使代碼更易于分析。
int DAA(int n){
int x = 0;
for(int i=1; i <= n; i ){
for(int m=1; m <= i; m ){ // New variable to avoid the if statement
int j = m*i; // The values for which the inner loop executes
for(int k=1; k <= j; k ){
x = 10;
}
}
}
return x;
}
外回圈迭代n次數。O(n) 到目前為止。
中間回圈迭代1時間，然后2時間，然后……n時間。人們可能會從 O(n 2 ) 排序演算法中識別出這種設定。回圈執行n次數，迭代次數增加到n，導致 O(n×n) 復雜度。
內回圈按 n×n 次的順序執行（中間回圈的復雜度）。每次執行的迭代次數增加到 n×n（ 的最大值j）。類似于中間回圈如何乘以它的執行次數和最大迭代次數以獲得其復雜性，內部回圈的復雜性 - 因此整個代碼 - 應該變成 O(n 4 )，但我將離開作為練習的精確證明。
上面確實假設時間復雜度表示x = 10;執行的次數。也就是說，它假設最內層回圈的主要作業壓倒了其余的作業。這通常是令人感興趣的，但也有一些注意事項。
第一個警告是，增加10并不比增加壓倒更多的作業。如果該行x = 10;不是“做作業”的方便替代品，那么時間復雜度可能應該包括所有迭代，即使是那些不作業的迭代。
第二個警告是if陳述句中的條件相對于最里面的回圈來說是廉價的。在某些情況下，條件可能很昂貴，因此時間復雜度應包括if陳述句執行的次數。消除該if陳述句確實會干擾這一點。
如果您碰巧遇到了這些警告之一，則需要對省略的內容進行計數。修改后的代碼在每次執行時省略了中間回圈的i 2 -i 次迭代n。因此，省略的迭代將對整體復雜性貢獻 n 倍 n 2 -n，或 O(n 3 )。
因此，原始代碼的復雜度為 O(n 4 n 3 )，與 O(n 4 ) 相同。
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/344358.html
上一篇：盜屋變種：最多可盜K間屋
下一篇：加權回圈有向圖中的最長路徑