вывод алгоритма сложности

Question

Освежающие на сложность алгоритма, я смотрел на этот пример:

int x = 0; 
    for (int j = 1; j <= n; j++) 
     for (int k = 1; k < 3*j; k++) 
      x = x + j; 

Я знаю, что петли заканчивается время O (N^2). Я полагаю, что внутренний цикл выполняется 3 * n раз (3 (1 + 2 + ... n)), а внешний цикл выполняется n раз. Итак, O (3n * n) = O (3n^2) = O (n^2).

Однако источник, на который я смотрю, расширяет выполнение внутреннего цикла до: 3(1+2+3+...+n) = 3n^2/2 + 3n/2. Может ли кто-нибудь объяснить время исполнения 3n^2/2 + 3n/2?

Answer 1

Для каждого J вы должны выполнить итерации J * 3 внутреннего цикла, так что команда x=x+j будет выполнена, наконец, n * 3 * (1 + 2 + 3 ... + n) раз, сумма Arithmetic progression равна n * (п + 1)/2, так что вы команда будет выполняться:

3 * n * (n+1)/2 which is equals to (3*n^2)/2 + (3*n)/2

но большая O не то, сколько итераций будут, речь идет о асимптотических мерах, поэтому в выражении 3 * N * (n + 1)/2 необходимо удалить consts (установить их все в 0 или 1), поэтому мы имеем 1 * n * (n + 0)/1 = n^2

Небольшое обновление о большом O calculatio п для этого случая: сделать большой вывод из 3n (п + 1)/2, для большого O вы можете себе представить, чем N равно бесконечности, так:

infinity + 1 = infinity 
3*infinity = infinity 
infinity/2 = infinity 
infinity*infinity = infinity^2 

так что вы после этого у вас есть N^2

Answer 2

Big O Обозначение дает верхнюю оценку асимптотического времени работы алгоритма. Он не учитывает члены нижнего порядка или постоянные факторы. Поэтому O (10n) и O (1000n + 4n + 56) все еще O (n).

Что вы делаете, это попытка подсчитать количество операций в вашем алгоритме. Однако Big O ничего не говорит о точном количестве операций. Он просто дает вам верхнюю границу времени наихудшего случая, которое может иметь место при неблагоприятном вводе.

Answer 3

Сумма целых чисел от 1 до m равна m * (m + 1)/2. В данной задаче j идет от 1 до n, а k переходит от 1 до 3 * j. Таким образом, внутренний цикл на k выполняется 3 * (1 + 2 + 3 + 4 + 5 + ... + n) раз, причем каждый член в этой серии представляет одно значение j. Это дает 3n (n + 1)/2. Если вы расширите это, вы получите 3n^2/2 + 3n/2. Тем не менее, все дело в O (n^2). Вам все равно, будет ли ваше время выполнения как квадратично, так и линейно, так как линейка затухает квадратичной.

Answer 4

Точная точность вашего алгоритма можно найти с помощью Sigma обозначения, как это:

Это было эмпирически подтверждено.