27
правок
Изменения
→Сложность
При неправильной реализации алгоритма, используя вместо очередей <tex>M_1{''}</tex> и <tex>M_1{'}</tex> [[Персистентный дек|дек]] и добавляя вершины из <tex>M_0</tex> в начало дека, алгоритм в худшем случае будет работать за экспоненциальное время, так делать не рекомендуется.
В плохих случаях алгоритм Левита работает за <tex>O(n^2m)</tex>. Рассмотрим полный граф <tex>K_n</tex> с <tex>n</tex> вершинами и такими <tex>m</tex> рёбрами, идущими в [[Лексикографический порядок|лексикографическом порядке]]:* для все всех вершин <tex>1 < i < j \leqslant n</tex> вес ребра <tex>(i,j) = j - i - 1</tex>, т.е. количество вершин между <tex>i</tex> и <tex>j</tex>; <tex>w_{i,i+1}=0</tex>,
* ребро <tex>(1,n)</tex> веса <tex>0</tex>,
* для всех вершин <tex>1 < i < n</tex> вес ребра <tex>(1,i) = w_{1,i+1} + i - 1</tex>; от <tex>1</tex> до <tex>i</tex> вершины расстояние равно <tex>\sum\limits_{k=i-1}^{n-2}k</tex>.
