Сортирање поређењем — разлика између измена
Садржај обрисан Садржај додат
м datum; козметичке измене |
|||
Ред 160:
<div class="thumbcaption">
Изнад: Поређење доње границе
</div>
</div>
Ред 186:
Ово је најлакше приметити помооћу концепта теорије информације. Ентропија тако случајне пермутације је ''log<sub>2</sub>(n!)'' битова. Пошто поређење може дати само два решења, највећа количина информације коју произведе је 1 бит. Зато, после ''k'' поређења преостала ентропија поређења, с обзиром на резултате поређења је бар ''log<sub>2</sub>(n!) - k'' битова. Да бисмо сортирали, неопходна је комплетна информација, да би преостала ентропија била 0. Из тога следи да ''k'' мора бити најмање ''log<sub>2</sub>(n!)''.
Приметите да се ово разликује од најгоре случаја који је дат горе изнад,
У оваквим случајевима више елемената може имати исти кључ, не постоји очигледна статистичка интерпретација за "просечан случај",
== Белешке ==
Ред 195:
== Референце ==
* {{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.
{{DEFAULTSORT:Comparison Sort}}
| |||