36
правок
Изменения
→Сравнение с наивными реализациями
!Обычный подъем до нужного уровня
|<tex>O(n)</tex>||<tex>O(n)</tex>||<tex>O(n)</tex>
|-align="center"
!Полный предподсчет
|<tex>O(n^2)</tex>||<tex>O(1)</tex>||<tex>O(n^2)</tex>
|-align="center"
!Двоичные подъемы
|<tex>O(n)</tex>||<tex>O(1)</tex>||<tex>O(n)</tex>
|}
== Примечания ==
[https://www.mi.fu-berlin.de/en/inf/groups/abi/teaching/lectures/lectures_past/WS0910/V____Discrete_Mathematics_for_Bioinformatics__P1/material/scripts/treedecomposition1.pdf Longest path decomposition]
