算法的對數複雜度

對於我來說，理解算法的對數複雜度是困難的。算法的對數複雜度

例如

for(int j=1; j<=n; j*=2){ 
    ... 
}

其複雜度爲O（log N）

所以，如果它是什麼j*=3？那麼複雜度就是O（log N）？

2013-07-01 Deqing

[本文檔]的最後一張幻燈片（http://faculty.kfupm.edu.sa/ics/jauhar/ics202/Unit03_ComplexityAnalysis1.ppt）解釋了對數循環的一般情況。 –

只要循環體是O（1），就可以說是。

然而，請注意，日誌 N =登錄 N /登錄 3，所以它也是爲O（log 2 N），由於恆定因子並不重要。

還要注意，很明顯從這樣的說法，對於任何固定的恆定k，爲O（log _ķ N）也爲O（log 2 N），因爲你可以與k替代3。

2013-07-01 02:47:23

這就是爲什麼對數複雜度通常表示爲「log N」而沒有指定基數的原因。 –

@PatriciaShanahan嗯，我一直認爲簡單的'log'作爲日誌庫2，但是你的方式也是有意義的。 –

在Big O符號中，重要的不是Log2或Log3，重要的是算法的複雜性如何隨着輸入大小而增長。常數時間，Log，Linear和Exp是常見的。 – Ayman

基本上，是的。讓我們假設你的循環如下所示：

for (int j = 1; j < n; j *= a) {...}

其中a是一些常量。如果for循環執行了k次，那麼在最後一次迭代中，j將等於^k。並且由於N = O（j）和j = 0（N = O（a ^k））。由此得出k = 0（log _a N）。再次，for循環執行k次，因此該算法的時間複雜度爲O（k）= O（log _a N）。

2013-07-01 13:20:40 michelangelo

回答