for (int i = 0; i < 2*n; i ) {
if (i == n){
for (int j = 0; j < i; j ) {
for (int k = 0; k < i; k ) {
O(1);
}
}
}
else {
for (int j = 0; j < i; j ) {
O(1);
}
}
問題只是問上面代碼的時間復雜度是多少。根據解決方案，只有一種情況，時間復雜度為O(n^2)。
這就是我解決它的方法：
有一個 for 回圈嵌套所有其他代碼。在 for 回圈的內容中是一個 if 陳述句。if 陳述句將代碼分為兩個方向。如果（i==n），那么它分支到分支#1，如果（i！=n）那么它分支到分支#2。
分支#1：for (...) --> if (...) --> for (...) --> for (...) --> O(1)。因此 n(1 n ( n ( 1 ) ) ) = n n^2( n (1) ) = n n^3(1) = n n^3。這被簡化為 n^3。因此分支#1 的時間復雜度是O(n^3)。
分支#2：for (...) --> if (...) else --> for(...) --> O(1)。因此 n(1 n(1)) = n n^2(1) = n n^2。這被簡化為 n^2。因此分支#2 的時間復雜度是O(n^2)。
因此最壞的情況是分支#1，它的時間復雜度為O(n^3)。最好的情況是分支#2，它的時間復雜度為O(n^2)。根據問題，只有一種情況，時間復雜度為O(n^2)。我需要幫助知道我在分析中做錯了什么。
uj5u.com熱心網友回復：
由于以下原因，您的分析不正確。
雖然您已正確識別出具有不同復雜性的兩個分支，但它們實際上都發生了……對于所有N大于 1 的值。
- 第一個分支出現一次。
- 第二個分支出現
2N - 1次數。
因此，由于這些不是不同的情況，因此沒有“最佳情況”或“最壞情況”。
實際上：
整個計算中第一個分支對復雜性的貢獻是
1 x O(N^2)。貢獻第二個分支是
(2N - 1) x O(N)。
換句話說，兩個分支都有貢獻O(N^2)，整體復雜度是兩個貢獻的總和；即O(N^2)。
（請注意，我的分析相當粗略和準備就緒……但如果有人進行了嚴格的分析，我認為他們會得到相同的結果。）
另一種快速而骯臟的方法是O(1)用只會增加計數器的東西來替換；在@johnchen902's answer 中查看修改后的代碼。運行程式，N并N針對計算出的計數繪制不同的圖形。
或者要獲得完全嚴格的答案，請做一些代數并計算出計數作為 的函式的公式N。
uj5u.com熱心網友回復：
這個形狀的面積是多少？
n*n
┌───────────────────┐ 1
│ ┌─────────────────┘
│ │
│ │
n│ │
│ │
│ │
│ │
└─┘
1
該區域顯然是 ?(n 2 )，而不是 ?(n 3 )。或者， 的確切輸出是foo什么？
int foo(int n) {
int ans = 0;
for (int i = 0; i < 2 * n; i ) {
if (i == n) {
for (int j = 0; j < i; j ) {
for (int k = 0; k < i; k ) {
ans = 1;
}
}
} else {
for (int j = 0; j < i; j ) {
ans = 1;
}
}
}
return ans;
}
是 3n 2 -2n。換一種方式，
for (...) --> if (...) --> for (...) --> for (...) --> O(1)。因此 n(1 n ( n ( 1 ) ) )
不緊。
uj5u.com熱心網友回復：
該陳述句if (i == n)將使以下代碼執行兩次。if 陳述句下面的代碼是 On^2。2 x On^2 是 On^2
uj5u.com熱心網友回復：
讓我們把演算法放到一些實際措辭的例子中。例如，假設我們處理干草堆，并在其中尋找針頭。
for (int i = 0; i < 2*n; i ) {
處理2*n干草堆，編號0,1, ...,2n-1。if (i == n) {
當你處理干草堆數時n，..（在 O(i 2 ) 情況下）
...在您的搜索中要非常徹底。} else {
對于所有其他干草堆，..（在 O(i) 的情況下）
......正常進行。
在上面的程序中，確實有兩種情況：對haystack number 的徹底搜索n，以及每隔一個haystack 的粗略搜索。
您的分析中缺少的是演算法必須同時完成：一個徹底的案例和所有粗略的案例。因此，對于執行演算法的人來說，沒有選擇是進行一次徹底搜索還是進行多次粗??略搜索。他們必須按順序進行n粗略搜索，然后是徹底搜索，然后是n-1更粗略的搜索。
當我們談論演算法復雜度的不同情況時，它們是依賴于輸入的情況。
想象i是我們演算法的輸入而不是回圈變數，并且沒有外for回圈：就好像我們被告知只搜索一個大海撈針，而不是所有大海撈針。那么您的分析將接近要點，盡管不需要乘以2n。
但是在這段代碼中，n是唯一的輸入，并且i是一個內部變數。所以i歸根結底不可能有依賴的情況。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qiye/335892.html
上一篇：計算字串中字符出現的次數？