4551
правка
Полностью динамическая проверка на планарность: различия между версиями
Перейти к навигации
Перейти к поиску
м
Полностью динамическая проверка на планарность (посмотреть исходный код)
Версия от 19:47, 26 июля 2014
, 26 июля 2014→Открытые вопросы
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 26: | Строка 26: | ||
== Открытые вопросы == | == Открытые вопросы == | ||
Граница O( | Граница <math>O(n^{1/2}) \;</math> для проверки на планарность является амортизированной. Можно ли улучшить эту границу или сделать ее границей для наихудшего случая? | ||
Сложность представленных алгоритмов и большие константные сомножители, входящие в некоторые асимптотические временные границы, делают некоторые результаты непригодными для практического применения. Можно ли упростить эти методы с сохранением сходных теоретических границ? | Сложность представленных алгоритмов и большие константные сомножители, входящие в некоторые асимптотические временные границы, делают некоторые результаты непригодными для практического применения. Можно ли упростить эти методы с сохранением сходных теоретических границ? | ||
== См. также == | == См. также == | ||