дъсъааа Flashcards
какво е алгоритъм
поредица от стъпки които трябва да бъдат изпълнени за да се реши някакъв проблем; абстрактно описание на процес, възможно най-генерализирано
разлика между програма и алгоритъм
програмата е конкретна имплементация на алгоритъм
кога един алгоритъм е правилен?
когато резултатът му е верен всеки път независимо от входните данни; за един проблем може да има повече от един правилен алгоритъм, но “цената” на всеки алгоритъм (т.е. количеството ресурси които употребява - време, пространство) може да се различава
Какво означава сложност на алгоритъм?
Сложността е количеството време и пространство, които са нужни, за да се изпълни алгоритъмът; различните алгоритми имат различни сложности; сложността на алгоритъма не е равна на броя стъпки, които той съдържа;
алгоритмична сложност = брой примитивни операции, които алгоритъмът съдържа
Какво означава да анализираме един алгоритъм
– да предвидим ресурсите, които са нужни за да се изпълни (напр. сметачно време - процесор; пространстово в паметта - RAM; интернет); да можем да анализираме един алгоритъм означава да си задаваме въпроса - как ще се държи този алгоритъм, ако трябва да обработи повече входни данни?
тъй като пространството не е проблем като ресурс (благодарение на технологичния ни напредък), когато анализираме алгоритми се концетрираме върху времето - сложността на един алгоритъм всъщност се определя от общия брой примитивни операции, които той трябва да изпълни
Как мерим алгоритмичната сложност
Алгоритмичната сложност е приблизителното изчисление на броя стъпки, които ще направи алгоритъмът, в зависимост от размера на входните данни.
какво е asymptotic notation
начин да преценим сложността на един алгоритъм абстрахирайки се от външни фактори които му влияят (като например мощността на машината на която се изпълнява); най-често за целта се разглежда най-лошия случай (т.е. най-многото данни, през които би се наложило да мине алгоритъмът) - за целта винаги вземаме предвид действието с най-висока степен; това не е точно измерване, а относителна преценка
Типични видове сложност (6)
константа (не зависи от входните данни) - О(1);
логаритмична (някви матемачитески лоши неща)
линейна (равна на размера на входните данни) - О(n) – например цикъл
квадратична – например вложен цикъл
кубична – например два вложени цикъла
експоненциалнаО(2^n)
масив - характеристики
линейна структура от данни
има фиксирана дължина
елементите в масива се поставят в паметта eдин до друг
хомогенни са - съдържат един тип данни
време за достъпване - О(1) т.е. константно (защото елементите в масива са индексирани)
време за търсене - O(n) ; за бинарно търсене (ако масивът е сортиран) е O(log n)
разлика между абстрактен тип данни и структура от данни
- абстрактният тип от данни е тип определен от неговото поведение (а не имплементация); например лист, стек, опашка, мап
- структурата от данни е конкретната имплементация на абстрактен тип от данни - например масив, linked list, hash table
Листове - общи характеристики
- линейна абстрактна структура от данни
- съдържа последователност от подредени елементи
- елементите може да се срещат повече от веднъж
- размерът може да се променя
- ползволява да достъпваме елемент по неговата позиция (индекс)
Singly-linked list - ко и туй?
Конкретна структура от данни която се състои от последователност от нодове; всеки нод пази две нека - елемента (някаква стойност) и адреса на следващия нод
head сочи към първия нод - това е едниствения ни начин да достъпваме този лист
Singly linked list - възможни операции
- addHead, removeHead, retrieveHead - O(1)
- addTail, retrieveTail са О(1) ако имплементацията има променлива коят опази адреса на опашката; иначе са O(n)
- removeTail - O(n) защото трябва да мине през всички нодове за да стигне до предпоследния и да промени неговата референция на Null
- операциите за достъпване на някой нод по неговата позиция (add, remove, replace, retrieve) са O(n) (защото в най лошия случай би се наложило да минат през целия лист)
- операциите за достъпване на някой нод по неговата стойност (find, remove) са O(n) отново поради същата причина
- за да добавим нод в началото правим нов нод и правим референцията му да сочи към стария head
- за да добавим нод в края правим нов нод, слагаме в референцията на последния нод да соци към новия, а новия в референцията си да има null
- за да добавим нов нод някъде по средата - правим си новия нод; променяме референцията му да сочи към нода който искаме да е след него; променяме референцията на нода преди новия нод да сочи към новия нод
Singly linked list - преимущества (4) и недостатъци (3)
- преимущества: лесно се имплементира; вкарването и триенето на елемент е “евтино” (не се налага всички останали елементи да се преместват както е с масива); може лесно да отделя или освобождава нова памет по време на изпълнение (когато никоя референция вече не сочи към определен елемент той просто се изтрива от garbarge collector-а); една от най ефективните структури от данни в сручай че ни трябва прекосяване на листа в една посока
- недостатъци: използва повече памет в сравнение с масив (нодовете са винаги цели обекти с няколко полета); тъй като елементите не се намират един до друг отнема повече време да достъпим конкретен елемент от листа; изизсква линейно време за премахване на последния елемент (което е повече от другите структури от данни)
Doubly-linked list
същото като сингли, но всеки нод има и поле където се пази референция към предишния нод; има си head и tail; в сравнение със сингли позволява преминаване през структурата и в двете посоки което със сингли не е възможно; триенето също е по лесно отколкото в сингли; листът лесно се преобръща; НО използва повече памет
