алгоритмична сложност. Алгоритми за търсене

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

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

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

Определения

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

Има концепции за сложност в най-лошото, средно аритметичноили най-добрият случай. Обикновено сложността се оценява в най-лошия случай.

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

Редът на нарастване на сложността на алгоритмите

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

Стъпка на алгоритъмае набор от последователно подредени елементарни операции, чието време за изпълнение не зависи от размера на входа, тоест е ограничено отгоре от някаква константа.

Видове асимптотични оценки

O - най-лошата оценка

Помислете за сложността f(n) > 0, функция от същия ред g(n) > 0, входен размер n > 0.
Ако f(n) = O(g(n))и има константи c > 0, n0 > 0, тогава
0 < f(n) < c*g(n),
за n > n0.

Функцията g(n) в този случай е асимптотично точна оценка на f(n). Ако f(n) е функция на сложността на алгоритъм, тогава редът на сложността се определя като f(n) – O(g(n)).

Този израз дефинира клас функции, които растат не по-бързо от g(n) до постоянен фактор.

Примери за асимптотични функции

f(n)	g(n)
2n 2 + 7n - 3	n 2
98n*ln(n)	n*ln(n)
5n+2	н
8	1

Ω – оценка за най-добрия случай

Дефиницията обаче е подобна на дефиницията на най-лошия случай
f(n) = Ω(g(n)), ако
0 < c*g(n) < f(n)

Ω(g(n))дефинира клас функции, които растат не по-бавно от функцията g(n)до постоянен фактор.

Θ – оценка за средния случай

Струва си да се спомене, че в този случай функцията f(n)при n > n0е навсякъде по средата c 1 *g(n)и c 2 *g(n), където c е постоянен фактор.
Например, когато f(n) = n 2 + n; g(n) = n2.

Критерии за оценка на сложността на алгоритмите

Единен критерий за тегло (RWC)предполага, че всяка стъпка от алгоритъма се изпълнява за една единица време, а клетка от паметта за една единица обем (до константа).
Логаритмичен тест за тегло (LWT)взема предвид размера на операнда, който се обработва от определена операция и стойността, съхранена в мястото на паметта.

Времева сложност с LVKопределена от стойността л (оп), където опе стойността на операнда.
Капацитивна сложност при LVCопределена от стойността l(M), където М- размерът на клетката с памет.

Пример за оценка на сложността във факторно изчисление

Необходимо е да се анализира сложността на алгоритъма за факторно изчисление. За да направите това, нека напишем този проблем в C псевдокод:

Void main() ( int result = 1; int i; const n = ...; for (i = 2; i<= n; i++) result = result * n; }

Времева сложност при критерий за еднакво тегло

Достатъчно е просто да определите какъв е размерът на входа на дадена задача н.
Брой стъпки - (n - 1).

По този начин времевата сложност за RVC е равна на На).

Времева сложност при логаритмичен претеглен критерий

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

И така, в тази задача се разграничават три операции:

1) аз<= n

На i-та стъпка ще се окаже дневник (n).
От стъпки (n-1), сложността на тази операция ще бъде (n-1)*log(n).

2) i = i + 1

На i-та стъпка ще се окаже дневник (i).
.

3) резултат = резултат * i

На i-та стъпка ще се окаже лог((i-1)!).
По този начин сумата .

Ако съберем всички получени стойности и изхвърлим членовете, които очевидно растат по-бавно с увеличаване н, получаваме крайния израз .

Сложност на капацитета при критерий за еднакво тегло

Тук всичко е просто. Трябва да преброите броя на променливите. Ако в задачата се използват масиви, всяка клетка от масива се счита за променлива.
Тъй като броят на променливите не зависи от размера на входа, сложността ще бъде равна на О(1).

Сложност на капацитета по критерий за логаритмично тегло

В този случай трябва да се вземе предвид максималната стойност, която може да бъде в клетка от паметта. Ако стойността не е дефинирана (например с операнд i > 10), тогава се счита, че има някаква гранична стойност Vmax.
В този проблем има променлива, чиято стойност не надвишава n(i), и променлива, чиято стойност не надвишава н! (резултат). Така резултатът е O(log(n!)).

заключения

Изучаването на сложността на алгоритмите е доста увлекателна задача. В момента анализът на най-простите алгоритми е включен в учебните планове на техническите специалности (по-точно обобщеното направление "Информатика и компютърна техника"), занимаващи се с компютърни науки и приложна математика в областта на ИТ.
Въз основа на сложността се разграничават различни класове задачи: П, НП, NPC. Но това вече не е проблем в теорията на асимптотичния анализ на алгоритмите.

