Основы алгоритмов и методы анализа

В мире компьютерных наук,алгоритмы— это как рецепт для компьютера. Это чёткая, конечная, исполняемая последовательность инструкций, используемая для решения конкретной задачи или выполнения определённой вычислительной задачи. Будь то навигационное приложение на вашем телефоне, прокладывающее для вас кратчайший маршрут, или поисковая система, находящая наиболее релевантные веб-страницы из огромных объёмов данных за миллисекунды, — обе они опираются на тщательно продуманные алгоритмы, скрытые за кулисами.

Понимание основ алгоритмов и методов анализа — ключевой шаг для каждого программиста на пути от исполнителя кода к решателю задач.

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

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

Соответствующий требованиям алгоритм должен обладать следующими пятью базовыми характеристиками. Их можно понять с помощью кулинарной аналогии:

  1. Конечность: Алгоритм должен завершаться после конечного числа шагов. Как рецепт не может требовать помешивать бесконечно до конца вселенной, он должен давать чёткое условие остановки.
  2. Детерминированность: Каждый шаг алгоритма должен иметь точное определение, без неоднозначности. Например, «добавьте щепотку соли» — неопределённо, а «добавьте 5 граммов соли» — определённо.
  3. Выполнимость: Каждая операция в алгоритме должна быть базовой и выполнимой. Нельзя написать в рецепте «взбейте яйца силой мысли».
  4. Входные данные: У алгоритма есть ноль или более входных данных. Эти входные данные — объекты, обрабатываемые алгоритмом, как ингредиенты, необходимые в рецепте.
  5. Выходные данные: У алгоритма есть один или более выходных данных. Выходные данные — это величина, имеющая определённую связь с входными данными и являющаяся результатом выполнения алгоритма, как готовое блюдо.

Как описать алгоритм?

Алгоритм можно описать многими способами; три наиболее распространённых:

1. Описание на естественном языке

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

Пример: Найти максимальное значение среди трёх чисел.

  1. Сравните первое число и второе число и запомните большее.
  2. Сравните число, запомненное на предыдущем шаге, с третьим числом.
  3. Выведите наибольшее число как максимальное значение.

2. Блок-схема

Используйте графические символы для представления потока управления алгоритма. Она наглядно показывает логические связи между шагами.

Описание блок-схемы: Эта диаграмма наглядно показывает процесс принятия решений алгоритма поиска максимума из трёх чисел. Ромбы обозначают условные проверки, прямоугольники обозначают шаги обработки, а стрелки указывают направление выполнения программы.

3. Псевдокод

Метод описания, промежуточный между естественным языком и языком программирования. В нём используются структуры, подобные структурам языка программирования (например,if, for, while), но игнорирует конкретные детали синтаксиса и сосредотачивается на логическом выражении.

算法：FindMax
输入：三个数字 a, b, c
输出：最大值 max

1.  if a > b then
2.      max = a
3.  else
4.      max = b
5.  end if
6.  if c > max then
7.      max = c
8.  end if
9.  输出 max

4. Реализация на языке программирования

В конечном счёте, алгоритм нужно перевести в код на каком-либо языке программирования (например, Python, Java, C++), чтобы он мог выполняться на компьютере.

Пример

# Реализация на Python: найти максимум из трёх чисел
def find_max(a, b, c):
    # Сначала сравнить a и b, присвоить большее значение max_value
    if a > b:
        max_value = a
    else:
        max_value = b
    # Затем сравнить max_value с c
    if c > max_value:
        max_value = c
    return max_value

# Тестовый код
print(find_max(5, 9, 3))  # Вывод: 9
print(find_max(-1, 0, 1)) # Вывод: 1

Результат вывода:

9
1

Анализ алгоритмов: как оценить качество алгоритма?

Разработка алгоритма, способного решить задачу, — это лишь первый шаг; также нужно определить, какой алгоритм лучше. Обычно мы оцениваем по двум измерениям:

1. Временная сложность

