время следующего цикла

Question

Я пытаюсь найти время выполнения следующего цикла Запуск:

int m=1; 
for(i=1;i<=k;i++) 
{ 
    for(j=1;j<=A[i];j++) 
    { 
     B[m]=i; 
     m++; 
    } 
} 

Здесь A представляет собой массив целых чисел, сохраняя в нем, и сумма этих чисел равна п. Например, если длина A равна 2, а A [1] = 2 и a [2] = 4, то внутренний цикл будет работать 6 раз.

Итак, в моих лекционных заметках говорится, что время работы этой части кода равно O (n + k). Но предположим, например, что k равно 5, а длина массива A равна 4, а A [1] = 3, A [2] = 0, A [3] = 0, A [4] = 9, A [ 5] = 0. Итак, n = 12. Затем для k = 1 внутренний цикл будет повторяться 2 раза, при k = 2 внешний цикл будет повторяться 1 раз, при k = 3 внешний цикл будет работать 1 раз, при k = 4 внутренний цикл будет выполняться 9 раз и при k = 5 внешний цикл будет работать 1 раз, поэтому общее число итераций равно 14. Это больше, чем k и n, а время работы не равно O (n), ни O (k). Что я здесь делаю неправильно?

Спасибо

Answer 1

Внешний контур будет перебирать к раз, потому что вы делаете

for(i=1;i<=k;i++)

Общее количество итераций внутреннего цикла является

sum (A[i]) для i = 1...k, который вы знаете = n.

Это дает n + k итераций. Так как материал внутри внутреннего цикла работает в постоянное время, сложность O(n + k).

EDIT:

Что мы имеем в виду, когда мы говорим, что неотрицательная функция f(n) является O(g(n))?

Ответ:

Посмотрите соответствующий StackOverflow вопрос

What is a plain English explanation of "Big O" notation?

EDIT2:

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

Позвольте f(n) быть неотрицательной функцией. Затем мы говорим f(n) = O(g(n)) (читай «е (п) о большое от г (п)»), если существуют положительные константы c и n0 таким образом, что

f(n) <= c g(n)

для всех n >= n0,

Answer 2

Если я не хватает чего-то исходную функцию можно упростить:

for(i=1;i<=k;i++) { 
    for(j=1;j<=A[i];j++) { 
    ... 
    } 
} 

В худшем случае, сумма (A [I]) = п

Это мне кажется эта функция должна пробег не хуже k * n и для больших k, k = n, поэтому O (n^2) должен быть ответом.

я думаю умножение в порядке, не дополнение.

Пусть цикл пробегает 3 раза и цикл B работает в 2 раза для каждого прогона А. Это равняется 6 пробегов, а не 5. Так 3 * 2, а не 3 + 2

Edit:

Доказательство:

F (п) = к * п

Пусть г (п) = п^2

F (п) = С < XG (п)

для C = 1, N0 = макс (А [I])