Със сигурност често сте срещали означения като O (log n) или сте чували фрази като "логаритмична изчислителна сложност" във връзка с всякакви алгоритми. И ако все още не разбирате какво означава това, тази статия е за вас.

Оценка на трудност

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

Да кажем, че някакъв алгоритъм трябва да изпълни 4n 3 + 7n условни операции, за да обработи n входни елемента от данни. Тъй като n се увеличава, общото време на работа ще бъде значително по-засегнато от повишаване на n до куба, отколкото от умножаването му по 4 или добавянето на 7n. Тогава казваме, че времевата сложност на този алгоритъм е равна на O(n 3) , т.е. зависи кубично от размера на входните данни.

Използването на главно O (или така наречената O-нотация) идва от математиката, където се използва за сравняване на асимптотичното поведение на функциите. Формално O(f(n)) означава, че времето за работа на алгоритъма (или количеството заета памет) нараства в зависимост от количеството входни данни не по-бързо от някаква константа, умножена по f(n).

Примери

O(n) - линейна сложност

Такава сложност има например алгоритъмът за намиране на най-големия елемент в несортиран масив. Трябва да преминем през всички n елемента на масива, за да разберем кой е най-големият.

O(log n) - лог сложност

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

O(n 2) - квадратична сложност

Такава сложност има например алгоритъмът за сортиране чрез вмъкване. В каноничната реализация се състои от два вложени цикъла: единият за преминаване през целия масив, а вторият за намиране на място за следващия елемент във вече сортираната част. По този начин броят на операциите ще зависи от размера на масива като n * n, т.е. n 2 .

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

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

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

Здравейте! Днешната лекция ще бъде малко по-различна от останалите. Ще се различава по това, че е само косвено свързан с Java. Тази тема обаче е много важна за всеки програмист. Ще говорим за алгоритми. Какво е алгоритъм? С прости думи, това е някаква последователност от действия, които трябва да се извършат, за да се постигне желаният резултат. Често използваме алгоритми в ежедневието си. Например, всяка сутрин имате задача: да дойдете на училище или на работа и в същото време да бъдете:

• Облечени
• чиста
• пълен

Който алгоритъмще ви позволи да постигнете този резултат?

1. Събудете се с аларма.
2. Вземете душ, измийте се.
3. Пригответе закуска, направете кафе/чай.
4. Яжте.
5. Ако не сте изгладили дрехите си от вечерта, изгладете ги.
6. Облечи се.
7. Напусни къщата.

Тази последователност от действия определено ще ви позволи да получите желания резултат. В програмирането цялата същност на нашата работа се състои в постоянното решаване на проблеми. Значителна част от тези задачи могат да бъдат изпълнени с помощта на вече известни алгоритми. Например, вие сте изправени пред следната задача: сортиране на списък от 100 имена в масив. Тази задача е доста проста, но може да бъде решена по различни начини. Ето едно възможно решение: Алгоритъм за сортиране на имена по азбучен ред:

1. Купете или изтеглете в интернет "Речник на руските лични имена" издание от 1966 г.
2. Намерете всяко име от нашия списък в този речник.
3. Запишете на лист на коя страница от речника се намира името.
4. Подредете имената, като използвате бележки върху лист хартия.

