Время сложности n ^ 2

Question

Это O (N ^ 2) или O (nlogn).Разве это не ^ ^ 2, когда есть вложенные циклы?

int a[], N;
int f1(){ int i, j, sum=0;
    for (i=1;; i=2*i)
    {
        If (i>=N)  return sum;
        for (j=1; j<2*i;j++) sum+=a[i];
    }

Answer 1

Это O(N log N), поскольку внешний цикл удваивает значение i на каждой итерации. Таким образом, сложность внешнего цикла составляет O(log N) вместо O(N).

Если бы у вас было i++ или подобное вместо i=2*i, тогда временная сложность двух циклов была бы O(n^2).

Редактировать: это упрощенный анализ. Пожалуйста, см. ответ от R Sahu для более тщательного анализа.

Answer 2

Это O (N ^ 2) или O (nlogn).

Это ни то, ни другое.

Разве это не ^ ^ 2, когда есть вложенные циклы?

Это верно, когда вы перебираетепредметы линейно.Это не так в вашем случае.

В вашем случае ...

Значения i: 1 2 4 8 16 ... N

внутренний цикл выполняется 2 + 4 + 8 + 16 + 32 ... N раз.

Это геометрический ряд.Сумма геометрического ряда равна a(1 - r^n)/(1 - r).

В вашем случае a равно 2, r равно 2, а n равно log2(N) (журнал с основанием 2).Следовательно, после некоторого упрощения сумма равна 2*2^(log2(N)), что равно 2*N.

, т.е. ваша алгоритмическая сложность равна O(N).

Спасибо @LedHead заисправление ошибки в исходном посте.