Сложность Bubble Сортировка

Question

Я видел на многих местах, сложность для пузырьковой сортировки является O (п).

Но как это может быть, потому что внутренний цикл должен всегда работает N-I раз.

for (int i = 0; i < toSort.length -1; i++) { 
      for (int j = 0; j < toSort.length - 1 - i; j++) { 
       if(toSort[j] > toSort[j+1]){ 
        int swap = toSort[j+1]; 
        toSort[j + 1] = toSort[j]; 
        toSort[j] = swap; 
       } 
      } 
     } 

Answer 1

А что такое «среднее» значение n-i? n/2

Так он работает в O(n*n/2), который рассматривается как O (N)

Answer 2

Так как наружный цикл выполняется п раз, и для каждой итерации прогонов внутреннего цикла (Ni) раз, общее количество операций может быть рассчитывается как n * (ni) = O (n2).

Answer 3

Существуют различные типы сложности времени - вы используете большое обозначение O так, что означает, что все случаи этой функции будет по крайней мере на этот раз сложность.

Как к бесконечности, это может быть в основном п^2 раз сложность в худшем случае. Сложность времени - это не точное искусство, а большая часть шага для какой скорости вы можете ожидать для этого класса алгоритма, и, следовательно, вы пытаетесь быть слишком точным.

Например теоретическая сложность времени вполне может быть п^2, хотя он теоретически должен быть п * п-1 из-за любой непредвиденной обработки накладных расходов может быть выполнена.

Answer 4

Это O (n^2), потому что длина * длина.