Такава последователност от действия ще реши ли проблема ни?Да, ще позволи. Ще това решение ефективен? Едва ли. Тук стигаме до друго много важно свойство на алгоритмите – тяхното ефективност. Можете да решите проблема по различни начини. Но както в програмирането, така и в ежедневието, ние избираме метода, който ще бъде най-ефективен. Ако работата ви е да направите сандвич с масло, със сигурност можете да започнете, като засадите пшеница и издоите крава. Но ще стане неефикасенрешение - ще отнеме много време и ще струва много пари. За да разрешите простия си проблем, можете просто да си купите хляб и масло. А алгоритъмът с жито и крава, въпреки че ви позволява да решите проблема, е твърде сложен, за да бъде приложен на практика. За да се оцени сложността на алгоритмите в програмирането, беше създадена специална нотация, наречена Big-O ("голямо O"). Big-O ви позволява да прецените доколко времето за изпълнение на даден алгоритъм зависи от данните, подадени към него. Нека разгледаме най-простия пример - пренос на данни. Представете си, че трябва да прехвърлите някаква информация като файл на голямо разстояние (например 5000 километра). Кой алгоритъм ще бъде най-ефективен? Зависи от данните, с които трябва да работи. Например, имаме 10 мегабайтов аудио файл.
В този случай най-ефективният алгоритъм би бил прехвърлянето на файла през интернет. Това ще отнеме най-много няколко минути! И така, нека отново изразим нашия алгоритъм: "Ако искате да прехвърлите информация под формата на файлове на разстояние от 5000 километра, трябва да използвате предаване на данни през Интернет." Отлично. Сега нека го анализираме. Решава ли проблема ни?Най-общо казано, да, става. Но какво да кажем за неговата сложност? Хм, тук нещата стават интересни. Факт е, че нашият алгоритъм е много зависим от входящите данни, а именно от размера на файловете. Сега имаме 10 мегабайта и всичко е наред. Ами ако трябва да прехвърлим 500 мегабайта? 20 гигабайта? 500 терабайта? 30 петабайта? Дали алгоритъмът ни ще спре да работи? Не, всички тези обеми данни все още могат да бъдат прехвърлени. Ще работи ли по-дълго?Да, ще стане! Сега знаем важна характеристика на нашия алгоритъм: колкото по-голям е размерът на данните, които трябва да бъдат прехвърлени, толкова повече време ще отнеме алгоритъмът, за да завърши. Но бихме искали да разберем по-точно как изглежда тази зависимост (между размера на данните и времето за тяхното предаване). В нашия случай сложността на алгоритъма ще бъде линеен. „Линеен“ означава, че с увеличаването на количеството данни времето за прехвърлянето им ще се увеличи приблизително пропорционално. Ако данните станат 2 пъти повече, и ще отнеме 2 пъти повече време за прехвърлянето им. Ако данните станат 10 пъти по-големи, времето за прехвърляне ще се увеличи 10 пъти. Използвайки нотация Big-O, сложността на нашия алгоритъм се определя като НА). Тази нотация се помни най-добре за в бъдеще - тя винаги се използва за алгоритми с линейна сложност. Обърнете внимание: тук изобщо не говорим за различни „променливи“ неща: скоростта на интернет, мощността на нашия компютър и т.н. Когато оценяваме сложността на алгоритъм, това просто няма смисъл - така или иначе не можем да го контролираме. Big-O оценява самия алгоритъм, независимо от „средата“, в която ще трябва да работи.Нека продължим с нашия пример. Да кажем, че в крайна сметка се оказа, че размерът на файловете за прехвърляне е 800 терабайта. Ако ги предадем по интернет, проблемът, разбира се, ще бъде решен. Има само един проблем: ще са необходими приблизително 708 дни за предаване по стандартна модерна връзка (при 100 мегабита в секунда), която повечето от нас използват у дома. Почти 2 години! :ОТака че нашият алгоритъм очевидно не е подходящ тук. Имате нужда от друго решение! Неочаквано на помощ ни идва IT гигант Amazon! Неговата услуга Amazon Snowmobile ви позволява да зареждате големи количества данни в мобилно хранилище и да ги доставяте на правилния адрес с камион!
И така, имаме нов алгоритъм! „Ако искате да прехвърлите информация под формата на файлове над 5000 километра и този процес отнема повече от 14 дни при прехвърляне през интернет, трябва да използвате транспортирането на данни на камион на Amazon.“ Цифрата от 14 дни е избрана произволно тук: да кажем, че това е максималният период, който можем да си позволим. Нека анализираме нашия алгоритъм. Какво ще кажете за скоростта? Дори камионът да се движи само с 50 км/ч, той ще измине 5000 километра само за 100 часа. Това са малко повече от четири дни! Това е много по-добро от опцията за интернет предаване. Какво ще кажете за сложността на този алгоритъм? Ще бъде ли и линеен, O(N)? Не, няма да стане. В края на краищата, камионът не се интересува колко го товарите - той все пак ще върви с приблизително същата скорост и ще пристигне навреме. Независимо дали имаме 800 терабайта или 10 пъти повече данни, камионът пак ще стигне до мястото за 5 дни. С други думи, алгоритъмът за доставяне на данни чрез камион постоянна сложност. „Константа“ означава, че не зависи от данните, предадени на алгоритъма. Сложете 1GB флашка в камиона - пристига след 5 дни. Поставете там дискове с 800 терабайта данни - ще ви стигнат за 5 дни. Когато използвате Big-O, постоянната сложност се обозначава като О(1). Откакто се запознахме НА)и О(1), нека сега да разгледаме още примери за „програмиране“ :) Да кажем, че ви е даден масив от 100 числа и задачата е да отпечатате всяко от тях на конзолата. Пишете нормален for цикъл, който върши тази работа int numbers = new int [100]; // ..попълване на масива с числа for (int i: numbers) ( System. out. println (i) ; ) Каква е сложността на написания алгоритъм? Линеен, O(N).Броят на действията, които програмата трябва да извърши, зависи от това колко числа са предадени в нея. Ако в масива има 100 числа, ще има 100 действия (извежда се на екрана) Ако в масива има 10 000 числа, ще трябва да се извършат 10 000 действия. Може ли нашият алгоритъм да бъде подобрен? Не. Във всеки случай трябва N преминава през масиваи изпълнете N изхода към конзолата. Нека разгледаме друг пример. public static void main(String args) ( LinkedList < Integer> числа = нов LinkedList< >() ; числа. добавяне (0, 20202); числа. добавяне (0, 123); числа. добавяне (0, 8283); ) Имаме празен LinkedList, в който вмъкваме някои числа. Трябва да оценим сложността на алгоритъма за вмъкване на едно число в LinkedList в нашия пример и как той зависи от броя на елементите в списъка. Отговорът ще бъде O(1) - постоянна сложност. Защо? Имайте предвид, че всеки път, когато вмъкваме число в началото на списъка. Освен това, както си спомняте, когато вмъкнете число в LinkedList, елементите не се движат никъде - връзките се предефинират (ако внезапно сте забравили как работи LinkedList, погледнете един от нашите). Ако сега първото число в нашия списък е числото x и вмъкнем числото y в началото на списъка, всичко, което е необходимо, е x. предишен = y; г. предишен = нула; г. следващ = x; За тази отмяна на връзката не ни интересува колко числа има в LinkedList сега- поне един, поне милиард. Сложността на алгоритъма ще бъде постоянна - O(1).

