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

Question

Я не хочу ответа, я хочу знать, как это сделать. Эффективность алгоритма doIt может быть выражена как O (f (n)) = n^3. Вычислите эффективность следующего программного сегмента точно и с помощью обозначения большого О.

for (i=1; i<=n+1; i++) 
    for (j=1; j<n, j++) 
     doIt (...) 

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

ALG (M, N, K, L) = 3n^3
М = ​​1n, N = 1 2n, K = 1n L = 1n^2
п^2 * п * 2n * n * 3n^3 = 6n^8 = O (n^8)

Итак, я предполагаю, что это вложенная петля, а наивысшее значение, равное n^3. Или кто-нибудь может написать код для примера, чтобы я мог понять его лучше?

Answer 1

for (i=1; i<=n+1; i++) 
for (j=1; j<n, j++) 
    doIt (...) 

Как вы упомянули, наихудшей сложностью является O (n^3).

Таким образом, в случае вложенных циклов основное внимание следует сосредоточить на том, что первая петля направляет внутренний цикл, то есть внутренний цикл, как правило, не работает. итераций (не обязательно всегда), чем внешний цикл!

Как и в вашем вопросе, внешний цикл работает для i = 1 до i = n + 1 --- n+1 times. Аналогично, внутренний цикл работает для j = 1 до j < n --- n-1 итераций на каждой итерации внешнего контура. Кроме того, функция doIt() находится внутри внутреннего цикла со сложностью порядка O (n^3).

Далее, n + 1 итераций имеют порядок O (n) в соответствии с наихудшей сложностью.

Аналогично, итерации n-1 имеют порядок O (n) в соответствии с наихудшей сложностью!

Таким образом, общий наихудший сложность = O(n)*O(n)*O(n^3) = O(n^5) ...

Если вы не в состоянии понять, пожалуйста, оставьте комментарий ниже!