Временная оценка работы программы.
Общее количество вызовов рекурсивной процедуры Search: C = N-1+N-2+…+1 = N*(N-1) / 2. Стандартная рекурсивная процедура поиска в глубину (Search_Depth) имеет временную оценку порядка N2; мы имеем N вершин и для каждой вершины – N вариантов путей поиска, таким образом С = N*N. Наша измененная процедура Search имеет такую же временную оценку, однако, в большинстве случаев временная сложность процедуры равна N, потому что мы не рассматриваем смежные вершины и вершины, валентность которых равна 1.
Посчитаем временную сложность алгоритма всей процедуры Solve:
С = N*N*(N-1)/2 = O(N3).
Для процедуры, позволяющей выводить на экран не только максимальное количество вершинно-непересекающихся <u,v>-цепей для каждой пары несмежных вершин, но и сами <u,v>-цепи, это хорошая временная характеристика.
Заключение.
У каждого учащегося есть свое понимание понятия связности графа. Чаще всего это понимание строится на основе неформальных наблюдений, и не всегда является четким, ясным и даже правильным. Терема Менгера придает этим наблюдениям точный и строгий смысл. Поэтому целесообразным будет включение темы "Алгоритмическая реализация Теоремы Менгера" в раздел учебного курса по информатике.
Литература.
Новиков Ф.А. Дискретная математика для программистов – СПб: Питер, 2001 г. Окулов С.М. Конспекты занятий по информатике (алгоритмы на графах). – Киров, 1996 г. Окулов С.М. Основы программирования. Часть 4. – Киров, 2001 г.
Loading ...