Логаритмична сложност

Без паника! :)Ако при думата „логаритмичен“ искате да затворите лекцията и да не четете повече, изчакайте няколко минути. Тук няма да има математически затруднения (има много такива обяснения на други места) и ще анализираме всички примери „на пръсти“. Представете си, че вашата задача е да намерите едно конкретно число в масив от 100 числа. По-точно да проверя дали изобщо го има. Веднага след като се намери желаното число, търсенето трябва да бъде спряно и на конзолата трябва да се изведе следният запис: „Желаният номер е намерен! Неговият индекс в масива = ....” Как бихте решили такъв проблем? Тук решението е очевидно: трябва да преминете през елементите на масива един по един, като започнете от първия (или от последния) и да проверите дали текущото число съвпада с това, което търсите. Съответно броят на действията зависи пряко от броя на елементите в масива. Ако имаме 100 числа, тогава трябва да преминем към следващия елемент 100 пъти и да проверим числото за съвпадение 100 пъти. Ако има 1000 числа, тогава ще има 1000 стъпки за проверка. Това очевидно е линейна сложност, НА). И сега ще добавим едно пояснение към нашия пример: масивът, в който трябва да намерите числото, е сортиран във възходящ ред. Променя ли нещо за нашата задача? Все още можем да търсим желания номер чрез груба сила. Но вместо това можем да използваме добре познатите двоичен алгоритъм за търсене.
В горния ред на изображението виждаме сортиран масив. В него трябва да намерим числото 23. Вместо да сортираме числата, просто разделяме масива на 2 части и проверяваме средното число в масива. Намираме числото, което се намира в клетка 4 и го проверяваме (втори ред на снимката). Това число е 16, а ние търсим 23. Сегашният брой е по-малък. Какво означава това? Какво всички предишни числа (които са разположени преди числото 16) не могат да бъдат проверени: определено ще са по-малко от това, което търсим, защото нашият масив е сортиран! Нека продължим да търсим сред останалите 5 елемента. Обърнете внимание: направихме само една проверка, но вече елиминирахме половината от възможните опции. Остават ни само 5 артикула. Ще повторим нашата стъпка - разделяме отново останалия масив на 2 и отново вземаме средния елемент (ред 3 на фигурата). Това число е 56 и е повече от това, което търсим. Какво означава това? Че отхвърляме още 3 варианта - самото число 56 и две числа след него (със сигурност са по-големи от 23, защото масивът е сортиран). Остават ни само 2 числа за проверка (последният ред на фигурата) - числа с индекси на масива 5 и 6. Проверяваме първото от тях и това е, което търсихме - числото 23! Индексът му = 5! Нека да разгледаме резултатите от нашия алгоритъм и след това да разгледаме неговата сложност. (Между другото, сега разбирате защо се нарича двоичен: същността му е в постоянното разделяне на данните на 2). Резултатът е впечатляващ! Ако търсим правилното число с линейно търсене, щяхме да имаме нужда от 10 проверки, а с двоично търсене пропуснахме 3! В най-лошия случай те биха били 4, ако на последната стъпка нужното ни число беше второто, а не първото. Какво ще кажете за неговата сложност? Това е много интересен момент :) Алгоритъмът за двоично търсене зависи много по-малко от броя на елементите в масива, отколкото алгоритъмът за линейно търсене (т.е. просто изброяване). При 10 елементи в масив, линейното търсене ще се нуждае от максимум 10 проверки, а двоичното търсене ще се нуждае от максимум 4 проверки. Разликата е 2,5 пъти. Но за масив в 1000 артикулалинейното търсене ще изисква 1000 проверки, а двоичното - общо 10! Разликата вече е 100 пъти! Обърнете внимание, че броят на елементите в масива се е увеличил с коефициент 100 (от 10 на 1000), докато броят на проверките, необходими за двоично търсене, се е увеличил само с коефициент 2,5, от 4 на 10. Ако получим да се 10 000 артикула, разликата е още по-впечатляваща: 10 000 проверки за линейно търсене и общо 14 проверкиза двоичен. И отново: броят на елементите се увеличи 1000 пъти (от 10 на 10 000), а броят на проверките се увеличи само 3,5 пъти (от 4 на 14). Сложността на алгоритъма за двоично търсене е логаритмична, или, използвайки Big-O нотация, - O(log n). Защо се казва така? Логаритъмът е обратен на степенуването. Двоичният логаритъм се използва за изчисляване на степента на число 2. Например, имаме 10 000 елемента, които трябва да сортираме с двоично търсене.
Сега имате картина пред очите си и знаете, че за това са ви необходими максимум 14 проверки. Но какво ще стане, ако няма картина пред очите ви и трябва да изчислите точния брой необходими проверки? Достатъчно е да отговорите на един прост въпрос: На каква степен трябва да се повдигне числото 2, така че полученият резултат да е >= ​​броя на елементите за проверка?За 10000 ще бъде 14-та степен. 2 на степен 13 е твърде малко (8192) Но 2 на 14-та степен = 16384, това число удовлетворява нашето условие (то е >= ​​броя на елементите в масива). Намерихме логаритъма - 14. Трябват ни толкова много проверки! :) Алгоритмите и тяхната сложност е твърде обширна тема, за да се побере в една лекция. Но да го знаете е много важно: в много интервюта ще получите алгоритмични задачи. За теория мога да ти препоръчам няколко книги. Можете да започнете с „Big-O video on YouTube. Ще се видим на следващите лекции! :)

