дъсъааа 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; в сравнение със сингли позволява преминаване през структурата и в двете посоки което със сингли не е възможно; триенето също е по лесно отколкото в сингли; листът лесно се преобръща; НО използва повече памет
Потенциални приложения на doubly-linked list
- в системи за ннавигация където трябва да изчисли пътя натам и обратно
- в браузъри за back & forward бутон
- undo/ redo
- за да представя тесте от карти в игра
- или като цяло различните състояния в игра
Листовете в джава
List е общия интерфейс за всички лист типове; ArrayList & LinkedList са две често срещани негови имплементации; има също вектор, който е дърт
ArrayList в джава
Имплементация, която пази елементите в масив; размерът на масива се уголемява автоматично когато няма достатъчно място при добавяне на елемент в листа; можем да зададем какъв да ни е първоначалния размер при създаването на лист (ако не зададем просто е дефолтния);
!!! най подходящ когато ни трябва бърз и произволен достъп до елементи
LinkedList в джава
Имплементация, която пази елементите в doubly-linked list структура.
!!! най-подходящ ако искаме бързо да добавяме и премахваме елементи в края на лист (единствено в това отношение е по добър от arraylist)
стек - ко и туй
лифо структура (последния влезнал е първия излезнал); елементите се вкарват (или пушват) на върха (top) и се махат (или поп-ват) от върха (top);
много алгоритми ползват скатове; може да се имплементира чрез масив, arraylist или linked list (последното е може би най добрия вариант)
стек базиран на масив
настоящия индекс (или с др. думи топ-а) се движи наляво или надясно с всеки поп или пуш; има отделна променлива която следи кой е индекса на топ-а; лошото е че масивът може да се напълни
всички операции са О(1) стига топ-а да е винаги най-големия ползван индекс; не се налага местене на елементите;
стек базиран на arraylist
отново всички операции са константни стига опашката на листа да е топ-а на стека;
!!! изключение: пуш би бил линейна операция ако се налага уголемяване на листа (в случай че е запълнен)
стек базиран на linkedlist
всеки нод си има стойност и референция към следващия нод; има специална променлива която държи референцията към топ-а; пуш създава нов нод и променя топ-а да сочи към него; операциите са константни; топ-а реално е head на линкдлиста (а ако ползваме дъбли, значи и тейла може да е топ)
кога ползваме стек
- например виртуалната машина на джава следи кои са активните методи с помощта на стек
- да обърнем дума
- проверка на скоби (дали са отворени и затворени правилно)
- бек функционалността в браузърите например
джава стек
имплементира стек с помощта на arraylist - т.е. ако масивът се запълни го удвоява, но ако намалим използваните позиции масивът никога няма да се смали
3 основни метода: push(добавя нов елемент на топ-а), pop (маха елемента от топ-а и го връща) и peek (връща елемента от топ-а без да го маха)
в джава стек-а наследява вектор, а вектор наследява лист, така че със стека може да се изпълняват същите операции които и с лист…което е странно…т.е. мога да декларирам стека като лист и после да го третирам като стек или лист в зависимост какво ми се прави?
!!! според джава докумунтацията е за предпочитане вместо стек да ползваме имплементации на deque интерфейса (например ArrayDeque) защото съдържа по-пълен списък с LIFO операции
https://docs.oracle.com/javase/7/docs/api/java/util/Stack.html
опашка - ко и туй
фифо структура (първия добавен е и първия който се премахва); нови елементи се добавят на края на опашката (нарича се enqueue/ offer), а премахването става от началото й (dequeue/poll); може да се импленетира с масив, arraylist или линкдлист
опашка - операции
- имплементация базирана на масиав:
peek - константна (виждаме елемента начело на опашката)
enqueue - константна освен ако размерът на масива трябва да се уголеми, тогава е линейна
dequeue - линейна, защото всички оставащи елементи трябва да се премахнат - базирана на линкдлист:
всички операции са константни при случай че имаме променлива за хед и тейл
Джава интерфейс опашка операции
offer - добавя нов елемент на края на опашката
пол - маха елемент от началото на опашкта
пийк - връща елемента в началото на опашката без да го маха
има две популярни имплементации:
- линкдлист - тук опашката е имплементирана с двойно свързан лист
- арейдек - по-бърз е, тук опашката е имплементирана с кръгов масив
!!! всеки метод съществува в два варината - единият връща exception ако операцията се провали, а другият връща стойност
