4.2 Анализ по времени
Анализ по времени проводится функцией clock() из стандартной библиотеки <time.h>. Длины ребер задаем с помощью функции rand() из той же библиотеки <time.h>, длины этих ребер будут варьироваться от 0 до 15. Ниже на рисунке 7 представлена диаграмма роста функции f(t)=N, где t – время работы программы, а N – количество вершин. Жирным выделен график роста функции алгоритма Прима, а тонким выделен график роста функции алгоритма Крускала.
Рисунок 6 – Диаграмма роста функции
Заключение
В ходе реализации алгоритма, были применены теоретические и практические знания полученные за период обучения.
Теория графов применяется во многих областях человеческой деятельности для формализации информации и выявления скрытых закономерностей. На примере задачи оминимальном остовом дереве можно видеть, что теоретико-графовые алгоритмы легко и в виде, удобном для восприятия, переводятся на декларативные языки, при этом эффективность реализации лишь в некоторых случаях уступает реализациям на императивных языках программирования. Также можно отметить, что все инструкции программы направлены исключительно на решение задачи, отсутствуют операции приведения типов, присваивания и т.п., что значительно сокращает количество возможных ошибок. Т.о., декларативные языки программирования являются мощным и удобным инструментом решения задач.
Список используемых источников.
ГОСТ 7.32–2001. Отчёт о научно-исследовательской работе. Структура и правила оформления [Текст]. – Взамен ГОСТ 7.32–91 ;введ. 2001–07–01. – Минск :Межгос. совет по стандартизации, метрологии и сертификации ; М. : Изд-во стандартов, 2001. – 16 с. – (Система стандартов по информации, библиотечному и издательскому делу).
ГОСТ 7.1–2003. Библиографическая запись. Библиографическое описание. Общие требования и правила составления [Текст]. – Взамен ГОСТ 7.1–84, ГОСТ 7.16–79, ГОСТ 7.18–79, ГОСТ 7.34–81, ГОСТ 7.40–82 ;введ. 2004–07–01. – М. : Изд-во стандартов, 2004. – 116 с. – (Система стандартов по информации, библиотечному и издательскому делу).
Кормен Т. Х. / Лейзерсон Ч. И., Ривест Р. Л., Штайн К. Алгоритмы: построение и анализ, 2-е изд. — М.: Вильямс, 2007. — 1296 с.
Роберт Серджвик. Фундаментальные алгоритмы на С++. [Текст]: в 5 ч. / Роберт Серджвик. – СПб, ООО «ДиаСлфтЮП», 2002.
Ч. 5: Алгоритмы на графах: Перевод с англ. – 2002 – 486с. ISBN 5-93772-054-7.
Степанов, В.Н. Дискретная математика: графы и алгоритмы на графах: учеб.пособие / В.Н. Степанов. – Омск, Изд-во ОмГТУ, 2010 – 120с. ISBN 978-5-8149-0913-8
Форум программистов и сисадминов CyberForum.ru [Электронный ресурс]. –Форум начинающих и профессиональных программистов, системных администраторов, администраторов баз данных, компьютерный форум. – Режим доступа: . http://www.cyberforum.ru/ –Загл. с экрана.
Википедия – свободная энциклопедия [Электронный ресурс]. – Википедия – свободная энциклопедия, которую может редактировать каждый. Режим доступа: . http://ru.wikipedia.org–Загл. с экрана.