jak obliczyć złożoność czasu sortowania bąbelkowego

Question

Próbowałem zrozumieć strukturę danych i inny algorytm, następnie pomylono mnie, by zmierzyć złożoność czasu sortowania bąbelkowego.

for (c = 0; c < (n - 1); c++) { 
    for (d = 0; d < n - c - 1; d++) { 
    if (array[d] > array[d+1]) /* For descending order use < */ 
    { 
     swap  = array[d]; 
     array[d] = array[d+1]; 
     array[d+1] = swap; 
    } 
    } 
} 

Teraz każdy mówi Big O najlepszym przypadku O (n), case Średnia (N2) i najgorszy przypadek (N2) .Ale kiedy widzę kod, znajdujący się w pierwszej fazie wewnętrznej pętli biegu n czas potem w sekundę faza n - 1, i n - 2 i tak dalej. Oznacza to, że w każdej iteracji jego wartość maleje. Na przykład, jeśli mają [] = {4, 2, 9, 5, 3, 6, 11} więc całkowita liczba porównań będzie -

1st Phase - 7 time 
2nd phase - 6 time 
3rd Phase - 5 time 
4th Phase - 4 time 
5th Phase - 3 time 
6th Phase - 2 time 
7th Phase - 1 time 

Kiedy więc obliczyć czas wygląda = (7 + 6 + 5 + 4 + 3 + 2 + 1) + 7 = 35, ale najgorsza złożoność czasu to n2 jak na dokument.

tak Czy ktoś może mi powiedzieć, jak obliczyć prawidłową wartość.

Answer 1

Chodźmy przez przypadkach do Big O dla Bubble Sort

przypadek 1) O (n) (najlepszym przypadku) Tym razem złożoność może wystąpić, jeśli tablica jest już posortowane, a to oznacza, że ​​nie nastąpiła zamiana i tylko 1 iteracja n elementów

Przypadek 2) O (n^2) (Najgorszy przypadek) Najgorszy przypadek ma miejsce, jeśli tablica jest już posortowana, ale w porządku malejącym. Oznacza to, że w pierwszej iteracji musiałoby zajrzeć do n elementów, a następnie wyglądałoby elementy n-1 (ponieważ największa liczba całkowita jest na końcu) i tak dalej, aż do momentu, gdy nastąpi 1 porównanie. Big-O = n + n - 1 + n - 2 ... + 1 = (n * (n + 1))/2 = O (n^2)

W twoim przykładzie może nie te wiele elementów w każdej fazie, jako tablica, nie jest w porządku malejącym.

Answer 2

Zauważyłeś, że całkowita liczba wykonanych porównań wynosi n + (n - 1) + ... + 2 + 1. Ta suma jest równa n * (n + 1)/2 (patrz Triangular Numbers), która jest równa 0,5 n^2 + 0,5 n, co jest oczywiście 0 (n^2).

Answer 3

dokonuje porównania między dwoma elementami. więc w Pierwsza faza - porównanie n-1. tj. 6 Druga faza - porównanie n-2. tj. 5 i tak dalej do 1. , a zatem suma = n (n-1)/2, to jest O (n^2).

jeśli wystąpił błąd, który można poprawić .....

Answer 4

Wyjaśniając dla najgorszego przypadku, tutaj:

elements = raw_input("enter comma separated elements : ") 
elements = elements.split(',') 
elements = map(int, elements) 
length = len(elements) 

for i in xrange(length - 1): 
    print "outer pass : ", i 
    for j in xrange(length - i - 1): 
     print "inner pass : ", j 
     if elements[j] > elements[j + 1]: 
      elements[j + 1], elements[j] = elements[j], elements[j + 1] 
     print "elements : ", elements 
print elements 

wyjściowych:

wprowadzić przecinek oddzielne elementy: 5,4,3,2,1

zewnętrzna wprost 0

wewnętrzny pass: 0

elementy: [4, 5, 3, 2, 1]

wewnętrzna przechodzą: 1

elementy: [4, 3, 5, 2, 1]

wewnętrzne przejście 2

elementy: [4, 3, 2, 5, 1] ​​

wewnętrzne przejście: 3

elementy: [4, 3, 2, 1, 5]

zewnętrzna przechodzą: 1

wewnętrzne przejście 0

elementy: [3, 4, 2, 1, 5]

wewnętrzna przechodzą: 1

elementy: [3, 2, 4, 1, 5]

wewnętrzne przejście 2

elementy: [3, 2, 1, 4, 5]

zewnętrzna wprost 2

wewnętrzne przejście 0

elementy: [2, 3, 1, 4, 5]

wewnętrzna przechodzą: 1

elementy: [2, 1, 3, 4, 5]

zewnętrzna wprost: 3

wewnętrzne przejście 0

elementy: [1, 2, 3, 4, 5]

[1, 2, 3, 4, 5]

W ten sposób pierwsza iteracja wszystkich n elementów zostanie przeskanowana, to skanuje n - 1 elementów w następnej iteracji. Tak więc dla wszystkich elementów.

n + n - 1 + n - 2 ... + 1 = (n * (n + 1))/2 = O (N^2)

Answer 5

O(n^2) = n(n-1)/2 jest właściwa.

Podobnie jak w powyższym przykładzie 5 elementów.

5(5-1)/2 == 10. 

5(5+1)/2 != 10. 

Answer 6

dla numeru n liczb, łącznej liczby porównań wykonanych będzie (n - 1) + ... + 2 + 1. suma ta jest równa (n-1) * n/2 (patrz Numery trójkątne), które są równe 0,5 n^2 - 0,5 n, tj. O (n^2)