Алгоритмы и их эффективность

Алгоритмы и их эффективность

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

Сложность алгоритма

Вычислительная сложность показывает, как растёт число операций с увеличением n. Её записывают через скорость роста. Если для массива из n элементов алгоритм делает порядка n действий — это линейная сложность; если n² — квадратичная; если порядка log n — логарифмическая (очень быстрая).

Сложность	Рост операций	Пример алгоритма
Логарифмическая	log n	Двоичный поиск
Линейная	n	Линейный поиск, сумма массива
Квадратичная	n²	Сортировка «пузырьком»

Поиск элемента

Линейный поиск перебирает элементы подряд, пока не найдёт нужный, — в худшем случае n сравнений. Если массив отсортирован, работает двоичный (бинарный) поиск: он сравнивает искомое со средним элементом и каждый раз отбрасывает половину диапазона.

лево = 1, право = n пока лево <= право   середина = (лево + право) / 2   если A[середина] = x → нашли, стоп   если A[середина] < x → лево = середина + 1   иначе → право = середина - 1

В массиве из 1000 элементов линейный поиск может сделать 1000 сравнений, а двоичный — около 10, ведь каждый шаг сокращает область вдвое.

Сортировка

Сортировка пузырьком многократно проходит по массиву, меняя местами соседние элементы, если они стоят в неверном порядке; за каждый проход наибольший элемент «всплывает» в конец. Это наглядный, но медленный метод сложности n². Существуют более быстрые сортировки (слиянием, быстрая) со сложностью порядка n·log n.

для i от 1 до n-1   для j от 1 до n-i     если A[j] > A[j+1]       то поменять местами A[j] и A[j+1]

Здесь два вложенных цикла дают как раз порядок n² сравнений. На массиве из 10 элементов это около 100 операций, а на 1000 — уже около миллиона: вот почему квадратичные алгоритмы плохо подходят для больших данных.

Почему сложность важна

Разница в сложности проявляется именно с ростом n. При n = 10 квадратичный и линейный алгоритмы почти неотличимы, но при n = 1 000 000 квадратичный потребует триллион операций и «зависнет», а логарифмический управится за два десятка шагов. Поэтому при работе с большими объёмами данных выбор эффективного алгоритма важнее мощности компьютера.

Практическое правило. Двоичный поиск применим только к упорядоченному массиву — на неотсортированных данных он даст неверный ответ. Прежде чем ускорять поиск, оцените, не дороже ли обойдётся сортировка. Для маленьких n разница в сложности почти незаметна, она важна на больших данных.

Трассировка: выполняем команды буквально

Для анализа программы выпишите начальные значения и после каждого шага обновляйте только те переменные, которым присвоено новое значение. Не подменяйте команду предполагаемым намерением автора. В Python присваивание n = n // 2 сначала вычисляет правую часть по старому n и только потом заменяет n.

n = 19
s = 0
while n > 0:
    if n % 2 == 1:
        s += n
    n //= 2
print(s)

n в начале шага	Нечётное?	s после if	n после деления
19	Да	19	9
9	Да	28	4
4	Нет	28	2
2	Нет	28	1
1	Да	29	0

Ответ: 29. Условие while проверяется ещё раз при n = 0, но тело шестой раз не выполняется. Количество итераций для положительного целого n равно ⌊log₂n⌋ + 1; при n = 0 итераций нет.

Логические условия

В Python среди not, and, or сначала выполняется not, затем and, затем or. Скобки могут явно изменить группировку. Например, для x = 5, y = 0 выражение x > 3 or y > 0 and x < 0 истинно: оно означает (x > 3) or ((y > 0) and (x < 0)). Запись ((x > 3) or (y > 0)) and (x < 0) уже ложна.

Проверяем завершение

В примере положительное n при каждом шаге уменьшается и достигает нуля. Если забыть n //= 2, условие останется истинным и программа зациклится. Одна успешная трассировка подтверждает результат для выбранного входа; для общего вывода нужно рассуждение обо всех допустимых данных.

Для исполнителя на клетчатом поле аналогично записывают текущую клетку, результат проверки стен и реально выполненную команду. Условия «справа свободно ИЛИ снизу свободно» и «И» останавливают движение в разных ситуациях.

Справочные материалы: Алгоритмы и их эффективность — исходная тема; Алгоритмы и их эффективность — исходная тема. Связанные уроки: Трассировка алгоритма по шагам, Что такое логические операции.

Первоисточники: Python: логические операции и приоритет.

Кратко о главном

• Эффективность алгоритма оценивают по затратам времени и памяти при росте n.
• Сложность бывает логарифмической, линейной, квадратичной и др.
• Линейный поиск работает всегда, двоичный — только в отсортированном массиве, но гораздо быстрее.
• Сортировка пузырьком проста, но медленна (n²); есть методы быстрее.
• Выбор алгоритма особенно важен при больших объёмах данных.