鑒于這個問題，在迭代器上增加 i 是通過將其值增加其自己的日志值來發生的。這個片段的大 O 時間復雜度是多少？
i = 10
while(i<n) {
i=i log(i);
}
uj5u.com熱心網友回復：
有趣的問題！這是制定運行時的第一步。
假設我們已經到達回圈中的某個點，對于某個自然數 k ， i 的值已經達到 2k。然后 i 增加到 2 k 1，我們需要大約 2 k / k 次迭代才能過去。為什么？那是因為
- 我需要增加的數量是 2 k 1 - 2 k = 2 k (2 - 1) = 2 k，并且
- 在每一步，將 i 增加 log i 將使 i 增加大約 log 2 k = k。
因此，我們可以將演算法分解為“階段”。在第一階段，我們從大小 2 3增長到大小 2 4，需要（大約）2 3 /3 個步驟。在第二階段，我們從大小 2 4增長到大小 2 5，需要（大約）2 4 / 4 個步驟。在多次重復這個程序之后，我們最終從大小 n/2 = 2 log n - 1增長到大小 n = 2 log n，需要（大約）2 log n / log n 步驟。因此，完成的作業總量由下式給出
2 3 / 3 2 4 /4 2 5 / 5 ... 2 log n / log n。
現在的目標是找到這個運算式的一些界限。我們可以看到總和至少等于它的最后一項，即 2 log n / log n = n / log n，所以所做的功是 Ω(n / log n)。我們還可以看到完成的作業少于
2 3 2 4 2 5 ... 2對數
≤ 2 log n 1 （幾何級數之和）
= 2n,
所以完成的作業是O(n)。這將運行時間夾在 Ω(n / log n) 和 O(n) 之間。
事實證明，Θ(n / log n)在這里確實是一個緊密的界限，這可以通過對 summation 進行更細致的分析來證明。
uj5u.com熱心網友回復：
讓我們看一下g(n)=O(f(n))的定義：說函式 g 的階數為 O(f(n)) 意味著存在一個數 n0 和一個常數 c 使得對于所有n>n0它是g(n)<=cf(n)。
看看最壞的情況，while 將運行最多n次，這意味著我們可以說您的代碼是O(n)順序的。
現在讓我們假設 while 回圈內的代碼是
(*) while(i<n) {
i = i i ;
}
這顯然應該跳過原始迭代更多的迭代。所以我們可以使用這段代碼來估計一個下限。檢查(*)我們看到，在每次迭代中，計數器都會加倍，如果我們稍微考慮一下，我們會看到對于 n 次迭代，每次都會拋出一半的輸入。因此 (*) 中的代碼將具有最壞情況的漸近運行時O(log n)。
現在我們估計原始代碼應該介于兩者之間，因此我們可以說它的漸近下界是Ω(log n)并且它的漸近上界是O(n)。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qiye/515242.html
標籤：算法时间复杂度复杂性理论
下一篇：html和css中的關系選擇器