Я начинаю изучать основы анализа сложности. В качестве практики я хочу использовать «количество примитивных операций», чтобы найти временную сложность следующего фрагмента кода:
int calc(int n)
{
int i,j,res=0;
for(i=0;i<n;i++)
{
for(j=0;j<100;j++)
{
res=res+j;
}
}
return res;
}
Будет ли правильным следующий счет:
+ Три объявления и одно присвоение: 4
+ Для цикла, который повторяется n раз (назначение, сравнение, арифметическое сложение): 2 (n + 1) + n
+ Вложенный цикл For, который повторяется 100 раз (он запускается n раз): n (2 (101) + 100)
+ Арифметическое сложение, затем назначение: 2 (100)
+ Возврат: 1
Всего: 4 + 2 (n + 1) + n + n (202 + 100) + 200 + 1 = 305n + 207