Блог пользователя Darisishe

Где можно найти доказательство асимптотики алгоритма переливания меньшего к большему?
Автор Darisishe, история, 4 года назад, По-русски

Наткнулся на лекцию, где был приведена данная техника, но анализа асимптотики не было, но было сказано, что она составляет O(n*logn), где n — количество вершин в дереве.

  • Проголосовать: нравится
  • +23
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится +53 Проголосовать: не нравится

Давай оценим, сколько раз мы перельем каждый отдельный элемент. Заметим, что если на каком-то шагу мы переливаем наш элемент из $$$k$$$-элементного множества, то размер результирующего множества будет как минимум $$$2k$$$ (так как множество из которого мы переливаем — меньше по размеру чем то, в которое переливаем). Вот таких умножений размера множества на 2 можно сделать не более чем $$$\log n$$$, значит каждый элемент будет перелит не более чем $$$O(\log n)$$$ раз. Итого $$$O(n \log n)$$$.

→ Ответить