Временная сложность цикла

Question

Мне нужно вычислить временную сложность следующего цикла:

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

 statements;

} 

Предполагая, что n = 10, Is i < n; оператор управления будет выполняться в течение n времени и оператор i++; для n-1раз?И зная, что оператор i = 1; будет выполняться в течение единицы времени.

Вычисление общей сложности времени трех операторов в цикле for дает 1 + n + n-1 = 2n и цикл сего утверждения дают 2n + n-1 = 3n-1 = O (n).

Верны ли мои расчеты в этом отношении?

Answer 1

Да, ваши расчеты верны, цикл for, подобный такому, будет иметь обозначение O (n).

Аналогично, вы можете сделать вычисление, подобное такому:

for(int i = 0; i <n*2; i++){
//calculations
}

в этомв этом случае цикл for будет иметь большую запись O (n ^ 2) (вы понимаете):

Этот цикл занимает время O (n ^ 2);математическая функция = n ^ n Таким образом, вы можете рассчитать, сколько времени понадобится вашему циклу для n 10, или 100, или 1000

. Таким образом, вы можете строить графики для циклов и т. д.

, как упоминалось в DAleв комментариях на обозначение большой O не влияют вычисления внутри цикла, только сам цикл.