Алгоритмы

Алгоритмы

Общее понимание

Определение:

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

Свойства:

• Конечность: Алгоритм должен завершаться за конечное число шагов.
• Определённость: Каждая инструкция должна быть ясной и не допускать двусмысленности.
• Эффективность: Алгоритм должен быть выполним с использованием доступных ресурсов за приемлемое время.
• Ввод: Алгоритм может принимать входные данные.
• Вывод: Алгоритм должен выдавать результат.

Основные Алгоритмические Конструкции

• Последовательное выполнение: Инструкции выполняются одна за другой в заданном порядке.

   ```
   Инструкция 1;
   Инструкция 2;
   Инструкция 3;
   ```

Ветвление (Условные операторы):

Выполнение инструкций зависит от выполнения определенного условия.

• `if`:

       ```
       if (условие) {
           // Инструкции, выполняемые, если условие истинно
       }
       ```

• `else if`:

       ```
       if (условие1) {
           // Инструкции, выполняемые, если условие1 истинно
       } else if (условие2) {
           // Инструкции, выполняемые, если условие2 истинно
       }
       ```

• `else`:

       ```
       if (условие) {
           // Инструкции, выполняемые, если условие истинно
       } else {
           // Инструкции, выполняемые, если условие ложно
       }
       ```

Циклы:

Повторяющееся выполнение блока кода до тех пор, пока выполняется определенное условие.

• `for`:

       ```
       for (инициализация; условие; изменение) {
           // Инструкции, выполняемые в цикле
       }
       ```

• `while`:

       ```
       while (условие) {
           // Инструкции, выполняемые, пока условие истинно
       }
       ```

• `do-while`:

       ```
       do {
           // Инструкции, выполняемые хотя бы один раз
       } while (условие);
       ```

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

Сортировка пузырьком (Bubble Sort):

Многократно проходит по списку, сравнивая соседние элементы и меняя их местами, если они находятся в неправильном порядке.

• Сложность: $O(n^2)$

Сортировка вставками (Insertion Sort):

Каждый элемент поочередно вставляется на правильную позицию в уже отсортированной части списка.

• Сложность: $O(n^2)$

Сортировка выбором (Selection Sort):

Находит минимальный элемент в списке и меняет его местами с первым элементом, затем повторяет процесс для оставшейся части списка.

• Сложность: $O(n^2)$

Быстрая сортировка (Quick Sort):

Выбирает опорный элемент, разделяет список на две части (элементы меньше опорного и элементы больше опорного), а затем рекурсивно сортирует эти части.

• Сложность: $O(n \log n)$ в среднем, $O(n^2)$ в худшем случае.

Сортировка слиянием (Merge Sort):

Разделяет список на меньшие списки, сортирует их и затем сливает в отсортированный список.

• Сложность: $O(n \log n)$

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

Линейный поиск:

Последовательно просматривает каждый элемент списка, пока не найдет искомый элемент или не достигнет конца списка.

• Сложность: $O(n)$

Бинарный поиск:

Требует отсортированного списка. Сравнивает искомый элемент со средним элементом списка. Если искомый элемент меньше, поиск продолжается в левой половине, иначе — в правой.

• Сложность: $O(\log n)$

Рекурсия

Определение:

Рекурсия — это метод решения задачи, при котором функция вызывает саму себя для решения подзадач.

• Базовый случай: Условие, при котором рекурсия останавливается и возвращает результат без дальнейших вызовов.
• Рекурсивный вызов: Функция вызывает саму себя с измененными входными данными, приближая решение к базовому случаю.
• Пример (вычисление факториала):

   ```python
   def factorial(n):
       if n == 0:  # Базовый случай
           return 1
       else:
           return n * factorial(n - 1)  # Рекурсивный вызов
   ```

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

Нотация "O" (Big O notation):

Используется для описания асимптотического поведения алгоритма, то есть как время выполнения или использование памяти растет с увеличением размера входных данных.

• Временная сложность: Оценивает, как время выполнения алгоритма зависит от размера входных данных.
• Пространственная сложность: Оценивает, как объем памяти, используемый алгоритмом, зависит от размера входных данных.
• Примеры:

   $O(1)$ — константное время (не зависит от размера входных данных).
   $O(\log n)$ — логарифмическое время.
   $O(n)$ — линейное время.
   $O(n \log n)$ — линейно-логарифмическое время.
   $O(n^2)$ — квадратичное время.
   $O(2^n)$ — экспоненциальное время.

Дополнительные Алгоритмы и Темы

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

Метод решения сложных задач путем разбиения их на более простые подзадачи и сохранения результатов этих подзадач для избежания повторных вычислений.

Жадные алгоритмы:

Принимают локально оптимальные решения на каждом шагу с надеждой найти глобально оптимальное решение.

Алгоритмы на графах:

• Поиск кратчайшего пути (алгоритм Дейкстры, алгоритм Флойда-Уоршелла).
• Поиск минимального остовного дерева (алгоритм Прима, алгоритм Крускала).