Сложност на алгоритми

Computation Complexity

В темата за сортиране разгледахме два алгоритъма (Bubble Sort и Selection Sort), за които казахме, че са относително бавни. Как можем да определим, че един алгоритъм е по-бърз от друг? Един начин би бил да напишем и двата и да тестваме с различни входни данни, като така правим емпирична проверка. Това, обаче, не винаги е особено хубаво решение, тъй като за целта трябва да имплементираме и двата алгоритъма. На състезание рядко ще имате достатъчно време за да направите това, така че би било хубаво да знаем друг начин, по който да предвиждаме бързината на алгоритъма, който смятаме да напишем, преди да го напишем. Тук ще разгледаме един много разпространен начин за оценка, който в повечето случаи дава достатъчно добра апроксимация на времето, което ще е нужно на вашето решение да обработи дадени входни данни.

Сравнение на различни решения

За мен лично, най-лесният начин за разбиране на идеята за сложности на алгоритми е чрез даване на конкретни примери. Затова ще разгледаме една сравнително проста задача (модификация на Zero Sum), за която ще покажем три различни решения. Търсим броя на различните двойки индекси (i, j), такива, че A_i + A_j == X. Ще тестваме с шест набора тестове, като всеки следващ е точно 10 пъти по-голям от предходния:

1. N = 1,000
2. N = 10,000
3. N = 100,000
4. N = 1,000,000
5. N = 10,000,000
6. N = 100,000,000

Решение 1: проста итерация

Най-простото решение е да направим два цикъла, които да обхождат числата. За всяка двойка индекси, проверяваме дали сумата на съответните елементи дава X, и ако това е така увеличаваме отговора. Това решение е просто както за измисляне, така и за имплементация. То е сравнително добро за малко на брой числа, но се представя доста бавно при повече. Докато за N = 1000 и N = 10,000 то върви почти мигновено, за 100,000 му трябват малко над две секунди, за 1,000,000 - почти четири минути, а за 10,000,000 - над шест часа! За най-големия тест на това решение биха му били нужни около двадесет и седем дни и половина.

Решение 2: двоично търсене

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

Решение 3: нека бъдем умни

Все пак има накъде да оптимизираме. С известни наблюдения можем да елиминираме дори двоичното търсене (тази оптимизация не е особено очевидна). Ако имаме двойка индекси (i, j), какво можем да кажем за сумата A_i + A_j в сравнение с A_i+1 + A_j? Тъй като числата са различни и сортирани, то със сигурност A_i + A_j < A_i+1 + A_j. Тоест увеличаването на някой от индексите води до увеличаване на сумата. Нещо повече, сходно наблюдение можем да направим при намалянето им. С намалянето на j сумата намалява. Тъй като индексите трябва да са различни, можем да считаме, че винаги i < j.

!	Не е толкова очевидно как тази оптимизация е свързана с двоичното търсене. Реално, индексът j е този индекс, който двоичното би намерилo. Но тъй като увеличаването на i води до потенциално преместване на j само и единствено наляво, то не е нужно да правим ново двоично търсене при всяко местене.

Така нашето решение ще е следното: в началото i = 0; и j = N - 1;. Докато сумата е по-малка от X мърдаме i надясно. Ако пък е по-голяма, мърдаме j наляво. Продължаваме да правим това, докато i < j. Може би забелязвате, че с тази хитра оптимизация ние правим точно N сравнения. Времената на това решение са още по-малки. За най-големия вход ни трябваше едва около десета от секундата!

Ето и пълната таблица с резултатите: Ако искате да тествате какви ще са времената при вас, можете да ползвате тази програма: pairsWithSumX.cc.

Наблюдения

Нека се вгледаме по-внимателно в горната таблица. Забелязвате ли, че при наивния алгоритъм времето скача от 2.376 секунди на 237.700 секунди, когато входът бива увеличен от 100,000 на 1,000,000? На по-наблюдателните от вас сигурно им е направило впечатление, че числата 2.376 и 237.700 съмнително си приличат - второто е почти точно 100 пъти по-голямо от първото. А входът беше увеличен само 10 пъти! Такова решение се нарича квадратно, тъй като времето за изпълнение расте с K² пъти при K пъти по-голям вход. Аналогично можете да видите, че 6.6 часа е 23760 секунди, което е отново приблизително 100 пъти повече от предходния тест.