Определяне на сложността на алгоритъм

Оценката на функцията на сложността, получена при асимптотичния анализ, се нарича сложност на алгоритъма.

Трябва да се има предвид, че има няколко оценки на сложността на алгоритъма.

Асимптотичното поведение на функцията за сложност е оперативната сложност. В допълнение към него можете да посочите следните видове трудности.

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

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

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

когнитивенсложност - характеристика на наличието на алгоритъм за разбиране от експерти в области на приложение.

Видове и означения на асимптотиката

При асимптотичния анализ на алгоритмите е обичайно да се използва нотацията на математическия асимптотичен анализ. В този случай се разглеждат три оценки (асимптотики) на сложността на алгоритмите, които се означават по следния начин:

• 1) /(i) = O^(n))- асимптотично точна оценка на функцията на сложност /(«), или оперативната сложност на алгоритъма;
• 2) /(n) = 0(§(n)) -асимптотично точна горна оценка на функцията на сложност /( П);
• 3) /(l) = ?2(#(l)) - асимптотично точна долна оценка на функцията на вложения труд /( П).

Вместо обозначение C1^(n))много често по-простият o(^(“)) се използва с буквата „o” с малки букви.

Нека обясним семантиката на формулите с пример: ако е написано / (n) = 0 (^2 (n)), ТОГАВА ТОВА означава, че функцията g(n)=og2 (н)е асимптотично точна оценка на функцията на сложност /(«). Всъщност има дефиниция с две позиции под формата на твърдение:

