Algorithms Analysis & Linear Data Structures Flashcards
What is algorithm and algorithm complexity?
- Алгоритъм: последователност от стъпки за решаване на даден проблем или задача.
- Две основни характеристики: сложност и коректност (дали връща правилен резултат)
- Сложност на алгоритъма: оценка на ресурсите (време и памет), които алгоритъмът изисква, в зависимост от размера на входните данни.
Два основни типа сложност:
- Времева сложност: колко време отнема изпълнението на алгоритъма.
- Пространствена сложност (място в паметта): колко памет е нужна на алгоритъма.
Why is algorithm analysis important?
- показва какви ресурси са нужни за алгоритъма (Време и място в паметта)
- показва как се държи алгоритъмът при по-голям обем от входни данни
How do we measure algorithm complexity?
- асимптотична нотация (Big O) - “O” is the order of the function
- време за изпълнение - брой примитивни операции, които извършва алгоритъмът за единица време (зависи от обема входни данни)
- не се интересуваме каква точно е f(n), а тенденцията, когато расте n по отношение на най-високия член на функцията
Which are the typical complexities and give example for each of them?
- O(1) (Константна): времето не зависи от размера на входа.
Пример: достъп до елемент в масив. - O(log n) (Логаритмична): сложността нараства логаритмично с размера на входа.
Пример: двоично търсене. - O(n) (Линейна): сложността нараства пропорционално на размера на входа.
Пример: обхождане на масив. - O(n log n) (Линейно-логаритмична): често срещана в сортиращи алгоритми.
Пример: merge sort, quicksort (в най-добрия случай). - O(n²) (Квадратична): сложността нараства с квадрата на размера на входа.
Пример: сортиране с балончета (bubble sort). - O(2^n) (Експоненциална): сложността нараства експоненциално с увеличаване на входа.
Пример: решаване на проблеми с рекурсия и множество варианти (като проблема с Хановите кули). - O(n!) (Факториална): най-бавната сложност, нараства изключително бързо.
Пример: решение на задачи за пермутации, като проблема на пътешественика (Traveling Salesman Problem).
What is the difference between abstract data type and data structure?
- абстрактни типове данни - Дефинира се от своето поведение, А НЕ от имплементация (List, Stack, Queue, Set, Map, Tree)
- структури от данни - конкретна имплементация на абстрактна структура от данни (Array, Linked List, Hash Table)
What is a linear data type and give examples?
Линейни типове данни: структури, при които елементите са подредени последователно, и всеки елемент има точно един предходен и един следващ (с изключение на първия и последния елемент).
Примери:
- Масив (Array): последователно подредени елементи в паметта.
- Свързан списък (Linked List): елементи, които съдържат връзка към следващия елемент.
- Стек (Stack): LIFO (Last In, First Out) структура, при която последно добавеният елемент се извлича първи.
- Опашка (Queue): FIFO (First In, First Out) структура, при която първият добавен елемент се извлича пръв.
Тези типове данни запазват реда на елементите и позволяват последователен достъп.
What is a linked list?
- линейна структура от данни, наподобяваща верига от node-ове, която може да се използва за имплементация на различни структури от данни
- когато подаваме LinkedList на метод, подаваме първия node
- Nodes - съдържат някаква данна + връзка със съседните Nodes
What are the two major implementations of a linked list?
Двете основни имплементации на свързан списък са:
- Еднопосочен свързан списък (Singly Linked List):
- Всеки node съдържа данни и указател към следващия node.
- Обхождането става само в една посока (от началото към края на списъка).
- head - сочи към първия node - Двупосочен свързан списък (Doubly Linked List):
- Всеки node съдържа данни, указател към следващия node и указател към предходния node.
- Обхождането може да става в двете посоки (напред и назад).
- head - сочи към първия node
- tail - сочи към последния node
Разлики:
- Еднопосочен: по-малко памет, по-лесен за реализиране.
- Двупосочен: по-гъвкав за операции, които изискват достъп до предходния елемент.
What is the complexity of the linked list’s operations?
Сложността на операциите със свързан списък зависи от типа на списъка (еднопосочен или двупосочен) и от конкретната операция:
1. Singly Linked List Operations
- Add/remove/access head – O(1)
- Add/access tail
-> If we have reference to the tail (operation optimization) – O(1)
-> Otherwise, we need to traverse the list – O(n)
- Remove tail – O(n)
-> We need to find the second-last
- Access element by index – O(n)
-> We need to traverse all previous elements
- Search element by value – O(n)
-> We need to traverse the whole list
2. Doubly Linked List Operations
- Add/remove/access head – O(1)
- Add/remove/access tail – O(1)
- Access element by index – O(n)
- Search element by value – O(n)
What is stack and what is the complexity of the different implementations?
Стек (Stack): линейна структура от данни, която следва принципа LIFO (Last In, First Out). Това означава, че последният добавен елемент е първият, който се извлича.
Основни операции:
- Push: добавя елемент към стека.
- Pop: премахва и връща елемента от върха на стека.
- Peek/Top: връща елемента на върха на стека без да го премахва.
- isEmpty: проверява дали стекът е празен.
Имплементации на стека:
1. Масив (Array):
- Push: O(1) (добавяне на елемент на върха на стека); премества top надясно
- Pop: O(1) (премахване на елемент от върха на стека).;
премества top наляво
- Peek/Top: O(1) (достъп до елемента на върха на стека).
- isEmpty: O(1).
- има променлива, която следи за индекса на top елемента
- Свързан списък (Linked List):
- Push: O(1) (добавяне на нов node в началото (head) на свързания списък).
- Pop: O(1) (премахване на node от началото (head) на свързания списък).
- Peek/Top: O(1) (достъп до node на върха на свързания списък).
- isEmpty: O(1).
- head на листа е top на stack-a
What is a queue and what is the complexity of the different implementations?
Опашка (Queue): линейна структура от данни, която следва принципа FIFO (First In, First Out). Това означава, че първият добавен елемент е първият, който се извлича.
Основни операции:
- Enqueue: добавя елемент в края на опашката.
- Dequeue: премахва и връща елемента от началото на опашката.
- Peek/Front: връща елемента в началото на опашката без да го премахва.
- isEmpty: проверява дали опашката е празна.
Имплементации на опашка:
1.Масив (Array):
- Enqueue: O(1) (добавяне на елемент в края на опашката); измества tail надясно
-> O(n) при resize на масива.
- Dequeue: O(n) (премахване на елемент от началото на опашката, тъй като елементите трябва да бъдат преместени наляво (O(n))).
- Peek/Front: O(1) (достъп до елемента в началото на опашката).
- isEmpty: O(1).
- има променливи, които следят за индексите на head и tail елементите
- Свързан списък (Linked List):
- head на листа е head на queue-то.
- tail на листа е tail на queue-to.
- Enqueue: O(1) (добавяне на нов node в края (tail) на свързания списък).
- Dequeue: O(1) (премахване на node от началото (head) на свързания списък).
- Peek/Front: O(1) (достъп до node в началото на свързания списък).
- isEmpty: O(1).
Stack in Java
- Stack е клас в Java, който имплементира List interface (Collection & Iterable interfaces)
- If the number of added elements exceeds the total Stack size, it will be doubled automatically. However, its size will never shrink after removing elements.
- Implements the stack data structure using an array
- E push(E item) → adds at the top O(1)(when resizing O(n))
- E pop() → removes and returns from the top O(1)
- E peek() → returns from the top O(1)
Queue in Java
- Queue е interface в Java
- boolean offer/add(E item) → adds at the tail
- E poll/remove() → removes and returns from the head
- E peek/element() → returns from the head
- Two popular implementations
-> LinkedList – Queue implemented with doubly linked list
-> ArrayDeque – Queue (double ended) implemented with circular array - faster
