Обсуждение:Теорема о нижней оценке для сортировки сравнениями

• мелкие оформительские недочёты, которые всё же стоит исправить

--Андрей Шулаев 19:56, 5 февраля 2012 (MSK)

• На иллюстрации [math]\lt [/math] и [math] \gt [/math], а не [math]\lt [/math] и [math]\ge[/math], как в конспекте. Вообще, иллюстрация выглядит не очень хорошо: слишком мелкий текст в довольно больших узлах, листья не отличаются от остальных вершин.
• Надо всё-таки написать неравенство [math]n! \le l \le 2^h[/math], где [math]l[/math] — количество листьев, поскольку нужна оценка снизу (в доказательстве написаны какие-то равенства).
• Лучше не "узлами являются", а "узлам соответствуют".
• Логарифм в одном месте [math]log[/math], а не [math]\log[/math].
• Заметку про рандомизированные алгоритмы убрать из формулировки теоремы, и вынести вниз. Дать ссылку на доказательство.

--Андрей Шулаев 13:35, 10 мая 2012 (GST)