Ако f(n)= @(log2(")),

mo g(n)\u003d log 2 (l) - асимптотично точна оценка на f(n).

Обърнете внимание, че постоянният коефициент не влияе на реда на сложност на алгоритъма, така че основата на логаритъма се пропуска, когато се определя логаритмичната сложност, и те просто пишат f(l) = @(lо§(l)), което означава, че логаритъмът има произволна основа, по-голяма от единица.

Формални дефиниции на асимптотиката

Асимптотично точна оценка на функцията на трудоемкостс, с 2 , l 0 , така че за l>l 0 функцията /(l) с точност до постоянни множители не се различава от функцията g( k), тогава функцията g(n)се нарича асимптотично точна оценка на функцията /(k).

• 3 s], s 2 eИ, с х > 0, с 2 > 0:
  • (3 l 0 e K, l 0 > 0: (/l e K, l > l 0:0 g(n) /(l) = 0(?(l)),

където 9^, N са наборите от всички реални и естествени числа, съответно.

Асимптотично точна горна граница за функцията на сложностустно определени по следния начин: ако има положителни числа си l 0 , така че за l>l 0 функцията /(l) расте не по-бързо от функцията g(n)до постоянен фактор c, тогава функцията g(n)се нарича асимптотично точна горна граница за функцията Ap).

По-точно формално определение има формата:

• 3 сд %s > 0:
  • (3 l 0 e X, l 0 > 0: (/l e K, l > l 0:0 s? #(l))) 0(g(n))

Асимптотично точна долна граница за функцията на сложносттаустно определени по следния начин: ако има положителни числа си l 0 , така че за l>l 0 функцията /(l) расте не по-бавно от функцията g(n)до постоянен фактор с,тогава функцията?(k) се нарича асимптотично точна долна граница за функцията

По-точно формално определение има формата:

• 3 с e 9^, с > 0:
  • (3 i 0 e X, i 0 > 0: (/i e K, i > аз 0: 0 s? g(n)

/(аз) = 0.^(n))

Обърнете внимание на следното:

• 1) неравенствата, посочени във формалните дефиниции на асимптотиката, в общия случай могат да бъдат удовлетворени не от една, а от определен набор от функции, често с безброй набор от членове, така че конструкциите Q(g(n)), 0^(n))и 0.^(n))символизират набор от функции, с която се сравнява изследваната функция на вложения труд /(i); поради това в нотацията на асимптотиката на формата /(n) = 0(?(n)), /(/0 = 0(? max (n)), Dn) = ?2(? m1n (n )) вместо знака "= » би било по-рационално да се използва знакът "e";
• 2) дизайни (d^(n)), 0^(n))и ?1^(n)),използвани като обозначения за някои количества, трябва да се четат съответно, както следва: всяка функция, която е една и съща, растяща не по-бързо и не по-бавно g(n).

Съвпадение и разлика на асимптотиката

Нека обърнем внимание на следния факт: оценката /(s) = 0(?(s)) задава както горни, така и долни оценки за /(s), тъй като нейната дефиниция предполага валидността на връзката c g g(n)

Следното свойство на асимптотиката е съвсем очевидно: ако оценката φ(n) = ©^(n))съществува, тогава равенствата /( П) = 0(^(n)) и /(n) = ?2(#(n)), т.е. горната и долната оценка на интензивността на труда съвпадат една с друга; ако /(i) = 0(? max (i)) и φ(n) = C1^ mn (n)), и g max (n)Фg m 1n(i), тогава няма функция g(n),така че /(i) = 0(?(i)).

Съвпадението на горната и долната оценка на интензивността на труда е възможно в следните случаи:

• 1) функцията за сложност за всички стойности на входната дължина е детерминистична (неслучайна) функция, т.е. броят на извършените операции не зависи от спецификата на стойностите на първоначалните данни; такива са например функциите на зависимостта на броя на операциите умножение и деление от броя на неизвестните величини в алгоритъма за решаване на системи от линейни алгебрични уравнения по метода на IS разширение;
• 2) функцията на трудоемкостта е случайна функция, т.е. броят на извършените операции зависи от спецификата на първоначалните данни и (или) реда на тяхното получаване и можете да посочите функциите / m | n (s), / max (s), описващи минималните и максимална сумаоперации, изпълнявани от изпълнителя на алгоритъма за определена входна дължина i, но и двете функции имат едни и същи доминанти - например те са полиноми от един и същи ред.

