Найти сложность вычислений вложенных циклов

Question

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

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

Это n-0 = n назначение, и это O (g (n)) вправо?

Хорошо так что знаю, если я хочу, чтобы получить количество заданий и O (г (п)) в этих вопросах:

sum = 0; 
for (i = 1 ; i < n * n ; j ++) 
{ 
    for (j = 1 ; j <= n; j ++) 
    { 
     sum += j; 
    } 
} 

что я сделал, сумма = 0 является одним присваивание и внешний контур равен п^2 - 1 задание и внутренний цикл N-1 задание и, наконец, сумма 1 назначение

Таким образом, количество назначений является 2+ (п^3 + 1), что дает O (g (n^3))

В этом вложенный цикл:

sum = 0; 
for (i = 1 ; i <= n; i ++) 
{ 
    for (j = 1 ; j <= 100 ; j++) 
    { 
     for (k = 1 ; k <= n ; k ++) 
     { 
      sum += k; 
     } 
    } 
} 

Что я сделал, сумма = 0 равно 1 Назначение тогда первый цикл 1-н заданий второго цикл 99 последнего цикл 1-н , а затем сумма = 2

Так что я получил 3 + (1 + п^2) задания, которые дают мне O (г (п^2))

существует ничего плохого с тем, что я только что сделал?

Answer 1

Ваши расчеты верны. Единственное, что может быть - иногда важно, является ли это O (g (n^2)) или O (g (* n^2)). Множитель не очень важен для широкомасштабных значений N, но в небольших масштабах - постоянный коэффициент в 99 раз больше, чем итерации (если они не оптимизированы компилятором).