Liniowa złożoność obliczeniowa

by Jerry Sky

2020-03-16


Aby osiągnąć sortowanie o złożoności O(n)O(n) należy dodać dodatkowe założenia na dane wejściowe (wyjść poza comparison model), takie jak sortujemy liczby naturalne z danego przedziału.



CountingSort

Własność stabilności sortowania:
algorytm sortowania musi zachowywać porządek równych sobie elementów.
CountingSort ma własność stabilności sortowania.

RadixSort

Użycie np. CountingSorta aby sortować w złożoności linowej z przedziału wielkości ndn^d, gdzie dd jest stałe.

Złożoność RadixSorta to O(dn)O(d \cdot n)