Вычислительная сложность алгоритма

Чтобы определить вычислительную сложность алгоритма пирамидальной сортировки, заметим, что почти полное двоичное дерево с n узлами имеет [log2(n +1)] уровней. При создании пирамиды и при её перестройке каждая запись сравнивается, в худшем случае, с одним узлом на каждом уровне.

Максимальная вычислительная сложность алгоритма

T max(n) = T С(n) + T П(n), где T С(n) – вычислительная сложность создания пирамиды, T П(n) – вычислительная сложность перестройки пирамиды и получения отсортированного массива.

Вычислительная сложность создания пирамиды составляет