Мне дали домашнее задание с Big O. Я застрял с вложенными циклами for, которые зависят от предыдущего цикла. Вот измененная версия моего домашнего задания, так как я действительно хочу это понять:
sum = 0;
for (i = 0; i < n; i++
for (j = 0; j < i; j++)
sum++;
Часть, которая отталкивает меня, это j < i
часть. Кажется, что это будет работать почти как факториал, но с дополнением. Любые намеки будут очень благодарны.
Ответы:
Итак, позвольте мне прояснить несколько вещей, вас интересует нотация big-O - это означает верхнюю границу . Другими словами, можно считать больше шагов, чем вы на самом деле. В частности, вы можете изменить алгоритм на
Таким образом , у вас есть два вложенных цикла, каждый цикл выполняется раз, что дает вам верхнюю границу изN O ( n2)
Конечно, вы хотели бы получить хорошую оценку для верхней границы. Итак, для завершения мы хотим определить нижнюю границу. Это означает, что можно считать меньше шагов. Так что рассмотрим модификацию
Здесь мы выполняем только некоторые из циклов-итераций. Снова у нас есть два вложенных цикла , но на этот раз мы имеем итерации на цикл, что показывает, что у нас есть по крайней мере дополнения. В этом случае мы обозначим эту асимптотическую нижнюю оценку через . Поскольку нижняя и верхняя границы совпадают, мы можем даже сказать, что является жесткой асимптотической границей, и мы пишем .н 2 / 4 Ω ( п 2 ) п 2 Θ ( п 2 )н / 2 N2/ 4 Ω ( n2) N2 Θ ( н2)
Если вы хотите узнать больше, прочитайте здесь .
источник
Давайте проследим это:
0<0 == false
).Таким образом, этот алгоритм будет увеличивать
sum
следующее количество раз:источник
давайте посмотрим, смогу ли я объяснить это ...
Так что, если внутренний цикл был J
Теперь для первой итерации вы выполняете n- (n-1) раз по внутреннему циклу. во второй раз вы делаете n- (n-2) раз по внутреннему циклу. В N-й раз вы делаете n- (nn) раз, то есть n раз.
если вы усредните число раз, которое вы пройдете по внутреннему циклу, это будет n / 2 раза.
Таким образом, вы можете сказать, что это O (n * n / 2) = O (n ^ 2/2) = O (n ^ 2)
Имеет ли это смысл?
источник
j < i
часть была на самом делеj < i^2
, полученная O для этой части была бы n ^ 2/2?