只是一些有趣的討論，靈感來自我班上的一次談話。
有兩種演算法，一種具有時間復雜度log n 和另一種log (n m)。
我對平均情況的爭論是否正確，log (n m)一個會執行得更快，而在漸近地考慮它時它們在運行時間上沒有差異？因為同時取極限和f1'/f2'會得到一個常數，所以它們的增長順序是相同的。
謝謝！
uj5u.com熱心網友回復：
正如我從問題中看到的那樣，n和m都是自變數。所以在說明的時候
O(m n) = O(n)
它應該適用于any m，這不是：反例是
m = exp(n)
O(log(m n)) = O(log(n exp(n))) = O(log(exp(n))) = O(n) > O(log(n))
這就是為什么在一般情況下我們只能說，
O(log(m n)) >= O(log(n))
一個有趣的問題是當 O(m n) = O(n). 如果m增長不是快則多項式的n，即O(m) <= O(P(n))：
O(log(m n)) = O(log(P(n) n)) = O(log(P(n))) = k * O(log(n)) = O(log(n))
在（多）圖的情況下，我們很少有那么多邊O(m) > P(n)：即使是完整的圖也Kn只包含m = n * (n - 1) / 2 = P(n)邊，這就是為什么
O(m n) = O(n)
適用于普通圖（無平行/多邊，無環）
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/313556.html