Какова сложность алгоритма этой суммы?

#include <stdio.h> 

int main() { 
    int N = 8; /* for example */ 
    int sum = 0; 
    for (int i = 1; i <= N; i++) 
     for (int j = 1; j <= i*i; j++) 
      sum++; 

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

для каждого значения n (i переменной), j значений будет n^2. Таким образом, сложность будет равна n. n^2 = n^3. Это верно?Какова сложность алгоритма этой суммы?

Если проблема становится:

#include <stdio.h> 

int main() { 
    int N = 8; /* for example */ 
    int sum = 0; 
    for (int i = 1; i <= N; i++) 
     for (int j = 1; j <= i*i; j++) 
      for (int k = 1; k <= j*j; k++) 
       sum++; 

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

Тогда вы используете существующий п^3. n^2 = n^5? Это верно?

источник

2014-02-01 Angus Comber

O (N^7). N * (N^2) * ((N^2)^2) – wacky6

У нас есть 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 для третьего цикла.

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

источник

2014-02-01 14:36:46 abiessu

Вы можете улучшить свой ответ, добавив больше в третью часть цикла - почему n^4 –

Для i = 1 внутреннего контура работает 1^1 раз, для i = 2 внутреннего цикла выполняется 2^2 раз .... и 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).

источник

2014-02-01 14:30:25 haccks

Можете ли вы объяснить, как вы это вывели –

Почему голос? – haccks

Вы сами объяснили сумму, а не алгоритм, используемый для ее вычисления. –

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

Во втором примере есть дополнительный цикл O(N^4) (петля до 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.

источник

2014-02-01 14:31:32 abligh

Любая вероятность того, что 'j^2' заставляет цикл O (n^4), что делает общий O (n^7)? – abiessu

Действительно - я неправильно понял это. – abligh

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

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

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

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

источник

2014-02-01 14:38:14 Sorin

Третий цикл на самом деле самый сложный бит - я получил это неправильно. –

Рассмотрим число раз все петли будут именоваться.

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; 
}

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

источник

2014-02-01 14:49:14 vishram0709

Неправильный способ решения этой проблемы (хотя обычно и часто дает правильный ответ) заключается в том, чтобы приблизить среднее число итераций внутреннего цикла в худшем случае. Здесь внутренняя петля в худшем случае 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. Установка п = я^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))

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

T = Theta(N^7)

источник

2014-02-01 17:43:37

Какова сложность алгоритма этой суммы?

ответ

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