Изменения

Перейти к: навигация, поиск

Level Ancestor problem

94 байта добавлено, 17:41, 18 мая 2019
Сравнение с наивными реализациями
{| class="wikitable" align="center" style="color: blue; background-color:#ffffff;" cellpadding="10"
|+
!colspan="54"| Сравнение асимптотик
|-align="center"
|!width="12%" | <tex>Алгоритм</tex>
|! width="12%" | <tex>Предподсчет</tex>
|! width="12%" | <tex>Ответ</tex>
!Двоичные подъемы
|<tex>O(n \log n)</tex>||<tex>O(\log n)</tex>||<tex>O(n \log n)</tex>
|-align="center"
!Декомпозиция
|<tex>O(n)</tex>||<tex>O(\log n)</tex>||<tex>O(n)</tex>
|-align="center"
!Алгоритм лестниц
|<tex>O(n \log n)</tex>||<tex>O(1)</tex>||<tex>O(n \log n)</tex>
|-align="center"
!Macro-Micro-Tree Algorithm
|<tex>O(n)</tex>||<tex>O(1)</tex>||<tex>O(n)</tex>
36
правок

Навигация