Сравнение массивов и связанных списков

Arrays

• A collection of elements of the same data type stored in contiguous memory locations
• Each element is identified by an index or key
• Operations:
  • Access: O(1)
  • Insertion: O(n)
  • Deletion: O(n)
• Advantages:
  • Fast access time
  • Efficient use of memory
• Disadvantages:
  • Fixed size
  • Slow insertion and deletion

Linked Lists

• A dynamic collection of elements, each of which points to the next element
• Operations:
  • Access: O(n)
  • Insertion: O(1)
  • Deletion: O(1)
• Advantages:
  • Dynamic size
  • Fast insertion and deletion
• Disadvantages:
  • Slow access time
  • More memory usage than arrays

Stacks

• A Last-In-First-Out (LIFO) data structure
• Operations:
  • Push: add an element to the top of the stack
  • Pop: remove the top element from the stack
  • Peek: access the top element without removing it
• Implementations:
  • Using arrays
  • Using linked lists
• Applications:
  • Evaluating postfix expressions
  • Implementing recursive algorithms

Queues

• A First-In-First-Out (FIFO) data structure
• Operations:
  • Enqueue: add an element to the end of the queue
  • Dequeue: remove the front element from the queue
  • Peek: access the front element without removing it
• Implementations:
  • Using arrays
  • Using linked lists
• Applications:
  • Job scheduling
  • Print queues

Hash Tables

• A data structure that maps keys to values using a hash function
• Operations:
  • Insert: add a key-value pair
  • Search: find a value by its key
  • Delete: remove a key-value pair
• Collision resolution techniques:
  • Chaining
  • Open addressing
• Advantages:
  • Fast search and insertion
  • Efficient use of memory
• Disadvantages:
  • Sensitive to hash function quality
  • Collision resolution can be slow

Массивы

• Коллекция элементов одного типа данных, хранящихся в liềnких местоположениях памяти
• Каждый элемент идентифицируется индексом или ключом
• Операции:
  • Доступ: O(1)
  • Вставка: O(n)
  • Удаление: O(n)
• Преимущества:
  • Быстрый доступ к элементам
  • Эффективное использование памяти
• Недостатки:
  • Фиксированный размер
  • Медленная вставка и удаление элементов

Связные Списки

• Динамическая коллекция элементов, каждый из которых ссылается на следующий элемент
• Операции:
  • Доступ: O(n)
  • Вставка: O(1)
  • Удаление: O(1)
• Преимущества:
  • Динамический размер
  • Быстрая вставка и удаление элементов
• Недостатки:
  • Медленный доступ к элементам
  • Более интенсивное использование памяти, чем в массивах

Стеки

• Структура данных Last-In-First-Out (LIFO)
• Операции:
  • Push: добавить элемент в верхнюю часть стека
  • Pop: удалить верхний элемент из стека
  • Peek: доступ к верхнему элементу без удаления
• Реализации:
  • С помощью массивов
  • С помощью связных списков
• Применения:
  • Оценка постфиксных выражений
  • Реализация рекурсивных алгоритмов

Очереди

• Структура данных First-In-First-Out (FIFO)
• Операции:
  • Enqueue: добавить элемент в конец очереди
  • Dequeue: удалить.front элемент из очереди
  • Peek: доступ к front элементу без удаления
• Реализации:
  • С помощью массивов
  • С помощью связных списков
• Применения:
  • Планирование задач
  • Очереди печати

Хеш-таблицы

• Структура данных,mapping keys to values using a hash function
• Операции:
  • Insert: добавить пару ключ-значение
  • Search: найти значение по ключу
  • Delete: удалить пару ключ-значение
• Техники разрешения коллизий:
  • Чейниг
  • Открытое адресование
• Преимущества:
  • Быстрый поиск и вставка
  • Эффективное использование памяти
• Недостатки:
  • Чувствительность к качеству функции хеширования
  • Разрешение коллизий может быть медленным

Структуры данных

Массивы

• Коллекция элементов одного типа, хранящихся в непрерывных областях памяти
• Каждый элемент идентифицируется индексом или ключом
• Операции: обход, вставка, удаление, поиск, сортировка

Списки

• Динамическая коллекция элементов, где каждый элемент (узел) ссылается на следующий узел
• Операции: обход, вставка, удаление, поиск
• Преимущества: эффективная вставка и удаление, гибкий размер
• Недостатки: медленный поиск, большее использование памяти

Стеки

• Структура данных Last-In-First-Out (LIFO)
• Операции: push, pop, peek
• Используется для: синтаксического анализа, вычисления hậuфиксных выражений, реализации рекурсивных алгоритмов

Очереди

• Структура данных First-In-First-Out (FIFO)
• Операции: enqueue, dequeue, peek
• Используется для: планирования задач, очередей печати, сетевых протоколов

Деревья

• Иерархическая структура данных, где каждый узел имеет значение и от 0 до N дочерних узлов
• Операции: обход, вставка, удаление, поиск
• Типы: бинарные деревья, AVL-деревья, BST, кучи

Графы

• Нелинейная структура данных, где узлы соединены ребрами
• Операции: обход, вставка, удаление, поиск
• Типы: взвешенные, невзвешенные, направленные, ненаправленные

Алгоритмы

Алгоритмы сортировки

• Сортировка пузырьком: итеративная, перестановка соседних элементов
• Сортировка выбором: итеративная, выбор наименьшего элемента
• Сортировка вставкой: итеративная, вставка элементов в отсортированный список
• Сортировка слиянием: рекурсивная, слияние отсортированных списков
• Быстрая сортировка: рекурсивная, разбиение списка на части

Алгоритмы поиска

• Линейный поиск: итеративный, проверка каждого элемента
• Бинарный поиск: рекурсивный, поиск в отсортированном списке

Алгоритмы графа

• Поиск в ширину (BFS): обход графа LEVEL by level
• Поиск в глубину (DFS): обход графа с максимальной глубиной
• Алгоритм Дейкстры: поиск кратчайшего пути в взвешенном графе

Динамическое программирование

• Разбиение задачи на小альные подзадачи
• Решение каждой подзадачи только раз, хранение результатов
• Используется для: ряда Фибоначчи, нахождения самой длинной общей подпоследовательности, проблемы рюкзака

Анализ алгоритмов

Сложность времени

• Обозначение О-большое: верхняя граница сложности времени
• Обозначение Ω-小ое: нижняя граница сложности времени
• Обозначение θ-정альное: точная граница сложности времени

Сложность пространства

• Обозначение О-большое: верхняя граница сложности пространства
• Обозначение Ω-小ое: нижняя граница сложности пространства
• Обозначение θ-정альное: точная граница сложности пространства