,49» К - 1 Н-1

49= U - UlGHTll) . W-1

49= ГО 4D0 I - I.NUHUM Ц.1

1225= IF(UIGKT(IJ .ое. U GO ТО ЧОО, ИМ-1)/2,С

.122= L-LlGHTd) В

122= К = 1 В

1225=. 400 CONTINUE HtH.-13/2 с

с БкдаЧЕНИЕ РЕБРА В ОЯНБ

49» EDGES » EDGES + 1 М

«В- FROH{EDGES) - 11NC№N(K) , tM

49= TOIEDGESJ » VERTEXIKJ И-1

49= .COsirCEDGES) »L H-l

49- VEIGHT " WEIGHT+ L fri

49- NEXT »UNCreN(K) И-1 \ .-C

- С ИСКЛЮЧЕНИЕ ВНОВЬ ВЫБРАННОЙ .ВЕРШИНЫ ИЗ СГИСКА НЕБЫБ-

= С РАННЫХ . ,

" С .

49= LIGHT(KJ »UeHT(NUMUNJ

49= ukCHSN(K) т UNCHSN(NUHUNJ

49» VERTEXtK) - VEftTEX(HUHUN) \ = С

= С ОСТАЛИСЬ ЛИ НЕБЫБРАННМЕ ВЕРШИНЫ = С

49= NUMUH » NUMUN - 1 H-t .

49= IF(NUHUN .NE. О) GO TO -200 «-1,H-a

1» RETURN • -

« . END

Рис. 4.1.7. Продолжение

напечатает соответствующее сообщение об ошибке и прекратит выполнение алгоритма. Построение этой простой подпрограммы мы предоставляем читателю.

Анализ алгоритма

Теперь проанализируем сложность алгоритма PRIM. Цель состоит в том, чтобы попытаться определить наибольшее количество операций, которые должен выполнить этот алгоритм, чтобы найти ОДМВ для произвольной связной сети с М вершинами.

Прежде чем проводить детальный анализ реализации на рис. 4.1.7, дадим сначала грубый анализ «по порядку величины».

Шаг О алгоритма PRIM требует 0{М) операций для инициализации списка невыбранных вершин. В нашей реализации это включает 0{М) операций для инициализации каждого из трех массивов по (М-1) элементов плюс постоянное количество (не зависящее от М) вспомогательных операций. Так как количество работы здесь прямо пропорционально М, шаг О имеет сложность 0{М).

Шаг 1, итерационный, по существу требует 0(М) проверок, чтобы установить, есть ли еще невыбранные вершины.

Шаг 2 выполняется точно М-1 раз. Каждое выполнение шага 2 требует поиска в текущем списке LIGHT для отыскания ребра с наименьшим весом от невыбранной вершины к выбранной. Эта работа требует О (NUMUN) операций, где NUMUN - текущее число невыбранных вершин (см. алгоритм МАХ из разд. 1.2). Так как NUMUNTW-1, эта часть шага 2 ограничена сверху 0{М) операциями. После идентификации вновь выбранной вершины / нужно обновить список невыбранных UNCHSN. Для каждой невыбранной вершины К мы должны сравнить значение LIGHT (/С) с С {К, I), чтобы увидеть, не дешевле ли теперь связать какую-нибудь из невыбранных вершин с некоторой выбранной, используя вновь выбранную вершину /. Необходим один проход по текущему списку LIGHT; процесс обновления ограничен сверху 0{М) операциями. Так как ни один из остальных подшагов шага 2 не требует более, чем 0{М) операций, сложность шага 2 ограничена сверху величиной 0(М) (напомним, что 0{М)+0{М)=0{М)).

Мы показали, что шаг 2 имеет сложность 0{М) и выполняется (М-1) раз. Следовательно, полная работа, производимая на шаге 2, составит (М-1)(0(УИ))=0(УИ), т. е. алгоритм PRIM имеет общую сложность О(УИ).

Алгоритм PRIM весьма эффективен, особенно если мы полагаем, что можно проверить 0{М) ребер ). Таким образом, ни один алгоритм построения ОДМВ не мог бы сколько-нибудь улучшить результат О(УИ), и алгоритм PRIM достигает этой нижней границы.

Наиболее важной целью анализа является получение функциональной зависимости числа операций, выполняемых алгоритмом, от параметров, характеризующих размеры задачи. Разумеется, алгоритм, требующий 2УИ+1 операций на сети с М вершинами, гораздо эффективнее алгоритма, требующего 30УИ+500 операций. Тем не менее оба алгоритма имеют сложность 0{М), а их время работы, приблизительно пропорциональное числу операций, возрастает с ростом М, по существу, одинаково. Сравните это со случаем двух алгоритмов, один из которых требует 1000УИ2+2000М+3000 операций, тогда как другой требует 0,5УИ! операций для решения той же задачи. Для значений около М=2 второй алгоритм превосходен, но обычно нас интересуют большие значения М. Каков будет результат сравнения этих алгоритмов при М==10, М=20 или УИ=100?

Теперь предпримем более детальный анализ алгоритма PRIM. При таком анализе тщательно рассматривают программную реализацию и подсчитывают число исполнений каждого оператора или по крайней мере стремятся получить ближайшую верхнюю границу для этого числа. Сумма всех этих чисел дает довольно точную оценку числа операций, необходимых данному алгоритму для задачи размера М. Этот тип анализа обычно более трудоемок, чем анализ «по порядку величиг ны», но зато дает более тонкую оценку сложности алгоритма и его частной рассматриваемой реализации.

) Заметим, что полная сеть с М вершинами имеет М{М-1) ребер.

На рис. 4.1.7 справа от каждого оператора приведена верхняя граница числа его выполнений. Большую часть этих чисел легко проверить, и читателю следует проделать это. Однако некоторые участки программы требуют специального пояснения.

Мы опускаем детальный анализ сложности оператора CALL CHECK, который исполняется только один раз. Легко вццеть, что любая реализация этой подпрограммы будет иметь сложность 0{М), так как необходимо проверить все элементов матрицы стоимостей.

Цикл DO300 выполняется М-1 раз. Каждое исполнение этого цикла включает итерации по NUMUN, причем значение NUMUN изменяется от М-\, УИ-2, ... до 1. Таким образом, оператор /= =UNCHSN(/), помещенный после оператора DO300, выполняется М-1 раз при первом выполнении этого цикла DO, М-2 раз при втором и т. д. Следовательно, всего он выполняется

(УИ-1) + (М-2)+... + 1= Е r=!i

i = l

раз.

Теперь легко определить кратность выполнения каждого из остальных операторов в подпрограмме PRIM. Объяснения требуют только кратности выполнения, помеченные буквами А, В, С и D. Они, очевидно, удовлетворяют уравнениям

gM(M-i) с + ю = Щ=.

Если мы просуммируем все кратности выполнения, то увидим, что количество операторов, выполняемых подпрограммой PRIM, ограничено сверху величиной

Ш+1Ш-Ы+В+В.

Так как значения В иО оба ограничены сверху величиной М(УИ-2)/2, общее число исполняемых операторов ограничено сверху величиной

5УИ2+15УИ-14.

Таким образом, общая сложность равна 0{М). Заметим, что в трудоемкости подпрограммы PRIM относительно мало неопределенности. Иначе говоря, число исполняемых операторов для двух различных сетей с УИ вершинами различается только в числах В и D.

Хотя мы и считали каждый оператор за одну операцию, на выполнение этих операторов затрачивается различное количество времени. Например, на операцию сравнения затрачивается больше времени, чем на операцию сложения. Такие уточнения анализа требуют детального знания компиляторов и операционных систем.