Skip to content

Алгоритмы и структуры данных

🧠 Алгоритмы и структуры данных

Этот раздел поможет разобраться с основами алгоритмов и структур данных — ключевыми элементами программирования, необходимыми каждому разработчику.

📚 Что такое алгоритмы?

Алгоритм — это последовательность шагов, предназначенная для решения определённой задачи. Хороший алгоритм эффективно использует память и время выполнения.

Примеры:

  • Сортировка массива
  • Поиск элемента в списке
  • Обход графа
  • Шифрование данных

🗂️ Основные характеристики алгоритмов:

Характеристика Описание
Корректность Работает ли алгоритм правильно на всех входных данных
Эффективность Как быстро работает и сколько памяти использует
Читаемость Насколько понятен код алгоритма
Масштабируемость Как алгоритм ведёт себя при увеличении объёма данных

⏱️ Временная сложность (Big O)

Описывает зависимость времени работы программы от размера входных данных.

Сложность Пример Пояснение
O(1) Доступ к элементу массива Константное время
O(log n) Бинарный поиск Логарифмическое время
O(n) Линейный поиск Линейное время
O(n log n) Сортировка слиянием Чуть больше линейного
O(n²) Вложенные циклы Квадратичное время
O(2ⁿ) Рекурсивный факториал Экспоненциальное время

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

Структура данных — это способ хранения и организации информации так, чтобы её можно было эффективно использовать.

1. Массив (Array)

  • Фиксированная длина
  • Доступ за O(1)
  • Пример: int[] numbers = {1, 2, 3};

2. Список (List / LinkedList)

  • Может динамически расти
  • Вставка/удаление быстрее, чем в массивах
  • Пример: List<string> names = new List<string>();

3. Стек (Stack)

  • LIFO — Last In First Out
  • Используется в рекурсии, браузерном истории
  • Пример: Stack<int> stack = new Stack<int>();

4. Очередь (Queue)

  • FIFO — First In First Out
  • Используется в потоках, обработке задач
  • Пример: Queue<int> queue = new Queue<int>();

5. Хэш-таблица (Dictionary / HashMap)

  • Пары ключ-значение
  • Доступ за O(1)
  • Пример: Dictionary<string, int> ages = new Dictionary<string, int>();

6. Дерево (Tree)

  • Иерархическая структура
  • Применяется в файловых системах, базах данных
  • Частный случай: двоичное дерево поиска

7. Граф (Graph)

  • Узлы и связи между ними
  • Применяется в соцсетях, картах, маршрутизации

🔍 Распространённые алгоритмы

Тип алгоритма Примеры Описание
Сортировка Bubble Sort, Quick Sort, Merge Sort Упорядочивание данных
Поиск Линейный, бинарный Нахождение элемента
Графовые BFS, DFS, Dijkstra Обход и анализ графов
Динамическое программирование Fibonacci, Knapsack Разбиение задачи на подзадачи
Жадные алгоритмы Huffman coding, задача о рюкзаке Выбор локально оптимального решения

💡 Пример: Бинарный поиск

def binary_search(arr, target):
    low = 0
    high = len(arr) - 1
    while low <= high:
        mid = (low + high) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1

📘 Полезные книги

  • «Грокаем алгоритмы» — Адитья Бхаргава (для новичков)
  • «Алгоритмы: построение и анализ» — Кормен, Лейзерсон, Ривест, Штайн
  • «Программируем коллективно» — Джон Сиджу

🌐 Полезные ресурсы

🎯 Совет: Не учите всё сразу. Начните с простых алгоритмов и структур данных, а затем постепенно углубляйтесь.