Вычислить Время воспроизведения алгоритма с использованием Big-O Notation

Question

здесь вопроса:

for(i=1;i<=n,i++){ 

     for(j=2*i;j<=n,j++){ 

     puts("hello"): 
     } 
} 

Вот мое решение: внешний контур имеет 1+n+1+n время работы и вторые для петель имеют n*(1+n/2+1+n/2) время работы, и третий оператор имеет n*n/2 время выполнения. второй и третий статуты очень смутили меня, я не знаю, правильны ли мои вычисления или нет, любые разъяснения будут оценены, спасибо в advnace.

Answer 1

Поскольку вам разрешено использовать нотацию Big-O, вам не нужно записывать все детали.

Пусть T (n) - это время работы вашего алгоритма, когда размер ввода равен n.

Прежде всего, puts("hello") является O (1). Как вы можете ясно видеть из кода, puts("hello") был выполнен менее n^2 раз. Также отметим, что, если внешний контур был изменен (уменьшен) до

for (i = 0; i < n/4; ++i)

внутренний цикл будет выполнен, по крайней мере, п/2 раза для каждого i, это означает, что оператор puts("hello") будет выполнен, по крайней мере, n/4 * n/2 = n^2/8.

Теперь, как обсуждалось выше, у нас есть n^2/8 <= T(n) <= n^2. Поэтому T (n) = O (n^2) (анализ плотный, это означает, что мы имеем T(n) = \Theta(n^2)).

Если у вас есть проблемы с пониманием концепции Big-O и Тета, Вы можете обратиться к этому видео: https://youtu.be/6Ol2JbwoJp0