Big O: вложенный в петлю с зависимостью

9

Мне дали домашнее задание с Big O. Я застрял с вложенными циклами for, которые зависят от предыдущего цикла. Вот измененная версия моего домашнего задания, так как я действительно хочу это понять:

sum = 0;
for (i = 0; i < n; i++ 
    for (j = 0; j < i; j++) 
        sum++;

Часть, которая отталкивает меня, это j < iчасть. Кажется, что это будет работать почти как факториал, но с дополнением. Любые намеки будут очень благодарны.

Рафаэль
источник
Хорошее объяснение здесь
saadtaame

Ответы:

10

Итак, позвольте мне прояснить несколько вещей, вас интересует нотация big-O - это означает верхнюю границу . Другими словами, можно считать больше шагов, чем вы на самом деле. В частности, вы можете изменить алгоритм на

 ...
    for (j = 0; j < n; j++) 
 ...

Таким образом , у вас есть два вложенных цикла, каждый цикл выполняется раз, что дает вам верхнюю границу изnO(n2)

Конечно, вы хотели бы получить хорошую оценку для верхней границы. Итак, для завершения мы хотим определить нижнюю границу. Это означает, что можно считать меньше шагов. Так что рассмотрим модификацию

for (i = n/2; i < n; i++)
    for (j = 0; j < n/2; j++) 
        sum++;

Здесь мы выполняем только некоторые из циклов-итераций. Снова у нас есть два вложенных цикла , но на этот раз мы имеем итерации на цикл, что показывает, что у нас есть по крайней мере дополнения. В этом случае мы обозначим эту асимптотическую нижнюю оценку через . Поскольку нижняя и верхняя границы совпадают, мы можем даже сказать, что является жесткой асимптотической границей, и мы пишем .н 2 / 4 Ω ( п 2 ) п 2 Θ ( п 2 )n/2n2/4Ω(n2)n2Θ(n2)

Если вы хотите узнать больше, прочитайте здесь .

A.Schulz
источник
6
sum = 0;
for (i = 0; i < n; i++)
    for (j = 0; j < i; j++) 
        sum++;

Давайте проследим это:

  • Когда я = 0, внутренний цикл не будет работать вообще ( 0<0 == false).
  • Когда i = 1, внутренний цикл будет запущен один раз (для j == 0).
  • Когда я = 2, внутренний цикл будет выполняться дважды. (для j == 0 и j == 1).

Таким образом, этот алгоритм будет увеличивать sumследующее количество раз:

x=1nx1=0+1+2+3+4...+n1=n(n1)2

nn2n2n2θ(n2)O(n2) and Ω(n2)

Keiths
источник
3

давайте посмотрим, смогу ли я объяснить это ...

Так что, если внутренний цикл был 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?
Прежде всего отметим, что O (n ^ 2/2) = O (n ^ 2). Теперь, если вы измените его на j <i ^ 2, то вы делаете (n- (n-1)) ^ 2 на первой итерации и n ^ 2 на последней итерации. Я не помню, что обозначение big-O было бы для внутреннего цикла. O (n ^ 2) - свободная верхняя граница. Таким образом, свободная верхняя граница для всего этого будет O (n ^ 3), но этот внутренний цикл меньше O (n ^ 2). Имеет ли это смысл?