我想計算在follow演算法中執行了多少條指令。
Begin
i = 0 // 1
While i <= n do: // n
i = i * 4 // 2n
print i // 1
End
So.. 3n 2?
3n 2 適合這個練習嗎？列印數是多少？
uj5u.com熱心網友回復：
正如目前所寫，
如果n ≥ 0：
Begin
i = 0 // θ(1)
While i <= n do: // θ(∞)
i = i * 4 // θ(∞)
print i // θ(1)
End
如果n < 0：
Begin
i = 0 // θ(1)
While i <= n do: // θ(1)
i = i * 4 // θ(1)
print i // θ(1)
End
現在，我懷疑i應該初始化為1. 在這種情況下，對于n → ∞：
Begin
i = 1 // θ(1)
While i <= n do: // θ(log(n))
i = i * 4 // θ(log(n))
print i // θ(1)
End
環路采用θ（日志（n））的步驟，因為i朝向取成指數較大的進步n：
1, 4, 16, 64, 256, 1024, 4096, 16384, 65536, 262144, 1048576, ...
請注意，我使用了theta 符號 (θ)，而不是特定的“指令計數”，因為在一般情況下，您無法知道每個高級陳述句對應多少“指令”。這就是為什么整個漸近符號系列都省略了常數，即O(c? n c?) = O(n).
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/355671.html
上一篇：通過多個元素進行二分搜索