Подобни наблюдения можем да се опитаме да направим и за останалите две решения, но тъй като времената са сравнително малки, те няма да са особено точни. Все пак, второто решение е почти 10 пъти по-бавно след всеки тест. Прави ни впечатление, че не е точно 10 пъти, ами малко повече.

?	Всъщност времената в последното решение варират толкова много (и са под 10 пъти) главно защото кодът е много прост и компилаторът прилага редица оптимизации - примерно извършва по няколко събирания и сравнения на такт.

Поради закръглянето и малките времена е доста трудно да се направи точно наблюдение за третото решение, но то е между 4 и 10 пъти по-бавно на всеки следващ тест.

Какво е сложност?

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

Логично е колкото по-големи са входните данни, толкова по-бавно да работи даден алгоритъм. Вече видяхме, че в горните алгоритми това беше точно така - колкото по-голямо беше N, толкова по-бавно работеха и трите.

!

Тук ползваме леко опростен вариант, в който константата за брой операции в секунда speed е еднаква и в двете формули. Това, обикновено, не е точно така, тъй като по принцип различни алгоритми ползват различни типове операции, а различни операции се изпълняват различно бързо. Все пак, разликата в общия случай не е голяма.

Но докато времето за наивния алгоритъм растеше квадратично спрямо входните данни (можем да си го представим като time = N²/speed, за някаква константа speed), това за умното решение растеше линейно спрямо тях (time = N/speed). Kонстантата speed, на която делим, e броят операции в секунда, които може да изпълни тестващата машина. И тъй като тя е еднаква, независимо какъв алгоритъм ползваме, то можем... да я махнем! Е, вече времето на изпълнение няма да е измерено в секунди, но какво от това? Все пак ние искаме да сравним скоростта на различни алгоритми, а не да намерим за колко точно време ще вървят те.

Така стигаме и до това какво е сложност на алгоритъм по време. В най-общи линии, това е функция, описваща колко операции ще са му нужни, при вход с дадена големина.

Big-O нотация

Някакви хора са измислили специален начин да се обозначава, че говорим за сложности. Разбира се, направили са го сложно и теоретично, с маса дефиниции и изисквания. Ние ще игнорираме повечето от това (йее!). Ако се интересувате от точни дефиниции, погледнете Introduction to Algorithms (MIT Press, Cormen, Leiserson, Rivest, Stein), където това е обяснено много, много добре. Прекалено добре всъщност, в следствие на което е над двадесет страници.

Ние ще игнорираме theta, omega, small-o и другите възможни, като се спрем единствено на най-често ползваната нотация: Big-O. Нейното име идва от начина на изразяване на сложността като главно О, отваряща скоба, функция и затваряща скоба. Демек O(f(n)). Например сложността на наивния алгоритъм, който написахме, изразена чрез Big-O, би била O(N2) (тук функцията е N²), тъй като, както видяхме вече, той зависи квадратично спрямо големината на входните данни. Хитрият алгоритъм пък би бил O(N), тъй като зависеше линейно от тях.

За да сметнем сложността на алгоритъма с двоично търсене трябва да помислим малко. Както казахме, двоичното търсене работи за логаритъм на брой стъпки - тоест O(log(N)), изразено в Big-O. А в нашата имплементация ползвахме двоично търсене за да намерим втория индекс за всеки първи индекс. Така на практика направихме N на брой двоични търсения, като сложността на целия алгоритъм става O(N∙log(N)). Ето откъде идват "малко по-бързо от линейно" нарастващите времена!

В най-лошия случай...

Big-O нотацията всъщност не казва точно колко операции ще са нужни на нашия алгоритъм, нито дава приблизителния им брой. Нещо повече, Big-O не показва дори средния случай, което би било много по-полезно за задачи от реалния живот. Тя дава негова горна граница. За повечето алгоритми, ако горната граница е изчислена правилно, тя ще е еквивалентна и на средния случай, но това не винаги е така.

Ако помните, в задачата с познаването на числото на Станчо, Ели имаше шанс да го познае още в самото начало и да не задава пълния брой log(N) въпроси, които казахме, че са ѝ нужни.

!	Дори 99.99% от случаите вашата програма да ползва N*log(N) операции, ако в някои от останалите ползва N2, то тя е със сложност O(N2). Пример за много известен такъв алгоритъм е quicksort.

