根據大 O 表示法，如果一種演算法的時間復雜度為 O(2^n)，而另一種演算法的時間復雜度為 O(n^1000)，那么哪個演算法更快？
uj5u.com熱心網友回復：
對于我們每天遇到的較小數量的大小，2^n 將小于 O(n^1000)，但如果 n 變得足夠大，在這種情況下它會反轉并且 2^n 將開始變得比 n 快^1000
uj5u.com熱心網友回復：
如何識別一些不明顯情況的整體行為：獲取兩個函式的對數。
（有時我們也可以得到函式的比率并評估大 n 的比率限制，這里這種方法不好）
log(2^n) = n*log(2)
log(n^1000) = 1000*log(n)
第一個結果是具有正系數的斜線。第二個圖是具有負二階導數的凸曲線，因此第一個函式在某個較大的 n 值處變大。
uj5u.com熱心網友回復：
O(n^1000) 與 (n^2) 和 O(n^777777777) 屬于同一類，后者是多項式時間，而 O(2^n) 是指數時間，比多項式時間慢得多
https://www.bigocheatsheet.com/
轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/435767.html
標籤：算法
下一篇：帶有可選串列的笛卡爾積