0 added
0 removed
Original
2026-01-01
Modified
2026-03-10
1
<p>Теги: алгоритмы сортировок, дерево решений, формула стирлинга, алгоритмы для разработчиков, алгоритмы и структуры данных</p>
1
<p>Теги: алгоритмы сортировок, дерево решений, формула стирлинга, алгоритмы для разработчиков, алгоритмы и структуры данных</p>
2
<p>Когда люди изучают алгоритмы сортировок, у них часто возникает вопрос: а существует ли идеальный алгоритм, который может сортировать всё за линейное время или даже быстрее - за константное? Ответ: не существует и не может существовать.</p>
2
<p>Когда люди изучают алгоритмы сортировок, у них часто возникает вопрос: а существует ли идеальный алгоритм, который может сортировать всё за линейное время или даже быстрее - за константное? Ответ: не существует и не может существовать.</p>
3
<h2>Почему?</h2>
3
<h2>Почему?</h2>
4
<p>Предположим, у нас есть n-элементов (вектор), которые нужно отсортировать: а1, а2, …, аn.</p>
4
<p>Предположим, у нас есть n-элементов (вектор), которые нужно отсортировать: а1, а2, …, аn.</p>
5
<p>Любой<strong>алгоритм сортировки</strong>из любого входного вектора делает отсортированный выходной вектор. Сортировка в данном случае делается путём попарных сравнений элементов друг с другом. Если мы представим процесс сортировки графически, получится так называемое “<strong>дерево решений</strong>”.</p>
5
<p>Любой<strong>алгоритм сортировки</strong>из любого входного вектора делает отсортированный выходной вектор. Сортировка в данном случае делается путём попарных сравнений элементов друг с другом. Если мы представим процесс сортировки графически, получится так называемое “<strong>дерево решений</strong>”.</p>
6
<p>В каждом узле такого дерева будет сравнение между соответствующими элементами. Переход по левому потомку будет соответствовать ситуации, когда аi < аj, переход по правому - когда аi >= аj. Когда дошли до конца дерева, то есть до листовой вершины, - алгоритм окончен, порядок определён.</p>
6
<p>В каждом узле такого дерева будет сравнение между соответствующими элементами. Переход по левому потомку будет соответствовать ситуации, когда аi < аj, переход по правому - когда аi >= аj. Когда дошли до конца дерева, то есть до листовой вершины, - алгоритм окончен, порядок определён.</p>
7
<p>Чему равна оценка снизу для такого<strong>алгоритма</strong>? Это количество сравнений, то есть высота<strong>дерева решений</strong>, причём в его листьях<strong>n!</strong>перестановок исходных элементов.</p>
7
<p>Чему равна оценка снизу для такого<strong>алгоритма</strong>? Это количество сравнений, то есть высота<strong>дерева решений</strong>, причём в его листьях<strong>n!</strong>перестановок исходных элементов.</p>
8
<p>Обозначим за h<strong>высоту</strong>этого дерева. Число листьев для полного дерева высоты h составляет (2h - 1). Единицу отбрасываем, потому что нас интересует только порядок величины.</p>
8
<p>Обозначим за h<strong>высоту</strong>этого дерева. Число листьев для полного дерева высоты h составляет (2h - 1). Единицу отбрасываем, потому что нас интересует только порядок величины.</p>
9
<p>Таким образом, у нас получается, что для произвольного дерева имеем:<strong>n! < 2h</strong></p>
9
<p>Таким образом, у нас получается, что для произвольного дерева имеем:<strong>n! < 2h</strong></p>
10
<p>Логарифмируя, получаем:<strong>log(n!) < log(2h) ~ h</strong></p>
10
<p>Логарифмируя, получаем:<strong>log(n!) < log(2h) ~ h</strong></p>
11
<p>По<a>формуле Стирлинга</a>log(n!) ~ n * log(n), таким образом:<strong>h ~ n * log(n)</strong></p>
11
<p>По<a>формуле Стирлинга</a>log(n!) ~ n * log(n), таким образом:<strong>h ~ n * log(n)</strong></p>
12
<p>Это означает, что<strong>сортировка</strong>, работающая на сравнениях, не может сортировать быстрее, чем за<strong>n * log(n)</strong>сравнений.</p>
12
<p>Это означает, что<strong>сортировка</strong>, работающая на сравнениях, не может сортировать быстрее, чем за<strong>n * log(n)</strong>сравнений.</p>
13
<p><em>Хотите задать вопрос? Пишите комментарий!</em></p>
13
<p><em>Хотите задать вопрос? Пишите комментарий!</em></p>
14
14