Това, обаче, би било просто късмет, а не най-лошия случай. Всъщност, това, че Big-O дава горната граница е много удобно за нас, тъй като в състезателни задачи, ако има най-лош случай, то той най-вероятно ще присъства в тестовете. Някои от авторите на задачи имат свойството да са гадни копелета в това отношение (hi). Така че, когато пишем дадена задача, нас най-много ни интересува дали ще може да мине всички тестове, тоест дали ще се държи достатъчно добре в най-лошия случай.

Константи

Малко шокиращо за хора, които за първи път срещат Big-O нотацията е, че константите "изчезват", тоест биват игнорирани, при изчисляване на сложности. Например два алгоритъма, единият от които прави 5*N операции, а другият само 2*N, биват оценени като O(N). Това е така, тъй константите не влияят на скоростта на нарастване на необходимото време, нужно за изпълнение на алгоритъма ни, с нарастване на входните данни. Както казахме и малко по-рано, когато премахнахме константата за "брой операции в секунда", с нарастване на големината на входа два пъти, скоростта също нараства два пъти, и това е най-важното.

Наистина, при алгоритми с еднаква сложност константите биха били полезни - за да изберем този от тях, който действително би вървял най-бързо. Когато сложностите са различни, обаче, константите могат да са заблуждаващи. За следващия пример ще позволим да имаме константи в сложността, което по принцип не е правилно.

Ако забелязахте, в наивната имплементация на задачата от началото на темата не правим точно N² операции, тъй като вторият цикъл започва от i+1 вместо от 0. Така той прави N²/2 операции, следователно много по-точна негова горна граница би била O(0.5∙N2). Версията с двоичното търсене пък има деление и допълнителни сметки вътре в себе си. Тъй като делението е сравнително по-бавна операция от събирането, можем да кажем, че неговата константа е, примерно, 100, тоест O(100∙N∙log(N)). Това е доста завишено, но точно това се опитваме да покажем - че всъщност няма значение.

?

Когато има два възможни алгоритъма с различна сложност, като този с по-висока сложност има много по-малка константа, те могат да се комбинират. За малки стойности да се ползва теоретично по-бавния (но който ще се справи много по-бързо за малки стойности поради ниската си константа), а за големи - другия. Този трик е приложен в STL-ския sort(), където за малък брой елементи се ползва едно сортиране, а за голям - друго.

При N = 100 първият алгоритъм ще се нуждае от около 5,000 операции, докато вторият от цели 70,000. Когато N става по-голямо, обаче, например N = 10,000, първият алгоритъм ще се нуждае от около 50,000,000 операции, докато вторият от едва 14,000,000. Така че алгоритъмът с двеста пъти по-малка константа се оказва по-бавен (при достатъчно голям вход). Като заключение можем да кажем, че константите имат значение само когато искаме да сравняваме алгоритми с еднаква сложност, затова и биват игнорирани при този вид нотация.

Примери за сложности

Съществуват много различни функции на сложности, които може да срещнете. Само някои от тях обаче са наистина често срещани. Тук ще разгледаме тези, които най-често ще ви трябват за състезания по информатика.

Константна

Константната сложност, или O(1), е най-бързата възможна сложност, тъй като тя не зависи от обема на входните данни - тя е винаги някакъв константен брой операции.

Логаритмична

Логаритмичната сложност, или O(log(N)), ще срещнете в някои бързи и сравнително прости алгоритми, които най-често ще са само част от решението ви. Примери за такива са вече разгледаното двоично търсене, алгоритъм на Евклид и бързото вдигане на степен, което ще видим по-нататък.

Тя е една от най-бързите такива, които все пак зависят от входа. Както видяхме в темата за двоично търсене, при нарастване на входа ни от 1000 на 1,000,000,000,000,000,000 разликата в броя стъпки беше 10 срещу 60 - тоест само 6 пъти нарастване на времето за 1,000,000,000,000,000 пъти нарастване на входа.

!	Тъй като loga(x) = logb(x) / logb(a), а logb(a) е константа (при това малка, за повечето реални примери), то считаме, че loga(x) ~= logb(x).

