Что такое алгоритм

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

Что такое алгоритм

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

Четыре свойства

💡 Часто добавляют пятое свойство — корректность: результат обязан удовлетворять условию задачи. К нему вернёмся в теме 3.

Код ниже — алгоритм: вход — список и target, выход — индекс или -1, цикл заканчивается вместе со списком.

def find_index(items, target):
    for i, x in enumerate(items):
        if x == target:
            return i
    return -1


print(find_index([4, 8, 15, 16], 15))
print(find_index([4, 8, 15, 16], 23))

2
-1

Задача и решение

Задача говорит, что нужно получить (вход и ожидаемый выход). Алгоритм говорит, как это сделать. У одной задачи может быть много решений. Их сравнивают по трём вопросам: правилен ли он, насколько быстр и сколько памяти требует.

Пример: сумма от 1 до n

Первый алгоритм складывает числа по одному и делает n шагов:

def sum_loop(n):
    total = 0
    for i in range(1, n + 1):
        total += i
    return total


print(sum_loop(100))

5050

Второй использует формулу Гаусса: 1 + 2 + ... + n = n(n + 1) / 2. Это постоянное число операций:

def sum_loop(n):
    total = 0
    for i in range(1, n + 1):
        total += i
    return total


def sum_formula(n):
    return n * (n + 1) // 2


print(sum_formula(100))
print(sum_loop(100) == sum_formula(100))

5050
True

Результаты совпадают, а число шагов разное:

def loop_steps(n):
    steps = 0
    for _ in range(1, n + 1):
        steps += 1
    return steps


for n in (10, 100, 1000):
    print(n, loop_steps(n), 3)

10 10 3
100 100 3
1000 1000 3

Третий столбец — число операций формулы (около 3): оно не растёт вместе с n.

Зачем изучать алгоритмы

• Правильный алгоритм превращает часы работы в секунды.
• Встроенные sorted, dict, set — это алгоритмы; полезно знать, чего они стоят.
• Алгоритмическое мышление нужно и на собеседованиях, и в реальных проектах.

Путь курса

С каждой задачей мы действуем одинаково: чётко формулируем её, описываем идею псевдокодом, пишем код на Python, проверяем тестами и граничными случаями, затем измеряем скорость и оцениваем сложность. По этому пути мы дойдём до поиска, сортировок, структур данных и графов.

⚠️ Не путайте алгоритм с кодом: один алгоритм можно записать на Python или на другом языке. Код — лишь одна из его записей.