|
|
Математический и эмпирический анализ.
Математические исследования данных алгоритмов показывают, что алгоритм Прима и алгоритм Дейкстры, с использованием очередей по приоритету на базе многопозиционных частично упорядоченных полных деревьев, в худшем случае будет работать за время ElogdV, где E - количество ребер, V - количество вершин в графе, d - количество детей у узла в дереве для очередей с приоритетами. На практике это означает, что этот алгоритм работает за линейное время от количества ребер, кроме чрезмерно разреженных графов. То есть алгоритмы исполняются за время пропорциональное E для разреженных графов, и за V2 для насыщенных графов.
Все выше приведенные теоретические рассуждения проверяются эмпирическими исследованиями. Ниже приведено подробное исследование алгоритмы Дейкстры и менее подробное исследование алгоритма Прима. Замеры времени выполнения проводились на случайных графах с различным количеством ребер. В первой колонке таблицы дано количество вершин в графе, во втором насыщенность графа в процентах от максимального количества ребер, в третьей колонке время выполнения классического алгоритма, а в четвертой время выполнения алгоритма с использованием очередей по приоритетам. Из таблиц видно, что, чем больше в графе вершин, тем больше выигрыш в производительности алгоритмов с очередью по приоритетам с использованием деревьев, чем с использованием неупорядоченного массива. Что подтверждает, что рост времени выполнения у классических алгоритмов квадратичный, а у алгоритмов с применением очередей по приоритетам ElogdV, то есть практически линейно зависит от количества ребер в графе.
|
|