Просто путаница ....
Часть примера кода на C ++ выглядит следующим образом
Я просто заново отредактировал весь пост. Извините за путаницу
int i, j;
i = 0; // c1
j = 0; // c2
while (i < n) // (n+1)c3
{
i++; // n c4
while ( j < i) // (2+3+....+n+(n+1)c5
{
j++; // (1+2+...+n)c6
}
j = 0; // c7
}
Очевидно, что c1, c2 и c7 постоянны. Мы не заинтересованы в них, и они не имеют большого значения для определения времени работы.
Чего я не понимаю, так это c5 и c6.
Почему это 2 + 3 + 4 ... + n + (n + 1) для c5? Почему он начинается с 2, а не с 1 + 2 + 3 ... + (n + 1) ???
Обратите внимание, что мы можем переписать C5 -> (n * (n-1) / 2) + n
Для c6 эта комбинация может быть переписана как n * (n-1) / 2
Первоначально я думал, что C6 - это n, потому что C6 зависит от двух условий: первого цикла while и второго цикла while. Но поскольку j всегда будет возвращаться к 0, мы действительно зависим от первого цикла while. Поскольку n
n = 3
0 <3, 1, 0 <1, 1, 0 </p>
1 <3, 2, 0 <1, 1, 0 </p>
2 <3, 3, 0 <1, 1, 0 </p>
3 <3. </p>
Может кто-нибудь, пожалуйста, подробно объяснить, как определяются C5 и C6?
Извините, если эта проблема звучит глупо для экспертов
Спасибо!