Всеки път, когато се справяте с проблем в кода, има голям шанс решението, което измислите, да не е идентично с решенията, до които са стигнали други разработчици. Може би един разработчик обича да създава карти на символи, докато друг харесва сортиране с балончета. В зависимост от това върху какво работите, това МОЖЕ (забележете капачките там) да не е голяма работа. В много случаи обаче трябва да обърнете внимание кое точно решение избирате. Защо? Не е ли смисълът просто да разрешите проблем, без значение как е направен? Очевидно, тъй като задавам въпроса, отговорът е очевидно не… вие не търсите просто решаване на проблем. Вие търсите как НАЙ-ДОБРО да решите проблема.

И така, как разработчиците определят кое е „най-доброто“ решение? Въведете нещо, наречено Runtime Complexity, което се използва за описание на производителността на алгоритъм. Всеки път, когато определяте как да решите проблем с кодирането, вие търсите да изберете НАЙ-ЕФЕКТИВНОТО решение по отношение на производителността. Винаги трябва да се питате: колко повече процесорна мощност ще е необходима, за да стартирам избрания от мен алгоритъм или решение, ако броят на входовете в този алгоритъм се увеличи?

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

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

Нека да разгледаме друг пример, който илюстрира какво се случва в другия край на спектъра на сложност, с нещо, което изисква повече процесорна мощност. Виждал съм това, наречено проблем със „стъпките“, където ви е дадено положително цяло число, N. Вашата работа е да напишете функция, която приема N и конзолата регистрира форма на стъпка с N нива, използвайки знака „#“… там трябва да има интервали от дясната страна за всички стъпки с по-малко от N брой знака „#“.

Ето итеративното решение на този алгоритъм:

Какъв вид сложност на времето за изпълнение илюстрира това? Е, какво се случва всеки път, когато увеличим броя на „стъпките“, които преминаваме към нашата функция?

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

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

Някои често срещани времена на изпълнение и примери… и, о, да, нотация Big(O).

Кратка бележка преди да разгледате примерите. Когато говорим за сложност по време на изпълнение, може също да видите това като Big(O) нотация. Този тип нотация е това, което обикновено се вижда в академичния свят, когато се говори за ефективността на програмните решения. Нарича се „Голям(О)“, защото буквално пишете голямо О с малко уравнение, за да опишете сложността на решението.

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

Постоянен. Без значение какъв е нашият принос, винаги ще отнеме точно същото време. Това е „свещеният граал“ на кода, но почти никога не се случва. Можете да си представите пример за това като винаги да трябва да отпечатвате само първия елемент от колекция, без значение колко дълга е колекцията. В нотация Big(O) това е представено като O(1).

Логаритмичен. Този тип сложност се открива, ако удвоим входа, но количеството работа, което вършим, не се удвоява точно. Пример за това е търсенето в сортирани данни. В нотация Big(O) това се представя като O(log(n)).

Линеен. Това е най-често срещаният тип сложност. Ще видите това, ако итерирате през една фиксирана колекция от данни; например, ако използвате for цикъл, който работи от нула до array.length. В нотация Big(O) това се представя като O(n). Освен това, ако итерирате през две различни колекции с отделни for цикли, можете да изразите това като: O(n + m).

Квазилинейно. Този тип сложност се наблюдава, ако при увеличаване на входа с 1 количеството работа се увеличи с 1 плюс малко количество (така че не линейно, но не съвсем двойно). Това е сложността, проявена от много различни алгоритми за сортиране. В нотация Big(O) това се представя като O(n*log(n)).

Квадратичен. Ще видите тази сложност, когато всеки елемент в колекция трябва да бъде сравнен с всеки друг елемент. С други думи, докато увеличавате въвеждането, отнема значително повече време за завършване на алгоритъма. Спомнете си нашето решение за алгоритъм „стъпки“… този тип сложност се наблюдава, когато имате два вложени цикъла for, които повтарят една и съща колекция. В нотация Big(O) това се представя като O(n²).

Експоненциален. И накрая, този тип сложност се наблюдава, ако за всеки добавен елемент мощността на обработка се УДВОИ. Това очевидно е значително увеличение на процесорната мощност и вие НАИСТИНА не искате това. В нотация Big(O) това се представя като O(2^n).

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

Приятно кодиране!