Сортирање поређењем — разлика између измена
Садржај обрисан Садржај додат
Нема описа измене |
м Разне исправке; козметичке измене |
||
Ред 166:
Број поређења који овај алгоритам захтева повећање у пропорцији са <math>n\log(n)</math>, где <math>n</math> је број елемената за сортирање. Ова граница је [[Asimptotska složenost (računarstvo)|асимптотички мала]].
Дата је листа различитих бројеа (можемо претпоставити, пошто нас занима анализа најгорег могућег случаја), постоји ''n'' [[
Алгоритам за сортирање мора добити довољно информација из поређења да идентификује тачну пермутацију. Ако се алгоритам увек завршава после ''f''(''n'') корака, не може да разликује више од 2<sup>''f''(''n'')</sup> случајева зато што су кључеви различити и свако поређење има само два могућа случаја. Зато,
:<math>2^{f(n)}\geq n!</math>, или еквивалентно <math>f(n)\geq\log_2(n!).</math>
Ред 194:
== Референце ==
* {{cite book|author=[[Donald Knuth]]|title=[[The Art of Computer Programming]]|location=Volume 3|publisher=''Sorting and Searching'', Second Edition. Addison-Wesley|year=1997|id=ISBN 0-201-89685-0 |pages=}} Section 5.3.1: Minimum-Comparison Sorting. pp. 180–197.
| |||