ктерізує розмір вхідніх даніх задачі (розмірність одномірніх, двомірніх масівів, ...).
Часова складність алгоритмом - година Вирішення проблеми у залежності від розмірності задачі.
асимптотично Часова складність - поведінка часової складності при збільшенні розмірності задачі.
Задачі з Великої часової складністю неможліві для реальних комп'ютерів (млрд. років).
При аналізі алгорітмів Використовують Такі позначені.
Запис f (n) = O (g (n)) означає: функція має порядок g (n) тоді, існують Дві додатні Константі з in 0 , что f (n) <= c [g (n)] для всіх n> n 0 .
звичайна f (n) = O (g (n)) візначає годину обчислень;
.
Теорема. Если
A (n) = a m n m + ... a 1 n + a 0
є поліномом ступенів m, тоді
A (n) = O (n m ).
Нехай є два алгоритми з годин оцінкою обчислень O (n) i O (n 2 ). Година Виконання Першого алгоритмом - c 1 n, а іншого - c 2 n 2 (с - константи). Тоді при n 1 /c 2 ПЕРЕВАГА має перший алгоритм, а при n> c 1 /c 2 - другий.
При великих n значення констант несуттєві.
Найбільш типові часові ОЦІНКИ алгорітмів: O (1) - константна, O (log n) - логаріфмічна, O (n) - лінійна, O (n m ) - поліноміальна, O (2 n ) - експоненційна. Для й достатньо великих n:
O (1) 2 ) 3 ) < O ( 2 n )
О© (g (n)) - мінінімальна Часова оцінка.
Задачі класу P I NP
Если розмірність задачі n, то P задача может буті розв'язано за поліноміальній годину O (n m ).
Задача NP может буті вірішена за поліноміальній годину для недетермінованої машини Тьюринга (така машина породжує на шкірному кроці ПЄВНЄВ кількість новіх машин).
Більшість дискретних и комбінаторніх завдань можна вірішіті Шляхом перебору. Прото перебірні методи мают експоненційну складність.
Проблема: Знайте метод Вирішення експоненційніх завдань за поліноміальній годину.
3.1 Планування в просторі станів. Основні Поняття Теорії графів
Граф - сукупність вершин и дуг. Для комп'ютерного Опису графу Використовують: матриця інцідентності, матриця суміжності та списки суміжності.
Поширена структура даних до програмуванні - лінійні списки.
Лінійній список - скінченна послідовність однотипними ЕЛЕМЕНТІВ (певної Довжина). Списки бувають однозв'язні (лінійні), двозв'язні (ціклічні) і т.п. Лінійній список L, что Складається з l 1 , l 2 , .. l n ЕЛЕМЕНТІВ, запісується у вігляді L = 1 , l 2 , .. l n >
Рис .. 1. Графічне зображення списку
Існує два Основним методом задання Списків: послідовний (масив) i зв'язного (дінамічні змінні).
Стек - список, в якому занесення и видалений ЕЛЕМЕНТІВ можна Проводити Тільки через один початковий елемент (вершину стеку). Стек працює за принципом: Останній зайшов - перший Вийшов (Last In First Out - LIFO)
черго назівають список, в якому ВСІ вставки здійснюються в Кінець переліку (змінна rear), а ВСІ видалений відбуваються з голови (початки) переліку (змінна front).
Черга працює за принципом: перший зайшов - перший Вийшов (First In First Out - FIFO).
Поняття граф ввів у 1736 году Ейлер. Граф G містіть Дві множини G = (V, E), де V - множини вершин (вузлів 1 ... n), E - множини ребер. Колі парі вершин впорядковані - то граф орієнтований, інакше - неорієнтованій. Впорядкована пара позначається , невпорядкована - (i, j). У зваження графах Кожне ребро має Вагу. p> ступенів вершини назівається число суміжніх вершин. У орієнтованому графі віділяють півстепінь входу (число вхідніх ребер) та півстепінь виходе (число вихідних ребер).
Шляхом назівається послідовність вершин между двома вершинами p и q.
Циклом назівається шлях, у Якого початкова и кінцева вершини збігаються. Граф назівається зв'язного, ЯКЩО для довільної парі вершин існує между ними шлях.
В
а) б)
Рис.2. Зображення орієнтованого (а) i неорієнтованого (б) графів.
3.2 Способи завдання графів
Існує послідовний и зв'язного способ задання графів.
Послідовна форма вікорістовує квадратно таблицю (Graf (n, n), n - вершин), якові назівають матрицю суміжності. Если є зв'язок между вершинами, то Graf (I, j) = 1, інакше Graf (I, j) = 0. br/>
а) б)
Рис.3. Матріці суміжності графів з рис.2.: а - неорієнтованого, б - орієнтованого
Матриця інцідентності відобража...
