Подробный большой вопрос

Question

Итак, я немного смущен этим вопросом на моей домашней работе.

 for ( int j = 0; j < 2*n; j++){
for ( int k = 0; k < n * n * n; k += 3)
sum++;
}

Итак, я пришел к такому выводу после небольшого замешательства

для (1, 2n, n)
для (1/3 (1, 3n, 1)
У меня оно равно 1/3, потому что оно увеличивается на 3. Я просто не уверен, прав ли я, мы только что познакомились с этим, поэтому я как-то потерян.

Answer 1

Я не совсем уверен, что понимаю, о чем вы спрашиваете ... Предполагая, что вопрос в том, какой будет запись Big-O для этого вложенного цикла (и предполагая, что операция сложения является базовой операцией) *

• Внешний цикл выполняется 2n раз
• Внутренний цикл выполняется n^3/3 раз за каждую итерацию внешнего цикла

Это означает, что внутренний оператор выполняется 2n * n^3/3 = (2/3)*n^4. Для обозначения Big O мы игнорируем константы, поэтому этот вложенный цикл равен O (n ^ 4).