如果我們有 2 個演算法。其中一個是O()時間復雜度，另一個是θ()時間復雜度。我們更喜歡哪一種來解決我們的問題？為什么？
uj5u.com熱心網友回復：
在兩種不同的符號之間進行這樣的比較對我來說似乎沒有那么有意義，但這是邏輯：θ指示演算法的操作次數函式的上限和下限。而 O僅表示上限。因此從技術上講，具有θ(1)時間復雜度的函式也是O(nlogn)。關于這個問題，我根據這個邏輯把我的評論放在解釋的最后。
θ(nlogn)時間復雜度意味著您的演算法將執行的運算元上限為nlogn，下限為nlogn，即，運算元將是 的常數倍nlogn。
O(nlogn)時間復雜度意味著您的演算法將執行的運算元上限為nlogn，即最大運算元將是 的常數倍nlogn。
請注意，在第二種情況下，我們無法對可以執行的最小運算元發表任何評論。nlogn只要運算元不超過nlogn輸入大小趨于無窮大的倍數，任何函式都可以說是有上限的。因此，您的函式可以具有恒定時間、線性時間或對數復雜度。既然我們有可能有操作的號碼是θ(n)，θ(logn)，θ(n1)等我要說的是，使用演算法O(nlogn)會更好。
uj5u.com熱心網友回復：
讓我們嘗試比較演算法：
第一個演算法具有O(nlogn)時間復雜度，這意味著執行時間t1是
t1 <= k1 * n * log(n) o(n * log(n))
第二個演算法是θ(nlogn)，這就是為什么
t2 = k2 * n * log(n) o(n * log(n))
假設n是足夠大的，所以我們可以忽略o(n * log(n))來看，我們仍然有2點這里的可能性。
t1 < n * log(n)t1 = k1 * n * log(n)（至少在一些最壞的情況下）
在第一種情況下，我們應該更喜歡演算法2large n，因為當演算法足夠大時，1它的執行時間更短n。
在第二種情況下，我們必須比較unknown k1和k2，我們沒有足夠的資訊來選擇第一種和第二種演算法。
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/340380.html
上一篇：從python中的2個串列中獲取一定范圍內的所有數字組合的高效演算法
下一篇：了解按位二進制組合演算法