вложенного цикла анализ сложности Продолжительность

Question

я получил алгоритм вставки рода ниже, она включает в себя вложенный цикл:

public InsertionSort(AnyType [] a){ 
    int m; 
    for(int n = 1; n < a.length; n++){ 
     AnyType temp = a[n]; 
     for(m = n; m > 0 && tmp.compareTo(a[ m - 1]) <= 0; m--) 
      a[ m ] = a[ m - 1 ]; 
     a[ m ] = temp; 
    } 
} 

Первый цикл имеет время работы O (N), а второй O (N^2), поэтому общее время работы в вложенном цикле должно быть O (N * N^2 = N^3), верно? Но я знаю, что худший случай должен быть O (N^2) в сортировке вставки, однако мой учитель изменил этот сегмент кода, который книга немного, заменив [m - 1]) < = 0, вместо использования a [m - 1]) < 0. Так что я смущен, что, как я понял, дело хуже худшего. Кто-нибудь помогает? Заранее спасибо.

Answer 1

вторая O (N^2)

Это неправильно. Смотри как.

Учитывая a.length = N, TC должен быть O(N^2).

Поскольку (1 + 2 + 3 + ... + N-1) = N(N-1)/2 = O(N^2)

Внутренний цикл выполняется один раз больше, чем предыдущий раз.

[1, 1] 
[2, 1] 
[3, 1] 
... 
[N-1, 1] 

Answer 2

для (Int N = 1, N < a.length, п ++) {

В этой строке выше, вы собираетесь через массив п - 1 раз (с вы начиная с индекса всего 1 пути к a.length -1), таким образом, O (N)

для (т = п, т> 0 & & tmp.compareTo (a [m - 1]) < = 0; m--)

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

Таким образом, мы можем видеть следующее в наихудшем случае:

• Первая итерация: вы собираетесь от 1 до 1
• Вторая итерация: вы собираетесь от 2 до 1
• Третья итерация: вы собираетесь от 3 до 1
• ...
• N-1th итерация: вы собираетесь от N -1 до 1

Таким образом, вы выполняете 1 + 2 + 3 + 4 + ...N - 1 операции в общей сложности, которые составляет:

(N) (N-1)/2 = O (N^2)

Answer 3

Давайте сделаем этот код проще, как показано ниже.

public InsertionSort(AnyType [] a){ 
    // A value n 
    for(; n < length ;){ 
     // A value m 
     for(; m < someLength ;) { 
      // do something. 
     } 
    } 
} 

Как вы сказали, «someLength» может быть 1 из n-1.

Но давайте посмотрим на этот код во внутреннем цикле.

blahblah 
     for(; m < someLength ;) { 
      // do something. 
     } 
    blahblah 

Он работает только someLength - м (или ни, если он находится под 0) раз

, который является линейным

, который представлен в виде N (для O (N)).

---

Еще одна вещь.

1 + 2 + 3 + 4 + ... + n-1 не может происходить без внешней петли, не так ли?

Тогда почему вы считаете их сложностью внутреннего цикла?