Сортирање поређењем — разлика између измена
Садржај обрисан Садржај додат
Ред 164:
</div>
Број поређења који овај алгоритам захтева повећање у пропорцији са <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>
Ред 184:
не могуће је одредити у ком редоследу је улаз мањи од ''log<sub>2</sub>(n!)'' просеком поређења.
Ово је најлакше приметити
Приметите да се ово разликује од најгоре случаја који је дат горе изнад, смислу да не дозвољава заокруживање на најближи цео број. На пример, за ''n = 3'', најгори случак горње границе је 3, просек за доњу границу је око 2.58, док је највећа доња граница за просечне случајеве око 2.67.
| |||