Сложността на прости алгоритми и структури от данни в JS

В предишната статия „Стъпка към изчисляването като наука: опростени алгоритми и структури от данни в JS“, обсъдихме прости алгоритми (линейни и двоични търсения; балон, сортиране на избор и вмъкване) и структури от данни (обединени обекти с масив и ключ-стойност) ). Тук продължавам с концепцията за сложността и нейното приложение към тези алгоритми и структури от данни.

Сложност

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

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

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

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

Независимо дали изнасяте боклука или прахосмукирате стая , може да кажете, че броят на операциите ( O ) се увеличава точно с броя на елементите ( n ) . Ако имам 1 торба за боклук, трябва да извадя боклука веднъж. Ако имах 2 торби за боклук, трябва да изпълня една и съща задача два пъти, ако приемем, че физически не можете да вдигнете повече от една торба наведнъж. И така, Big-O на тези задължения е O = n или O = функция (n) или O (n) . Това е линейна сложност (права линия с 1 операция: 1 кореспонденция на елемент). И така, 30 операции се изпълняват върху 30 елемента (жълта линия на графиката).

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

Търсения

Линейно търсене

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

Двоично търсене

За двоично търсене най -добрият случай е O (1), което означава, че елементът от вашето търсене се намира в средната точка. Най -лошият и среден случай е log base 2 от n или:

Логаритъмът или дневникът е начин за изразяване на степен за дадена основа. Така че, ако имаше 16 елемента (n = 16), тогава в по-лошия случай ще са необходими 4 стъпки, за да се намери числото 15 (степен = 4).

Или просто: O (log n)

Сортира

Балон

При сортиране на балончета всеки елемент се сравнява с останалата част от колекцията, за да се определи най-високата стойност за балонче. Поради тази причина, средно до най-лошия случай , сложността му е O (n²) . Помислете за цикъл, вложен в друг цикъл.

Така че, за всеки елемент, вие го сравнявате с останалата част от вашата колекция. Това възлиза на 16 сравнения (или операции) за 4 елемента (4² = 16). Най -добрият случай е, ако вашата колекция е почти сортирана, с изключение на един елемент. Това би представлявало един кръг сравнения. Тоест, четири сравнения са необходими, за да се издигне член на колекция от четири елемента, което е сложност на O (n) .

Избор

За разлика от сортирането на балончета , вместо да балонира най-високата стойност, сортирането за избор избира най-ниската стойност, за да я замени на най-ранните позиции. Но тъй като изисква сравняване на всеки елемент с останалата част от колекцията, той също има сложност на O (n²) .

Вмъкване

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

Структури на данни

Масиви

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

Също така, тъй като промяна или unshift на стойност или от предната страна масив изисква Повторно индексиране всеки елемент, който следва (т.е. отстраняване на елемент с индекс 0 изисква повторно етикетиране елемент с индекс 1, както е индекс 0, и т.н.), те трябва сложност на O (n) . Преназначването се извършва от началото до края на масива.

Ключ - Стойност на сдвоени обекти

Достъпът , вмъкването или премахването на стойност чрез използване на ключ е мигновено и затова те имат сложност на O (1) . Търсенето във всеки „депозит“ за конкретен артикул с помощта на всеки наличен ключ е по същество линейно търсене . И така, има сложност на O (n) .

Заключение

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

Справка:

//www.udemy.com/js-algorithms-and-data-structures-masterclass/