多對數和對數有什麼區別？
我無法想像一個不是polylogarithmic 而是logarithmic的。
$ O(\log N) $ 滿足兩者。
關於什麼 $ O(\log^{3}N) $ , $ O(\log^{100}N) $ ， 和 $ O(\log^{10000}N) $ ?
比方說 $ N=10^{10} $
定義：
據說一個算法執行在
- 對數時間如果 $ T(n) = O(log(n)) $
- 多對數時間如果 $ T(n) = O(log(n)^k) $ （也寫為 $ T(n) = O(log^k(n)) $ )
這意味著它們對於 $ k=1 $ . 否則它們是不同的，你的其他例子都是多對數的。我不確定如何確切地解釋差異是什麼，但也許一張圖片會幫助你*：*
如果 ，則稱算法需要對數時間
T(n) = O(log n)。如果
T(n) = O((log n)^k)，對於某個常數 k，則稱算法在多對數時間內執行。對數時間
如果一個算法需要對數時間，如果 $ T(n) = O(\log n) $ . 由於電腦使用二進制數字系統，對數通常以 2 為底（即， $ \log_2 n $ , 有時寫 $ \lg n $ ）。然而，通過改變對數的底數， $ \log_a n $ 和 $ \log_b n $ 僅由一個常數乘數不同，這在大 $ O $ 符號被丟棄；因此 $ O(\log n) $ 是對數時間算法的標準表示法，與對數的底數無關。
採用對數時間的算法通常在二叉樹的操作或使用二分搜尋時發現。
一個 $ O(\log n) $ 算法被認為是高效的，因為完成每個實例所需的每個實例的操作都會減少。
這種類型的一個非常簡單的範例是一種算法，它將字元串切成兩半，然後將右半部分切成兩半，依此類推。這將需要 $ O(\log n) $ 時間 （ $ n $ 是字元串的長度），因為我們在每次列印之前將字元串切成兩半（我們假設 console.log 和 str.substring 在恆定時間內執行）。這意味著，為了增加列印次數，我們必須將字元串的長度加倍。
多對數時間
如果一個算法在多對數時間內執行，如果 $ T(n) = O((\log n)^k) $ , 對於某個常數 $ k $ . 例如，矩陣鏈排序可以在並行隨機存取機上以多對數時間求解。