Как этот основной алгоритм O (n)?

Question

int G(int a[], int n) {
int x=0, i, j;

 for(i=1; i<n; i=i*2){
 for(j=0; j<i; j++)
     x += a[j];
 }
 return x;
}

Как в худшем случае жестко ограничен этот алгоритм O (n).Не выполнен ли первый цикл O (log (n) раз), а второй для цикла выполнено O (n) раз, что дает O (n logn)?

Answer 1

O ( n ) означает, что алгоритм в конечном счете требует не более некоторого числа шагов, пропорциональных n , когда его входной размер равен n .В этой характеристике внутренний цикл равен O ( n ), но его входной размер равен i, поэтому требуется некоторое количество шагов, пропорциональное i.

.итерации внутреннего цикла.Если n является степенью двойки, то это 1 + 2 + 4 + 8 +… + n/2.Сумма этой серии n-1.Таким образом, вся программа выполняет n-1 итераций, когда ее входной размер равен n.Таким образом, это O ( n ).

(Если n не является степенью двойки, число итераций равно p-1, где p - наименьшая мощностьиз 2 не менее n. p-1 меньше 2*n, что пропорционально n, поэтому программа по-прежнему O ( n ).)