Имайте предвид следните три важни правиласвързани с оценки от реда на оперативна сложност:

• 1) постоянните фактори нямат значение за определяне на реда на сложност, т.е. 0 (k? g(n)) = 0(g(")) ;
• 2) редът на сложността на произведението на две функции е равен на произведението на техните сложности, тъй като равенството е вярно:
• 0(gl(i) §2(i)) = 0 (?| (i)) 0 (#2(i)) ;
• 3) редът на сложност на сумата от функции е равен на реда на доминантата на членовете, например: 0(i e + n 2 + n) = 0 (i 5).

Горните правила използват символа само на една асимптотика 0("), но те са валидни за всички асимптотични оценки - и за 0( ) , и &.{ ).

В набора от елементарни функции можете да посочите списък с функционална доминация: ако е променлива, а,б-числови константи, тогава следните твърдения са верни: i" доминира i!; i! доминира а"; а"доминира Zj" ако a>b a pдоминира П b, ако а> 1 за всеки b e 9? ; n aдоминира а/ ако a>b i доминира log q(i) if а > 1.

Оценка на средната интензивност на труда

На практика ре При изчислителните изчисления е от значителен интерес да се оцени f(n) на математическото очакване на сложността на M, тъй като в преобладаващата част от случаите f(n) е случайна функция. Въпреки това, в процеса на експериментални изследвания на алгоритми със случайни f(n), допълнителен проблем- избор на броя опити за надеждна оценка на М. Преодоляването на този проблем е централна задача в . Предложеното решение се основава на използването на бета разпределението за приблизително /(n). Това е много конструктивна и универсална техника. Въпреки това, в съвременни условия, когато производителността на компютъра е достатъчно висока, в много случаи е възможно да се използва по-прост метод за избор на обхвата на тестовете, базиран на наблюдение на текущата променливост на стойностите f(n) -стойностите се оценяват, докато дисперсията на оценките стане по-малка от определената грешка.

Оценяване на оперативната сложност на алгоритъм

Сложността на даден алгоритъм може да се определи въз основа на анализа на неговите управляващи структури. Алгоритмите без цикли и рекурсивни извиквания имат постоянна сложност. Следователно дефинирането на сложността на алгоритъма се свежда главно до анализ на цикли и рекурсивни извиквания.

Помислете за алгоритъма за изтриване да се-ти елемент от масив с size П, състоящ се в преместване на елементите на масива от (до + 1) -та до П-върнете една позиция назад в началото на масива и намалете броя на елементите Пза единица. Сложността на цикъла за обработка на масива е О (п-к),тъй като се изпълнява тялото на цикъла (операция за преместване). настолен компютърпъти, а сложността на тялото на цикъла е 0(1), т.е. е константа.

В разглеждания пример сложността се характеризира с асимптотиката 0("), тъй като броят на операциите, изпълнявани в този алгоритъм, не зависи от спецификата на стойностите на данните. Функцията на сложността е детерминирана и всички видове асимптотики съвпадат една с друга: f(n) = Q(n-k), f(n) = 0(n-k)и f(n) = Q(n- до). Този факт се доказва от обозначението точно ©( ). Използвайте 0(*) и/или?2(*) само ако тези асимптотики се различават.

Типът цикъл (for, while, repeat) не влияе на сложността. Ако един цикъл е вложен в друг и двата цикъла зависят от размера на една и съща променлива, тогава цялата конструкция се характеризира с квадратична сложност. Влагането на повторения е основен фактор за растежа на сложността. Като пример представяме сложността на добре известни алгоритми за търсене и сортиране за масив с размер П:

• брой операции за сравнение при последователно търсене: 0(n);
• брой операции за сравнение при двоично търсене: 0 (дневник 2 П);
• брой операции за сравнение в метода на прост обмен (балонно сортиране): 0(n 2);
• брой операции на пермутация при балонно сортиране: 0 (н 2);

Обърнете внимание, че броят на операциите за сравнение в метода на простата размяна има асимптотиката 0 (н 2), а броят на операциите на пермутация има две различни асимптотики 0 (стр. 2)и?2(0), тъй като броят на сравненията не зависи от спецификата на стойностите на сортираните данни, докато броят на пермутациите се определя от тази специфика. Пермутациите може изобщо да не се извършват - ако масивът от данни е правилно подреден първоначално или броят на пермутациите може да е максимален - от реда П 2 , - ако сортираният масив първоначално е подреден в обратна посока.

Име на функцията g(n)в асимптотиката /(x) = @(x(x)) и /(a) = 0(g(n))функцията за сложност /(«) се използва за характеризиране на алгоритъма. Така се говори за алгоритми с полиномиална, експоненциална, логаритмична и т.н. сложност.

Функция на сложността 0 (1). В алгоритмите с постоянна сложност повечето от операциите в програмата се изпълняват един или повече пъти. Всеки алгоритъм, който винаги изисква (независимо от размера на данните) едно и също време, има постоянна сложност.

Функция на сложност 0(N).Времето на работа на програмата обикновено е линейно, когато всеки елемент от входните данни трябва да бъде обработен само линеен брой пъти. Тази функция на сложност характеризира прост цикъл.

Функция на сложност 0(N 2), 0(N 3), 0(№) - полиномиална функция на сложността: броят на операциите нараства пропорционално на квадрата Н.В общия случай може да има O(A^) в зависимост от сложността на проблема. Тази функция на сложност характеризира сложен цикъл.

Функция на сложността O(Дневник 2 (A0), 0 (Nдневник 2 (A0). Това е времето, когато работят алгоритми, които разделят голям проблем на много малки и след това, след като ги решат, комбинират решенията.

Функция на сложност 0(e N).Алгоритмите с експоненциална сложност най-често са резултат от подход, наречен груба сила.

Функция на сложност 0(M) -броят на операциите нараства пропорционално на факториела Н.

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

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

Например, разгледайте алгоритъм за обработка на елементи от масив.

За /": = 1 до н doBegin

Сложността на този алгоритъм О(A), защото тялото на цикъла се изпълнява A пъти и сложността на тялото на цикъла е 0(1). Ако един цикъл е вложен в друг и двата цикъла зависят от размера на една и съща променлива, тогава цялата конструкция се характеризира с квадратична сложност.

За /: = 1 до ннаправи За j:= 1 към н doBegin

Сложността на тази програма 0(N2).

Пример 1Нека оценим сложността на програма, която въвежда масив от клавиатурата и намира най-големия елемент в него. Алгоритъмът се състои от следните стъпки:

• - въвеждане на масив (необходимо е да се прочетат A елементи);
• - търсене на най-големия елемент (трябва да направите A - 1 сравнение);
• - извеждане на резултата (трябва да изведете едно число или низ).

Добавяме броя на операциите A + (A - 1) + 1 = 2A, т.е. съществува

такава константа, че за всяко A броят на операциите не превишава CA. Следователно сложността на алгоритъма е 0(A).

Пример 2Нека оценим сложността на програма, която въвежда масив от клавиатурата и намира в него елемент с дадено свойство (например равно на определена стойност). Алгоритъмът се състои от следните стъпки:

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

В най-добрия случай посоченият алгоритъм ще изисква A + 2 операции (въвеждане на целия масив, едно сравнение, изход), в най-лошия случай (когато няма такъв елемент, 2A + 1 операция). Ако А ще Голям брой, например около 10 6 , тогава единицата може да се пренебрегне. Следователно сложността на алгоритъма е 0(N).

Пример 3Нека дефинираме функцията за сложност на алгоритъма за криптиране за дума с дължина Лметод на заместване. Нека има таблица, в която за всеки знак от азбуката има знак, с който трябва да бъде заменен. Обозначете броя на буквите от азбуката С.Алгоритъмът се състои от следните стъпки:

• - въвеждане на дума (една операция);
• - организация на цикъла:
  • 1) за всеки знак намерете неговата замяна в таблицата (ако таблицата не е подредена и няма свойства, които улесняват търсенето, тогава в най-лошия случай ще е необходимо Соперации за един знак, ако необходимият елемент е в самия край);
  • 2) извеждане на намерения символ;
• - края на цикъла.

Общ брой операции 1 + (S+)L.В случай на достатъчно големи Си Лединици могат да бъдат пренебрегнати и се оказва, че функцията за сложност на горния алгоритъм е O(S L).

Пример 4Нека дефинираме функцията на сложност на алгоритъма за транслация на естествени числа 1 V в двоична системасмятане (без операции за въвеждане и извеждане на данни). Алгоритъмът се състои от следните стъпки:

• - цикъл, докато резултатът от деленето на число на 2 стане 0:
• - разделете числото на 2 и запомнете остатъка;
• - приемете резултата от деленето като ново число;
• - края на цикъла.

Общият брой операции не надвишава 1 + log 2 A. Следователно описаният алгоритъм има сложност 0 (og 2 N).