search

kzhereb / kpi-acts-ta2020

Materials for "Algorithm theory" course
MIT License
0 stars 0 forks source link

D04.11. What is the minimum estimate of the complexity of the sorting algorithm? #27

Open DenVosk opened 4 years ago

DenVosk commented 4 years ago

D04.11. What is the minimum estimate of the complexity of the sorting algorithm?

D04.11. Яка оцінка знизу (мінімальна) складності алгоритму сортування?

khilchuk-ol commented 4 years ago

Тут можна почитати про доведення нижньої межі (lower bound) для алгоритмів сортування, які використовують порівняння: https://www.bowdoin.edu/~ltoma/teaching/cs231/fall07/Lectures/sortLB.pdf

PickDough commented 4 years ago

Було доведено, що не існує алгоритму сортування, який працював би швиджше ніж O(n), адже, якщо ми не знаємо додаткових умов, то потрібно розглянути ві елементи мінімум один раз.

bastikk commented 4 years ago

Тут можна почитати про доведення нижньої межі (lower bound) для алгоритмів сортування, які використовують порівняння: https://www.bowdoin.edu/~ltoma/teaching/cs231/fall07/Lectures/sortLB.pdf

Проте ж не можна нехтувати ситуативними алгоритмами які працюють за лінійний час(сортування підрахунком), хоча і потребують певної додаткової інформації про елементи. А O(n log n) являється правильно відповіддю для алгоритмів сортування, які базуються на порівнянні.