這個計算^ n的算法如何被重寫爲在O（log n）時間運行？

Question

假設您想計算一個ⁿ。一個簡單的算法會乘以n次，如下所示：

result = 1; 
for(int i =1; i <= n; i++) 
    result *= a; 

該算法需要O（n）個時間。不失一般性，假設N = 2 ^ķ

可以使用以下方案提高算法：

result = a; 
for (int i = 1; i <= k; i++) 
    result = result * result; 

該算法需要O（log n）的時間。對於一個任意n，你可以修改算法並證明覆雜度仍然是O（logn）

這麼混亂，那麼n怎麼樣？爲什麼只在第二個例子中顯示k？不明白這是怎麼變成O（logn）的時間複雜度的...

Answer 1

第二種算法在一般情況下不起作用;它只適用於有一些k，這樣你可以寫n = 2 ^k。如果有一個k你可以做到這一點，那麼通過取平等的兩邊的日誌，你會得到該日誌n = k的。因此：

• 循環計數到k，運行O（log n）次。
• 因此，循環運行時間O（log n）。

如果你想擺脫神祕k的，你可以寫

int result = a; 
for (int i = 0; i < log2(n); i++) { 
    result = result * result; 
} 

這更清楚地運行在O（log n）的時間，因爲在循環運行日誌 n次， O（1）是否在每次迭代中工作？

我不認爲「不失一般性」地說n是兩個完美的力量是公平的，因爲不是所有的數字都是！只有n是2的冪時，上面的代碼纔會起作用。您可以通過使用具有O（log n）複雜性但可用於任何電源的repeated squaring algorithm將其推廣到非二次方。

希望這會有所幫助！