我正在研究演算法分析以及演算法屬于哪個漸近類。
我在互聯網上找到了一個簡單的練習，有兩個解析度，我不知道哪個是正確的，或者如果兩者都正確，它們之間有什么區別？
決議 1
Begin
i = 0 // O(1)
While i <= n do: // O(n)
i = i 4 // O(1)
print i // O(1)
End
RESULT: This algorithm belongs to Θ = O(n).
決議 2
Begin
i = 0 // 1
While i <= n do: // n
i = i * 4 // 2n
print i // 1
End
RESULT: This algorithm belongs to Θ = 3n 2.
A - 這兩個決議對嗎？如果是，它們之間有什么區別？
B - 他們也必須計算“印刷品”？
uj5u.com熱心網友回復：
我很好奇為什么在解決方案 2 中，您將該行標記i = i 4為 O(2n)。當n更高時，該行代碼是否需要更長的時間才能運行？我不這么認為 - 似乎它總是需要相同的時間來運行。
一般來說，O(1)無論輸入的大小如何，總是需要相同的時間來運行的東西。例如，i = i n無論n是 1 還是 1,000,000 ，陳述句行將花費相同的時間。
一般來說，某事所O(n)花費的時間與 成正比n。因此，如果n是兩倍大，則運行時間將增加兩倍。請注意，我們并不是說 O(n) 的東西總是需要n步驟。它可能需要2*n步驟，或10*n步驟，或n/2步驟，但它始終與 成正比n。例如，您的 while 回圈符合這一類別。如果n是兩倍大，它們將需要兩倍的時間才能運行。
所以，沒有O(2n)orO(3n)或 or 之類的東西O(3n 2)。所有這些都描述了與 成正比的事物，n因此它們都將被描述為O(n)。
當然，還有其他類別，例如O(n^2)與 n 的平方成正比O(log n)的事物，或與 n 的對數成正比的事物等。
需要明確的是 - 此解釋適用于正在開發如何思考 big-O 風格分析的直覺的初學者。一個更高級的學生學習 big-omega、big-theta 等，將需要更細致入微的定義。
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/355675.html
上一篇：如何通過特定條件創建新列？