Защо ни е това
Теорията за сложността на алгоритмите възниква през 70-те години на миналия век, когато компютрите започват да се използват масово. Учените започват да си задават въпроси за качествата на различните алгоритми: защо два алгоритъма, които решават една и съща задача върху едни и същи данни, работят за различно време и ползват различен обем от паметта.
Ключово
Сложността се мери в брой стъпки, а не в секунди. Секундите зависят от машината; стъпките — само от алгоритъма.
Задача и алгоритъм
Двете основни понятия на теорията — задача и алгоритъм — са невъзможни за дефиниране. Задачата е достатъчно общ въпрос в термините на някаква предметна област, на който трябва да отговорим.
Задачата „намерете НОД на две естествени числа“ е масова, защото целта е да се посочи начин за намиране на НОД независимо от това кои са числата. Задачата „намерете НОД на 30 и 12“ не е масова — тя е екземпляр на масовата задача.
Бележка
Не за всяка масова задача намирането на алгоритъм е възможно. Съществуват задачи, които са алгоритмично неразрешими. Тук няма да се занимаваме с такива.
Машина с произволен достъп до паметта
Понятието „сложност на алгоритъм“ може да се разглежда само след като фиксираме съвкупността от допустими операции. Тази съвкупност наричаме изчислителен механизъм. Най-удобният за въведение е Машината с произволен достъп до паметта (МПД) — силно опростен модел на съвременния компютър.
- Входната и изходната лента са безкрайни в едната посока — аналог на клавиатурата и екрана. Във всяка клетка се записва по едно цяло число.
- Паметта за данни е крайна и клетките ѝ са номерирани. Тези номера наричаме адреси.
- Акумулаторът е „сърцето“ на МПД и също съдържа едно цяло число. Всички пресмятания минават през него.
- Броячът на командите пази адреса на изпълняваната команда. След всяка команда се увеличава с 1.
Командите на МПД
Всяка команда се състои от код и незадължителен аргумент. При аритметичните операции МПД може да изпълнява три типа команди — илюстрирано със събирането (с <X> означаваме съдържанието на X):
| Команда | Вид адресация | Какво прави |
|---|---|---|
ADD A | пряка | <АК> = <АК> + <A> |
ADD@ A | косвена | <АК> = <АК> + <<A>> |
ADD# N | непосредствен аргумент | <АК> = <АК> + N |
Аналогични са SUB, MULT, DIV (целочислено деление) и MOD (остатък). Останалите команди:
| Команда | Какво прави |
|---|---|
LOAD A | Прочита в АК съдържанието на клетка A. Има и LOAD@ и LOAD#. |
STORE A | Записва съдържанието на АК в клетка A. Има и STORE@, но не и STORE#. |
INPUT | Прочита в АК число от входната лента и премества четящото устройство. |
OUTPUT | Записва числото от АК на изходната лента. |
JMP C | Безусловен преход: <БК> = C. |
JMPZ C | Преход при нулев АК. Аналогично JMPP, JMPN, JMPPZ, JMPNZ. |
STOP | Прекратява работата на програмата. |
Пример 1 — дискриминанта
Програма за намиране на дискриминантата D = b² − 4ac. Трите коефициента влизат на адреси 0, 1 и 2:
0) INPUT
1) STORE 0
2) INPUT
3) STORE 1
4) INPUT
5) STORE 2
6) LOAD# 4
7) MULT 0
8) MULT 2
9) STORE 3
10) LOAD 1
11) MULT 1
12) SUB 3
13) OUTPUT
14) STOPВсички входове имат един и същ размер — 3 числа — и всяка команда се изпълнява точно по веднъж. Затова T(n) = 15, а използваните клетки са 0, 1, 2 и 3, тоест S(n) = 4.
Пример 2 — четене на числа до нула
На входната лента са записани няколко положителни числа, последвани от нула. Програмата ги въвежда в паметта и намира броя им:
0) LOAD# 0 // 1 път
1) STORE 0 // 1 път
2) LOAD 0 // n+1 пъти
3) ADD# 1 // n+1 пъти
4) STORE 0 // n+1 пъти
5) INPUT // n+1 пъти
6) JMPZ 9 // n+1 пъти
7) STORE@ 0 // n пъти
8) JMP 2 // n пъти
9) LOAD 0 // 1 път
10) OUTPUT // 1 път
11) STOP // 1 пътТук се използва косвената адресация: в клетка 0 стои броячът, а STORE@ 0 записва прочетеното число в клетката, чийто адрес пише в клетка 0. Така първото число отива в клетка 1, второто — в клетка 2, и така нататък.
Командите 2–6 се изпълняват по n + 1 пъти, 7–8 — по n пъти, а останалите пет — по веднъж. Значи T(n) = 5(n+1) + 2n + 5 = 7n + 10, а S(n) = n + 1.
Размер на входа
За дефинирането на сложност е много важно да се определи размер на входа. В пример 2 това е броят n на числата — и не е трудно да се досетим, че колкото по-голямо е n, толкова по-дълго ще работи програмата.
Внимание
Не във всяка задача е лесно. В пример 1 всички екземпляри имат един и същ размер и няма ефектът „колкото по-голям размер, толкова по-дълго“. А при НОД(a, b) с a > b за размер е естествено да вземем a.
Има и задачи, в които не размерът на входа определя бързодействието, а размерът на изхода. Например задачата „пресметни квадратите на естествените числа, по-малки или равни на n“ има вход с размер 1, но изход, който расте с n. Тогава за размер на входа взимаме n.
Двете дефиниции
Сложност по време в най-лошия случай
T(n) = максимумът от броя изпълнени команди по всички входове с размер n.
Сложност по памет в най-лошия случай
S(n) = максимумът от броя използвани клетки памет по всички входове с размер n.
Бележка
Обърни внимание на „в най-лошия случай“. Не разглеждаме всички възможни входове един по един — в общия случай входът, при който алгоритъмът прави максимален брой стъпки, се намира без много труд.
Поведение на функциите на сложност
Точното пресмятане невинаги е толкова просто, а и в практиката рядко се използват езици като този на МПД. Затова вместо да пресмятаме точно функциите на сложност, за практически нужди по-често оценяваме тяхното поведение.
| Означение | Клас функции | Пример от урока |
|---|---|---|
O(1) | Константни — не зависят от n | Пример 1: T = 15, S = 4 |
O(n) | Линейни — най-простият представител е f(n) = n | Пример 2: T = 7n + 10, S = n + 1 |
Константите — 15, 4, 7, 10 — от гледна точка на практиката не са много важни. Важно е как расте функцията, когато n расте.
Въпроси и задачи
1. Напиши програма за МПД, която въвежда двете страни на правоъгълник и пресмята периметъра и лицето му. Оцени сложността по време и памет в най-лошия случай.
2. Напиши програма за МПД, която въвежда редица от неотрицателни числа, завършващи с нула, и извежда сумата им. Указание: допълни програмата от пример 2.
3. Напиши програма за МПД, която въвежда цяло положително число N и N цели числа, и извежда сумата им.
Какво трябва да запомниш
- Сложността се мери в брой стъпки — независимо от това колко бърз е компютърът.
- Пряка адресация е
ADD A, косвена —ADD@ A, непосредствен аргумент —ADD# N. - Размерът на входа е числото, от което зависи работата на алгоритъма; не винаги е броят на данните.
- „В най-лошия случай“ значи максимум по всички входове с даден размер.
O(1)— константна сложност,O(n)— линейна. Константите не се броят; расте ли — расте.