"Логаритмична", сама по себе си, скрива някои неща. Например, каква е базата на логаритъма? Дали е 2, дали е 3, дали е e, дали е pi? Оказва се, че няма голямо значение. Както при база 2, така и при база 10, нарастването е изключително бавно. Всъщност база 2 е един от най-лошите случаи, които може да имаме, и въпреки това вече видяхме, че се представя много добре! По-нататък ще видим алгоритми (като например този за троично търсене), в който базата ще е по-малка от 2 (в случая ще е 3/2). Все пак той работи много бързо.

Корен квадратен

Сложност корен квадратен, или O(sqrt(N)), ще срещнете често, когато искате да балансирате бързодействието на два алгоритъма (или две негови части). Всъщност, ако помните, вече срещнахме един пример за такъв алгоритъм! Спомнете си оптимизацията на наивното търсене, която приложихме в темата за двоично търсене. Там стигнахме до точно O(sqrt(N)) алгоритъм за познаване на числото на Станчо.

Линейна сложност

Линейна сложност, или O(N), имате често в алгоритми, които обработват всеки обект (елемент на масив, връх на граф, т.н.) по константен брой пъти. Два много разпространени примера за такива алгоритми са търсенето в ширина и търсенето в дълбочина, които ще разгледаме малко по-нататък. В много задачи, където искаме да постигнем O(N) сложност на цялото решение, идеята е да се ползва линейна структура данни и няколко (примерно един, два или три) "паса" на входните данни (всеки с линейна сложност) за да се стигне до крайния резултат. Както казахме, идеята е всеки елемент от входните данни да се обработи по O(1) пъти.

Често допускана грешка от начинаещи състезатели е да се пропуска четенето на входа и печатането на изхода, при изчисляването на сложността. Например ако в дадената по-горе задача се питаше дали в дадените числа се среща X, то донякъде интуитивно би било да допуснем, че има решение със сложност O(log(N)) - просто да ползваме двоично търсене за да проверим това. Но за да направим двоично търсене в случая, трябва да имаме масив с числата, а самото взимане (четене, генериране или копиране) на масив с N елемента е със сложност O(N).

Енлог сложност

Добре де, това не е някаква специална сложност, но решихме да я споменем, защото е много често срещана. ЕнЛог(Ен) сложност, или O(N∙log(N)), ще срещнете в задачи, където трябва да сортирате елементите (най-бързите сортирания са с такава сложност). Както видяхме, когато елементите са сортирани, можем да приложим редица бързи алгоритми върху тях (например двоично търсене, а по-късно ще разгледаме и други, като, да кажем, алчни алгоритми). Също така алгоритми, базирани на Разделяй и Владей, много често са с O(N∙log(N)) сложност.

Квадратична сложност

Квадратична сложност, или O(N2), можете да срещнете също сравнително често, тъй като редица прости алгоритми (например простите сортирания, които вече разгледахме) я изискват.

Кубична сложност

Кубична сложност, или O(N3), ще срещнете в много на брой, по-сложни алгоритми, като например умножение на матрици, алгоритъм на Флойд, Гаусова елиминация и други. Донякъде забавно (по-скоро иронично) е, че макар и с относително голяма изчислителна сложност, повечето алгоритми, които са с такава сложност, са прости за имплементация - те не са нищо повече от три вложени цикъла, които вършат сравнително прости операции.

Експоненциална сложност

Експоненциалната сложност може да е както O(2N) (по-добрият вариант), така и O(N!) (по-лошият вариант). Обикновено можем да ги срещнем при изчерпващи алгоритми (например backtrack), или пък динамично по битова маска. Понякога (най-вече в състезания като TopCoder) можем да срещнем задачи, в които трябва да направим всички пермутации на нещо и да пробваме дали всяка от тях е (оптимален) отговор. Това води до O(N∙N!) - една от най-високите сложности, които можете да срещнете в състезания.

Малко по-формално

Ама наистина държите да споменем формалната дефиниция, така ли? Добре... После да не съжалявате!

Нека имаме две функции f(x) и g(x), дефинирани върху подмножество на реалните числа. f(x) = O(g(x)) при x клонящо към безкрайност, тогава и само тогава, когато съществува положителна константа M, такава, че за всички достатъчно големи стойности на x, f(x) e не повече от M умножено по g(x) по абсолютна стойност.

