Найти время в обозначении Big O

Question

1)  for (i = 1; i < n; i++) {                         > n
2)      SmallPos = i;                                 > n-1
3)      Smallest = Array[SmallPos];                   > n-1
4)      for (j = i+1; j <= n; j++)                    >  n*(n+1 -i-1)??
5)          if (Array[j] < Smallest) {                > n*(n+1 -i-1 +1)  ?? 
6)              SmallPos = j;                         > n*(n+1 -i-1 +1)  ?? 
7)              Smallest  = Array[SmallPos]           > n*(n+1 -i-1 +1)  ??     
            }                                         
8)      Array[SmallPos] = Array[i];                   > n-1
   9)                Array[i] = Smallest;             > n-1
                                     }

я знаю, что большая буква O - это n ^ 2 (мой плохой, это не n ^ 3)

Я не уверен, что между строкой 4-7 кто-нибудь хочет помочь? я не уверен, как получить выход для второго цикла, так как j = i +1, как я меняется, то же самое делает j

также для строки 4 ответ должен быть n (n + 1) / 2 -1, я хочу знать, почему, поскольку я никогда не смогу получить это

я на самом деле не решаю для больших O, я пытаюсь сделать шаги, которые достигают больших O, поскольку константы и переменные выделяются в больших O-нотациях.

Answer 1

Я бы сказал, что это O (n ^ 2) (хотя, как указывает Фред выше, O (n ^ 2) - это подмножество O (n ^ 3), поэтому нет ничего плохого в том, что это O (n ^ 3)).

Обратите внимание, что обычно нет необходимости вычислять количество выполнений каждой отдельной строки ; поскольку нотация Big-O отбрасывает термы младших разрядов, достаточно сосредоточиться только на наиболее исполняемом разделе (который обычно находится внутри самого внутреннего цикла).

Так что в вашем случае ни один из циклов не зависит от значений в Array, поэтому мы можем спокойно проигнорировать все это. Внутренний цикл запускается (n-1) + (n-2) + (n-3) + ... раз; это арифметический ряд , и поэтому имеет член в n ^ 2 .

Answer 2

Это алгоритм, данный вам или тот, который вы написали?

Я думаю, что ваши индексы цикла неверны.

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

должно быть либо

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

или

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

в зависимости от того, начинаются ли индексы вашего массива с 0 или 1 (это 0 в C и Java).

Предполагается, что мы исправим его следующим образом:

for (i = 0; i < n; i++) {
    SmallPos = i;
    Smallest = Array[SmallPos];
    for (j = i+1; j < n; j++)
        if (Array[j] < Smallest) {
            SmallPos = j;
            Smallest  = Array[SmallPos];
        }                                         
    Array[SmallPos] = Array[i];
    Array[i] = Smallest;
}

Тогда я думаю, что сложность составляет n ² -3 / 2n = O (n ² ).

Вот как ...

Самая дорогостоящая операция в самом внутреннем цикле (мой лектор назвал это «базовой операцией») - это сравнение ключей в строке 5. Это делается один раз за цикл.

Итак, теперь вы создаете суммирование:

Sum(i=0 to n-1) of Sum(j=i+1 to n-1) of 1.

Теперь разверните самую внутреннюю (самую правую) сумму, чтобы получить:

Sum(i=0 to n-1) of (n-1)-(i+1)+1

, а затем:

Sum(i=0 to n-1) of n-i-1

, а затем:

[Sum(i=0 to n-1) of n] - [Sum(i=0 to n-1) of i] - [Sum (i=0 to n-1) of 1]

и затем:

n[Sum(i=0 to n-1) of 1] - [(n-1)(n)/2] - [(n-1)-0+1]

, а затем:

n[(n-1)-0+1] - [(n^2-n)/2] - [n]

, а затем:

n^2 - [(n^2/2) - n/2] - n

равно:

1/2n^2 - 1/2n

находится в:

O(n^2)

---

Если вы спрашиваете, почему это не O (n ³ ) ...

Рассмотрите вариантыт случае.if (Array[j] < Smallest) будет истинно в большинстве случаев, если Array отсортировано в обратном порядке.

Тогда у вас есть внутренний цикл, который выглядит следующим образом:

    Array[j] < Smallest;
    SmallPos = j;
    Smallest  = Array[SmallPos];

Теперь у нас есть константатри операции для каждого внутреннего for (j...) цикла.

И O (3) = O (1).

Так что на самом деле, i и j определяют, сколько работы мыделать.Ничто во внутреннем цикле if ничего не меняет.

Вы можете думать об этом, как вы должны считать только циклы while и for.

---

Почему for (j = i+1; j <= n; j++) равно n (п + 1) / 2.Это называется арифметической серией.

Вы делаете n-1 проходов цикла for (j...), когда i==0, n-2 проходит, когда i==1, n-3 и т. Д., До 0.

Итак, сумма теперь равна

n-1 + n-2 + n-3 + ... 3 + 2 + 1

, теперь вы суммируете пары извне, переписывая это как:

n-1+1 + n-2+2 + n-3+3 + ...

равно:

n + n + n + ...

и таких пар n / 2, поэтому у вас есть:

n*(n/2)

Answer 3

Это O (n ^ 2).

Для каждой из n итераций внешнего цикла у вас есть n итераций во внутреннем цикле.

Answer 4

Два for() цикла, внешний цикл от 1 до n, внутренний цикл проходит от 1..n до n.Это делает его O (n ^ 2).

Если вы «вытяните это», оно будет треугольным , а не прямоугольным, поэтому O (n ^ 2), тогда как true, скрывает тот факт, что член с постоянным множителем меньше, чем если бы внутренний цикл также повторялся от 1 до n.