Асимптотична нотация

Досега анализирахме линейното търсене и двоичното търсене, като брояхме максималния брой предположения, които трябва да направим. Но това, което наистина искаме да разберем, е колко дълго ще оперират тези алгоритми. Интересуваме се от време, не само от предположения. Времето за изпълнение на линейното и на двоичното търсене включва времето, необходимо за правенето и проверяването на предположенията, но трябва да разберем нещо повече за тези алгоритми.

Времето за изпълнение на един алгоритъм зависи от това колко време отнема на компютъра да изпълни редовете код на алгоритъма – а това зависи от скоростта на компютъра, езика, на който е написана програмата, и от компилатора, който превежда програмата от програмния език в код, който се изпълнява директно от компютъра, както и други фактори.

Нека помислим за времето за работа на алгоритъма по-внимателно. Можем да използваме комбинация от две идеи. Първо трябва да определим колко време отнема на алгоритъма според размера на входните данни. Тази идея звучи логично, нали? Вече видяхме, че максималният брой предположения в линейното и двоичното търсене се увеличава с увеличаването на дължината на масива. Или да си представим GPS. Ако той знаеше само пътищата от междущатската магистрална система и не знаеше за всеки малък път, би трябвало да може да намира маршрутите по-бързо, нали? Затова мислим за времето за работа на един алгоритъм като за функция, зависима от размера на входа.

Втората идея е да се фокусираме върху това колко бързо расте функцията с увеличаване на размера на входа. Ще наричаме това скорост на растеж на времето за изпълнение. За да запазим нещата разбираеми, ще опростим функцията, така че да отделя най-важната част и да изхвърля по-маловажните неща от информацията. Например, да предположим, че един алгоритъм, работещ върху вход с размер $n$‍ се нуждае от $6n^2+100n+300$‍ машинни инструкции. $6n^2$‍ става по-голям от останалите членове $100n+300$‍, щом $n$‍ стане достатъчно голям (20 в този случай). Ето една диаграма, която показва стойностите на $6n^2$‍ и $100n+300$‍ за стойностите на $n$‍ от 0 до 100:

Можем да кажем, че времето за изпълнение на този алгоритъм расте като $n^2$‍, като оставим настрана коефициента 6 и останалите членове $100n+300$‍. Наистина няма значение какви коефициенти използваме; докато времето за работа е $a{n}^2+bn+c$‍ за някакви числа $a>0$‍, $b$‍ и $c$‍, винаги ще има такава стойност на $n$‍, за която $a{n}^2$‍ е по-голямо от $bn+c$‍ и тази разлика се увеличава с увеличаването на $n$‍. Например, ето диаграма, показваща стойностите на $0,6n^2$‍ и $1000n+3000$‍, където сме намалили коефициента на $n^2$‍ 10 пъти, а другите две константи сме увеличили 10 пъти:

Стойността на $n$‍ при която $0,6n^2$‍ става по-голямо от $1000n+3000$‍ се е увеличила, но винаги ще има такива точка на пресичане на двете графики, без значение какви са константите.

Чрез изхвърлянето на по-незначителните части и коефициентите можем да се фокусираме върху важната част от времето за работа на алгоритъма – неговата скорост на растеж – без да се оплитаме в детайли, които затрудняват нашето разбиране. Това се нарича Асимптотно означение. Ще видим три негови форми: big-$\mathrm{\Theta }$‍ нотация, big-O нотация, и big-$\mathrm{\Omega }$‍ нотация.

Това съдържание е резултат от съвместната дейност на преподавателите Томас Кормен и Девин Балком от Компютърни науки Дартмут, както и компютърния екип на Кан Академия. Съдържанието е лицензирано CC-BY-NC-SA.