Какова сложность этой двойной петли

#include <stdio.h> 

int main() { 
    int N = 32; /* for example */ 

    int sum = 0; 
    for (int i = 1; i <= N*N; i = i*3) 
     for (int j = 1; j <= i; j++) 
      sum++; 

    printf("Sum = %d\n", sum); 
    return 0; 
}

Внешняя петля нечетная.Какова сложность этой двойной петли

Если бы проверка была только с N (а не N * N), то i, увеличивая умножение на 3 каждый раз, означало бы n/3 итерации N для внешнего цикла?

Но проверка с N * N или N^2, так что подразумевает будет расти

N^2/3 ??? (n squared divided by 3) Is that correct?

Если я поиграться с различными значениями N, скажем, в два раза каждый раз, цикл I (сам по себе) не растет много. как логарифмический рост). Как я могу выразить это математически?

Тогда как вы думаете о внутренней петле? Если он каждый раз увеличивается до i, как я могу выразить это математически? Как я могу связать внутренний цикл с N?

Я хотел бы: a) выразить математическое выражение «сложность» в терминах N. Затем, следующий шаг, б) состоит в использовании обозначения большого О.

Смутно этим. Любая помощь приветствуется.

источник

2014-02-01 Angus Comber

Я думаю, что внешний цикл выполняется log3(N*N) раз, потому что каждый раз, когда вы умножаете на 3, у вас есть 1, 3, 9 ... и он принимает логарифмическую базу 3 из N * N исполнений, чтобы достичь N * N.

Внутренний цикл выполнен не более N * N раз, поэтому все становится log3(N*N)*N*N.

источник

2014-02-01 16:44:43 fede1024

Вы не всегда можете приблизиться к общей стоимости внутреннего цикла, предполагая наихудший случай (здесь N * N) каждый раз, когда он запускается. Обычно это логически некорректно, но создает правильную сложность, но здесь она дает завышенную оценку. –

Инструкция по приращению выполняется (приблизительно) N * N + N * N/3 + N * N/9 + ... = N * N (1 + 1/3 + 1/9 + ...) = N * N * 3/2 раза (с использованием формулы для геометрического ряда). Таким образом, общая продолжительность выполнения кода равна O (N * N) (при условии, что все арифметические функции O (1) и C int могут представлять собой сколь угодно большие числа).

источник

2014-02-01 17:02:16

fede1024 прав, что внешний цикл является log3 (n^2).

Внутренний цикл немного сложнее, но решение суммирования 1 + 8 + 27 .. (sum x^3) дает вам решение. Вы можете вычислить сумму кубов, используя набор линейных уравнений, учитывая, что сумма равна полиному степени 3 и выражается как ay^3 + на^2 + cy. Или Google это и найти, что сумма кубов равна (n (n + 1)/2)^2 (может включать полное решение, если вы хотите).

Тогда вся сложность была бы log3 (n^2) * (n (n + 1)/2)^2. Обозначение Big O, log3 (n^2) * n^3. Может быть, неправильно.

источник

2014-02-01 17:20:41

Какова сложность этой двойной петли

ответ

Смежные вопросы