如何使用求和符號證明算法是Θ（log n）？

Question

假設我有以下代碼：

int sum = 0; 
int val=128; 
for (int i=n; i>=1; i=i/2) { 
    for (int j=1; j<val; j++) { 
    sum ++; 
    } 
} 

你如何證明這是Θ（log n）的數學？

我通常的做法是使用求和（sigma notation），但在這種情況下，我們並沒有線性地增加循環變量。什麼是這樣的好方法？

Answer 1

i的值是n, n/2, n/4, ..., 1。由於它是整數，所以它的最終值是1。假設n爲2^k，則迭代次數爲k，即log n。因此情況不會改變，它是另一個for，具有一定的迭代次數。

由於val是恆定的，因此可以將內部循環視爲單個語句。