Сортирање поређењем — разлика између измена
Садржај обрисан Садржај додат
Ред 175:
Наведени аргумент омогућује'' апсолутну'', а не само асимптотичку доњу границу броја поређења, тј. <math>\lceil\log_2(n!)\rceil</math> поређења. Ова доња граница је стварно добра (може се постићи са простим алгоритмом сортирања спајањем), али је познат да може бити нетачан. На пример, <math>\lceil\log_2(13!)\rceil=33</math>, али најмањи број поређења за 13 елемената је 34 (што је доказано).<ref name="Peczarski2004" /><ref>Marcin Peczarski: The Ford-Johnson algorithm is still unbeaten for less than 47 elements. Inf. Process. Lett. 101(3): 126-128 (2007) {{doi|10.1016/j.ipl.2006.09.001}}</ref>
Одређивање тачног броја поређења потребних за сортирање датог броја пријава, је рачунски тежак проблем чак и за мало н, и није позната једноставна формула за решење. За неке од неколико конкретних вредности које су израчунате, види {{OEIS2C|id=A036604}}.
=== Доња граница за просечан број поређења ===
| |||