Я пытаюсь определить время выполнения алгоритма Дейкстры, используя очередь с минимальным приоритетом (которая реализована с использованием кучи Фибоначчи)
Код
Анализ: я знаю, что для вставки кучи Фибоначчи используется ключ уменьшения/вставки O (1), а для извлечения min это O (log (n))
Строки с 1 по 3: время выполнения равно O(V) для каждой вершины.
Цикл в строке 4 занимает O (V), но ExtractMin занимает O (log (V)), а цикл for из строк 6-7 — O (E) для каждого ребра.
Поскольку цикл for находится внутри цикла while, я бы получил V (log (V) + E)
поэтому я бы получил O(V + Vlog(V) + VE), что сводится к O(Vlog(V) + VE)
но в большинстве статей указано, что это O (V * log (V) + E), это потому, что E> V или я делаю что-то не так?