kealon(Ruslan)попробуй ради интереса доказать так O(N) для алгоритма составления бинарной кучи
Чтобы доказать формально нужно время. Интересная идея, я попробую, если будет возможность. Но на это уйдет наверное неделя-две, потому что я никогда таким не занимался.
А с помощью эвристик это можно сделать так:
Алгоритм выглядит следующим образом (по ссылке ещё есть ссылка на прикольную книгу, где всё описано более подробно "Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. Глава 6. Пирамидальная сортировка // Алгоритмы: построение и анализ"):
1.
2.
3.
4.
Build_Heap(A)
A.heap_size = A.length
for i = floor(A.length/2) downto 1
do Heapify(A, i)
где A - это входной массив, который нужно превратить в кучу
A.length - его длина (которая равна длине кучи A.heap_size и для простоты мы эту длину будем иногда обозначать просто N)
Heapify - это функция, которая упорядочивает элементы в поддереве кучи:
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
Heapify(A, i)
left = 2i
right = 2i+1
largest = i
if left <= A.heap_size и A[left] > A[largest]
then largest = left
if right <= A.heap_size и A[right] > A[largest]
then largest = right
if largest != i
then Обменять A[i] и A[largest]
Heapify(A, largest)
Допустим этот алгоритм написан на каком-то реальном ЯП, а не псевдоязыке. Мы распарсили его и получили абстрактное синтаксическое дерево (AST), которое будем анализировать.
Сначала оценим сложность функции Heapify:
Видим в AST этой функции рекурсивный вызов себя. Других рекурсивных вызовов или циклов нет, значит сложность определяется этим единственным вызовом. При рекурсивном вызове передаются 2 аргумента: A и largest. Аргумент A в теле функции никак не изменяется и передаётся как есть. Для largest возможны 3 варианта:
1) largest = i, в этом случае рекурсия прекращается
2) largest = 2i
3) largest = 2i+1
Короче анализатор AST должен сделать такие выводы:
1) С каждым рекурсивным вызовом i как минимум удваивается.
2) Рекурсия прекращается в худшем случае когда i достигает A.heap_size (для простоты будем называть её N)
В wiki и в книге из этого делается неправильный вывод, что сложность этой функции равна O(log N). Наш же анализатор должен сделать вывод, что сложность равна O(log N) - O(log i) или просто O(log N/i). Где log - логарифм по основанию 2. Попробую пояснить почему так.
Например есть цикл:
1.
for (int x = i; x < N; x += step) { ... }
Для него сложность будет O((N-i)/step). Если i=0 и step = 1, то это вырождается просто в O(N).
Для такого цикла:
1.
for (int x = i; x < N; x *= step) { ... }
Сложность будет O(log_step(N/i)), где log_step - логарифм по основанию step.
Функция Heapify эквивалентна как-раз такому циклу со step = 2.
Теперь оцениваем сложность Build_Heap. Видим в ней цикл от floor(N/2) до 1 с шагом 1. Сложность цикла равна
O(sum_i (сложность тела цикла)) =
O(sum_i (log N/i)) =
O(sum_i (log N) - sum_i (log i)) =
(раскрываем сумму по i от 1 до N/2)
O(N/2 * log N - log (N/2)!) =
(тут мы используем
тот факт , что O(log N!) = O(N log N))
O(N/2 * log N - N/2 * log (N/2)) =
O(N/2 * log (N / N/2)) =
O(N/2 * log 2) =
(отбрасываем константы)
O(N)
Готово!
Чтобы все эти вычисления автоматизировать нужно:
1) Заложить все эти эвристики по анализу for, if, рекурсивных вызовов и т.п. в абстрактных синтаксических деревьях
2) Нужна какая-то система, которая упрощает O-выражения - это выглядит вполне реальным. Возможно подойдут готовые системы для символьных вычислений или можно самому что-то написать.
