Dlaczego sortowanie jest ciągiem O (n log n)?

Question

Powiel możliwe:
Plain English explanation of Big O

W odpowiedzi na programowania układanki powiedziane sortowania ciąg zajmuje O (n log n). Jak to jest wyprowadzone?

Czy ktoś ma dobry odnośnik do zasobów Big O.

Dzięki

Answer 1

Definicja i kilka przykładów Big O można znaleźć za pomocą wyszukiwarki, na przykład tutaj:

• http://en.wikipedia.org/wiki/Big_O_notation

wyjaśnienie algorytmów sortowania opartych na elementach porównywanie, wraz z wyjaśnieniem dla dolnej granicy od liczby wymaganych porównań, można znaleźć tutaj:

• http://en.wikipedia.org/wiki/Comparison_sort

Answer 2

Dlaczego sortowanie ciągu O (n log n)?

Sortowanie znaków w łańcuchu nie musi oznaczać O (n log n).

• O (n log n) jest optymalna wartość dla comparison sort. Jest to również złożoność implementacji domyślnego sortowania wielu języków. Jednak na pewno można zrobić coś gorszego. Złożoność sortowania znaków w łańcuchu zależy od konkretnego algorytmu wybranego do rozwiązania tego zadania.
• W niektórych przypadkach możliwe jest również wykonanie funkcji lepszej niż O (n log n) za pomocą algorytmu sortowania, który nie jest sortowaniem porównawczym. Na przykład, jeśli wiesz, że masz ciąg ASCII z maksymalnie 127 różnymi znakami, możesz użyć wartości counting sort, która jest O (n). Sortowanie zliczania byłoby również możliwe do uzyskania w przypadku ciągów Unicode, w których wszystkie znaki znajdują się w Basic Multilingual Plane.