[sweet_dream99]

Dlaczego sortowanie przez wyszukiwanie ma złożoność n^2, skoro wykonuje się (n-1)+(n-2)+(n-3)... razy?

Nawet jak będę zliczać wejścia do wewnętrznej pętli w programie to dla n=10 wychodzi 45, a nie 100 wejść do wewnętrznej pętli.
I jak zliczam na papierze to tak wychodzi 9+8+7+6+5+4+3+2+1 = 45, bo odrzuca te elementy co już posortował.

#programowanie #naukaprogramowania #informatyka

[piternet]

@sweet_dream99 suma ciągu arytmetycznego 1..(n-1) to (1+(n-1))*(n-1)/2 = n*(n-1)/2 - czyli rzędu O(n^2). W złożoności nie chodzi o dokładną liczbę operacji, ale o to jak ta liczba operacji rośnie wraz ze wzrostem danych wejściowych.

[3denos]

Suma n pierwszych liczb naturalnych to wlasnie n(n-1)/2. Za bardzo skupiasz sie na tym, ze tam nie wychodzi 100 albo dokladnie n^2. Notacja big O to jest asymptotyczny wzrost z dokladnoscia co do pewnych wspolczynnikow.

[ponton]

Oprócz tego co pisali wyżej, to taka uwaga:

n=10 wychodzi 45, a nie 100

@sweet_dream99: To teraz policz dla dla n=20 (dwa razy większe) i wychodzi 190 (ponad 2x2 razy więcej), więc przy dwukrotnym wzroście wielkości danych czas rośnie ponad cztery razy. Przy n=100 (10 razy więcej) wychodzi 4950 (ponad 10x10 razy więcej). To nie jest złożoność liniowa, a właśnie kwadratowa, bo zwiększenie x razy wielkości wejścia powoduje wzrost czasu