С други думи, f(x) = O(g(x)) тогава и само тогава, когато съществуват положително реално число M и реално число x₀, при които |f(x)| <= M*|g(x)| за всяко x > x₀.

Надявам се да сте щастливи. Накарахте човек, който не можа да си вземе анализа до трети курс, да пише такива неща. Shame on you!

Леко объркващо

Игнорирането на константите може да е малко объркващо. С наученото до сега би било логично да предположим, че сложността на алгоритъм, който прави приблизително 2*N² операции, не може да е O(N2), тъй като N² < 2*N², а казахме, че Big-O задава горна граница. Той, обаче, все пак е O(N2), поради игнорирането на константите. Например, функцията в О-то може да е, да кажем, 3*N², което е по-голямо от 2*N². След това, обаче, сме премахнали константата във вътрешната функция, тъй като Big-O го изисква. Тоест, на практика може функцията, показана вътре в О-то, да е по-малка от броя операции, които се извършват в действителност, и все пак да е горна граница.

Всъщност това следва директно от формалната дефиниция, но тъй като изобщо не ви трябва да я знаете за състезания, особено пък ако сте по-малки (да се разбира под група А), то преценихме, че ще е полезно ако го покажем допълнително.

Зависимост от повече от една променлива

?	Ако F пъти изпълним функция, която има вложен цикъл до M, като вътре в него имаме операция със сложност O(G), то цялата сложност би била O(MFG).

Разбира се, понякога входът на задачата е по-сложен. Например, както ще видите малко по-късно, в алгоритмите за графи често имаме брой върхове N и брой ребра M. Така те често зависят и от двете бройки, без значение дали това ще е O(N+M), O(N∙M), О(N2∙M), O(MN) или други възможни комбинации между тях.

Секунда е много

Каква сложност можем да очакваме да върви за една секунда? Разбира се, това е много относително, но все пак, алгоритми с дадените сложности почти винаги се изпълняват за под секунда на хубав, модерен процесор (в момента е 2012 година), а също така вървят на TopCoder (където процесорите вече не са толкова нови, но пък time limit-ът е 2 секунди).

• O(1) при N < INF

?	Алтернативни Big-O нотации: O(1) = O(yeah) O(logN) = O(nice) O(N) = O(okay) O(N2) = O(my) O(2N) = O(no) O(N!) = O(mg!)

• O(log(N)) при N < INF
• O(sqrt(N)) при N ~ 10¹⁶
• O(N) при N ~ 100,000,000
• O(N∙log(N)) при N ~ 1,000,000
• O(N∙sqrt(N)) при N ~ 100,000
• O(N2) при N ~ 10,000
• O(N3) при N ~ 500
• O(2N) при N ~ 22
• O(3N) при N ~ 15
• O(N!) при N ~ 10

Сложност по памет

След като сме обяснили сложността по време е почти тривиално да обясним сложността по памет. Тя представлява скоростта, с която нараства ползваната памет с нарастване на входните данни. За горната задача, примерно, тази памет е O(N), тъй като се нуждаем от масив с N клетки, за да пазим входа. Тя рядко ще ви трябва, освен ако не искате да проверите дали решението ви ще се събере в ограниченията по памет. Но, обикновено, в задачата имате един голям масив, който доминира всички останали променливи и масивчета, та неговият размер е единственият, който е от значение. Затова на състезания много по-рядко се налага да изчислявате в Big-O нотация сложността на алгоритъма ви по памет.

Важност

Тази тема, макар и относително теоретична и досадна, е изключително важна. И по-странното е, че не е важна защото някой ще ви пита каква е сложността на алгоритъма, който сте написали (макар че и това ще се случва). Тя е важна, защото ще трябва вие да определяте дали даден алгоритъм си струва да бъде написан или не, и колко точки ще хване, ако го напишете (ако сте на ученическо състезание).

Готиното е, че ще ползваме сложности буквално за всеки алгоритъм и структура данни, които разглеждаме оттук нататък, като така с времето ще се научите сами интуитивно да определяте каква е сложността на дадено парче код.

Допълнителни материали

1. Статия за Big-O нотация (en.wikipedia.org)
2. Доста подобна на тази статия (www.topcoder.com)
3. Изчисляване на сложности в итеративни и рекурсивни алгоритми (www.topcoder.com)
4. Мастър теорема (en.wikipedia.org)

предишна тема

версия за печат

следваща тема