Комментарии 3
Я все понимаю, но данный вопрос и так прекрасно разобран в «Алгоритмы: построение и анализ» с более простым и коротким доказательством.
Мда, программа не программа, доказательство не доказательство.
Еще я бы добавил ссылку к первоисточнику. Данный алгоритм был придуман Робертом Флойдом в 1964 году, как часть алгоритма TreeSort: Floyd, Robert W., (1964), Algorithm 245 — Treesort 3, Communications of the ACM 7 (12): 701
Зарегистрируйтесь на Хабре , чтобы оставить комментарий
Двоичная куча: доказательство сложности построения О(n)