Она измеряет,как время выполнения алгоритмарастёт по мере того, какразмер входных данных (n)увеличивается... Нас интересует не конкретное количество секунд, а тенденция роста (называемаяасимптотической временной сложностью）。

Сравнение распространённых временных сложностей:

Сложность Name Пример (n = размер данных) Наглядная метафора
O(1) Константный порядок Доступ к элементам массива по индексу "Включить свет". Независимо от того, насколько велика комната, время на переключение выключателя одинаково.
O(log n) Логарифмический порядок Бинарный поиск «Пролистать словарь». Каждый раз исключается половина, поэтому скорость поиска чрезвычайно высока.
O(n) Линейный порядок Обход массива Посчитать людей. Считать человека за человеком; время пропорционально общему числу людей.
O(n log n) Линейно-логарифмический порядок Быстрая сортировка, сортировка слиянием «Сортировка разделяй и властвуй». Намного быстрее, чем O(n²).
O(n²) Квадратичный порядок Простая сортировка выбором, пузырьковая сортировка «Попарные рукопожатия». Каждый человек должен один раз пожать руку каждому другому человеку.
O(2ⁿ) Экспоненциальный порядок Решение задачи о Ханойской башне, полный перебор «Деление клеток». Рост чрезвычайно пугающий; чуть большее n становится невыносимым.

Как анализировать?Сосредоточьтесь на циклах и рекурсии.

  • Один цикл: обычно O(n).
  • Вложенные циклы: обычно O(n²) (если оба уровня связаны с n).
  • Стратегия бинарного поиска: обычно O(log n).

2. Пространственная сложность

Она измеряетобъём памяти, необходимый для работы алгоритма,какразмер входных данных (n)растёт с ростом ... Помимо хранения самих входных данных, также необходимо учитывать дополнительные массивы, переменные и т. д., выделяемые во время выполнения алгоритма.

Анализ примера:

Пример

# Пример 1: Пространственная сложность O(1)
def find_max_in_list(lst):
    max_val = lst[0]          # Использует только постоянное количество дополнительных переменных.
    for num in lst:
        if num > max_val:
            max_val = num
    return max_val

# Пример 2: пространственная сложность O(n)
def copy_and_double_list(lst):
    new_list = []             # Выделен новый список той же длины, что и входной список.
    for num in lst:
        new_list.append(num * 2)
    return new_list

Практическое упражнение: анализ и применение с точки зрения алгоритмов сортировки

Возьмём классическуюпузырьковую сортировкув качестве примера, комплексно применяя вышеизложенные знания.

Идея алгоритма

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

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

Реализация на Python и построчный анализ

Пример

def bubble_sort(arr):
    """
Алгоритм пузырьковой сортировки
Параметр arr: список для сортировки
Возвращаемое значение: отсортированный список (изменяется на месте и также возвращается напрямую)
    """
    n = len(arr)
    # Внешний цикл: управляет тем, сколько всего раундов «всплытия» необходимо.
    for i in range(n - 1):
        # Предполагаем, что этот раунд уже отсортирован; используется для оптимизации.
        swapped = False
        # Внутренний цикл: выполняет один раунд «всплытия», опуская наибольший элемент в конец.
        # После каждого раунда последние i+1 элементов уже отсортированы, поэтому диапазон равен n-1-i.
        for j in range(0, n - 1 - i):
            # Если предыдущий элемент больше следующего, поменять их местами.
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]  # Изящный синтаксис обмена в Python.
                swapped = True  # Произошёл обмен.
        # Если за этот проход не произошло ни одного обмена, список полностью отсортирован, поэтому можно выйти досрочно.
        if not swapped:
            break
    return arr

# Тестовые данные и проверка.
test_data = [64, 34, 25, 12, 22, 11, 90]
print("Перед сортировкой:", test_data)
sorted_data = bubble_sort(test_data.copy()) # Используйте copy, чтобы не изменять исходный список.
print("После сортировки:", sorted_data)

# Проверьте, верен ли результат.
print("Правильна ли сортировка?", sorted_data == sorted(test_data.copy())) # Должно совпадать с результатом встроенной сортировки Python.

Результат вывода:

排序前: [64, 34, 25, 12, 22, 11, 90]
排序后: [11, 12, 22, 25, 34, 64, 90]
排序是否正确? True

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

  • Временная сложность：
    • Худший и средний случай O(n²): Когда список полностью упорядочен в обратном порядке, необходимо выполнить(n-1) + (n-2) + ... + 1 = n(n-1)/2сравнений и обменов.
    • Лучший случай O(n): Когда список уже отсортирован, добавлениеswappedС оптимизацией флага достаточно одного прохода, чтобы обнаружить отсутствие обменов и завершить работу досрочно.
  • Пространственная сложность O(1): Алгоритм использует толькоi, j, swappedи другие временные переменные в фиксированном количестве, являетсясортировкой на местеалгоритмом.

Практические задания

  • Ручное моделирование: С помощью бумаги и карандаша проследите работу алгоритма для списка[5, 3, 8, 1]Выполните сортировку и запишите состояние списка после каждого прохода пузырька.
  • Эксперимент со сложностью: Измените тестовые данные и протестируйте на уже отсортированных списках (например,[1,2,3,4,5]) и полностью обратном списке (таком как[5,4,3,2,1]) чтобы наблюдать количество циклов (можно добавить счётчик во внутреннем цикле).
  • Попробуйте улучшить: Можете ли вы придумать алгоритм сортировки, который похож по идее на пузырьковую сортировку, но, возможно, более эффективен? (Подсказка: каждый проход не только поднимает наверх максимальный пузырёк, но и опускает вниз минимальный пузырёк.)
Другие расширения