В чем сложность этого алгоритма суммирования?

Ответ 1

Мы имеем i и j < i*i и k < j*j, которые x^1 * x^2 * (x^2)^2 = x^3 * x^4 = x^7 по моему счету.

В частности, поскольку 1 < i < N, мы имеем O (N) для цикла i. Так как 1 < j <= i^2 <= N^2, для второго цикла O (n ^ 2). Расширяя логику, мы имеем 1 < k <= j^2 <= (i^2)^2 <= N^4 для третьего цикла.

Внутренние к Outer циклам мы выполняем до N^4 раз для каждого цикла j и до N^2 раз для каждого цикла i и до N раз в цикле i, делая общее порядка порядка N^4 * N^2 * N = N^7= O(N^7).

Ответ 2

Для i = 1 внутренний цикл запускает 1^1 раз, для внутреннего цикла i = 2 выполняется 2^2 times.... и для i = N внутренний цикл запускает N^N раз. Его сложность (1^1 + 2^2 + 3^3 + ...... + N^N) порядка O(N^3).

Во втором случае для i = N первая внутренняя петля выполняет итерацию N^N раз, и, следовательно, вторая внутренняя петля (самая внутренняя) будет повторять до N * (N^N) * (N^N) раз. Следовательно, сложность имеет порядок N * N^2 * N^4, т.е. O(N^7).

Ответ 3

Я думаю, что на самом деле сложность - это O (n ^ 7).

Первый цикл выполняет N шагов. Второй цикл выполняет N ^ 2 шага.

В третьем цикле j * j может достигать N ^ 4, поэтому имеет сложность O (N ^ 4).

В целом, N * N ^ 2 * N ^ 4 = O (N ^ 7)

Ответ 4

Да. В первом примере цикл i запускает N раз, а внутренний цикл j настраивает i*i раз, что составляет O(N^2). Итак, все это O(N^3).

Во втором примере существует дополнительный цикл O(N^4) (loop to j*j), поэтому он равен O(N^5).

Для более формального доказательства выясните, сколько раз sum++ выполняется в терминах N, и посмотрите на самый высокий полиномиальный порядок N. В первом примере это будет a(N^3)+b(N^2)+c(N)+d (для некоторых значений a, b, c и d), поэтому ответ равен 3.

NB: отредактированный пример 2, чтобы сказать это O (N ^ 4): неверно прочитать i*i для j*j.

Ответ 5

Рассмотрим количество вызовов всех циклов.

int main() {
int N = 8;  /* for example */
int sum = 0;
for (int i = 1; i <= N; i++)   /* Called N times */
    for (int j = 1; j <= i*i; j++) /* Called N*N times for i=0..N times */
        for (int k = 1; k <= j*j; k++) /* Called N^2*N^2 times for j=0..N^2 times and i=0..N times */ 
            sum++;

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

Таким образом, выражение sum ++ называется O (N ^ 4) * O (N ^ 2) * O (N) times = O (N ^ 7), и это общая сложность программы.

Ответ 6

Неправильный способ решить эту проблему (хотя часто и часто дает правильный ответ) заключается в том, чтобы приблизить среднее число итераций внутреннего цикла в худшем случае. Здесь внутренняя петля в худшем случае O (N ^ 4), средняя петля петлей в худшем случае O (N ^ 2) раз, а внешний цикл петли O (N) раз, давая (случайно) решение O ( N ^ 7), умножив их вместе.

Правильный путь - это работать изнутри, пытаясь быть явным в отношении того, что аппроксимируется.

Общее число итераций, Т, инструкции приращения совпадает с вашим кодом. Просто напишите:

T = sum(i=1..N)sum(j=1..i^2)sum(k=1..j^2)1.

Самая внутренняя сумма равна j ^ 2, давая:

T = sum(i=1..N)sum(j=1..i^2)j^2

Сумма, проиндексированная j, представляет собой сумму квадратов последовательных целых чисел. Мы можем вычислить, что именно: sum (j = 1..n) j ^ 2 есть n * (n + 1) * (2n + 1)/6. Полагая n = я ^ 2, получим

T = sum(i=1..N)i^2*(i^2+1)*(2i^2+1)/6

Мы могли бы продолжать вычислять точный ответ, используя формулу для сумм 6-й, 4-й и 2-й степеней последовательных целых чисел, но это боль, и для сложности мы заботимся только о наивысшей степени i. Таким образом, мы можем приблизиться.

T = sum(i=1..N)(i^6/3 + o(i^5))

Теперь мы можем использовать эту сумму (i = 1..N) я ^ p = Theta (N ^ {p + 1}), чтобы получить окончательный результат:

T = Theta(N^7)