Оценка порядка роста времени работы с alogrithm

Question

Я следую онлайн курс, и я не могу хорошо понять, как оценить порядок роста алгоритма здесь приведен пример

Каков порядок роста наихудшего времени работы следующего фрагмента кода как функции N?

Int sum = 0; 
    For (int i = 1; i <= 4*N; i = i*4) 
    for (int j = 0; j < i; j++) 
    sum++; 

Может кто-нибудь объяснить мне, как получить его

Answer 1

Просто подсчитать, сколько раз оператор sum++; выполняется.

= 1 + 4 + 16 + 64 ... + 4 * N

Это геометрическая прогрессия с общим коэффициентом 4. Если число слагаемых в этой серии к, то

4^k = 4*N. 

Sum of series = (4^k - 1)(4-1) = (4*N - 1)/3. 

В порядке роста мы пренебрегаем постоянными факторами.

Следовательно, сложность O (N).

Answer 2

Это довольно просто:

Есть log(N) + 1 итерации внешнего цикла (логарифм основание 4).

Позвольте x быть номером итерации внешнего цикла. Внутренняя петля выполняет итерацию 4^x раз.

Таким образом, общее время выполнения является Sum(4^x) for x in [0..c], где c является log(N) Это geometric series, и это сумма легко вычисляется по следующей формуле из вики:

Sum(4^x) for x in [1..c] = (1 - 4^c)/(1 - 4) = (4^c)/3. Теперь c является log (N) в базе 4, следовательно 4^c = N. Таким образом, общий ответ - это N с некоторыми постоянными факторами.

Answer 3

Находя порядок алгоритма мы находим общее число шагов, алгоритм проходит через

Здесь внутренний цикл имеет число шагов, равные текущее значение I.

Пусть я прохожу через значение i1, i2, i3 ... в

Таким образом, общее число шагов в алгоритме является - >> i1 + i2 + i3 + ... в.

Здесь значения i1, i2, i3 ... in составляют 1,4,64 ... 4N; который является GP с первым членом = a = 1 и последним членом , равным 4N. Таким образом, сложность этого алгоритма представляет собой сумму всех членов этого GP.

SUM = 1 + 4 + 64 + ... 4N

сумма GP с п точки а, ар, ар^2 ... ар^(п-1) = а ((г^п) -1)/(r-1) = a (L * r-1)/(r-1) где L = последний член;

Здесь в нашем случае сумма = 1 * ((4 * 4N) -1)/3 , что примерно в 1,33 раза превышает последний член L SUM = 1.33 * 4N , который является линейным порядком N

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