Эффективность алгоритмов
Что мы сделаем
- Две программы могут быть обе правильными, но требовать совершенно разное время.
- Этот урок посвящён эффективности: тому, как растёт объём работы при увеличении входных данных.
- Прочитайте и обдумайте идеи; затем несколько коротких заданий позволят вам подсчитать шаги самостоятельно.
Подсчёт работы
- Мы измеряем алгоритм по количеству шагов, а не по секундам.
- Время в секундах зависит от компьютера; подсчёт шагов — нет.
- Больше входных данных обычно означает больше шагов. Вопрос в том, насколько больше.
Разумное и неразумное время выполнения
- «Разумное» время означает, что количество шагов растёт как полином или медленнее: константное, линейное, квадратичное или кубическое.
- Один цикл — это линейность. Вложенный цикл — это квадратичность (n × n). Квадратичная функция растёт быстрее линейной, но всё ещё является разумным временем.
- «Неразумное» время означает экспоненциальный или факториальный рост. Небольшое увеличение входных данных приводит к взрывному росту объёма работы.
Input size: 10 20 40
Search a list: 10 20 40 (linear - reasonable)
Nested loops: 100 400 1,600 (square - still reasonable)
Try all orders: 3,628,800 ... 48 digits (factorial - unreasonable)
Маленький демо-пример: подсчёт шагов
- Ниже мы подсчитываем количество сравнений, которое делает линейный поиск.
- Счётчик растёт пропорционально размеру списка — медленный, стабильный рост.
- Попробуйте изменить размер, чтобы увидеть, как счётчик следует за ним.
def count_steps(n):
steps = 0
data = list(range(n))
target = -1 # not in the list, so we scan everything
for item in data:
steps = steps + 1
if item == target:
break
return steps
print(count_steps(10))
print(count_steps(20))
print(count_steps(40))
Когда скорости недостаточно
- Некоторые задачи не имеют известных алгоритмов, работающих за разумное время.
- Точный метод может перебрать все перестановки. Это факториальный рост, поэтому он неразумен для больших входных данных.
- Эвристический метод — это упрощённый подход, который даёт приемлемый результат. Он не гарантирует оптимального решения. Запоминать конкретный эвристический метод не требуется.
Неразрешимые задачи
- Хуже, чем медленные: некоторые задачи невозможно решить никаким алгоритмом.
- Они называются неразрешимыми задачами.
- Какими бы быстрыми ни становились компьютеры, ни одна программа не сможет всегда давать правильный ответ.
Reasonable : constant, linear, square or cube growth
Unreasonable : exponential or factorial growth
Undecidable : no algorithm can solve it for every input
Ключевые идеи для запоминания
- Эффективность определяется тем, как количество шагов растёт с увеличением размера входных данных, а не тем, сколько секунд занимает работа на одном компьютере.
- Полиномиальный рост или ниже считается разумным временем. Вложенный цикл (n × n) также является приемлемым.
- Экспоненциальный или факториальный рост считается нерациональным. Некоторые задачи также являются неразрешимыми.
Распространенные ошибки
- Называть вложенный цикл нерациональным неверно. Квадратичный и кубический рост по-прежнему считаются приемлемым временем выполнения.
- Использование формальной нотации Big-O в качестве правила экзамена недопустимо. Nотация Big-O не проверяется. Критерий: полиномиальный или ниже, versus экспоненциальный или факториальный.
Теперь попробуйте сами
- Пишите маленькие функции, которые подсчитывают шаги, чтобы почувствовать, как растёт объём работы.
- Сравните одиночный цикл, вложенный цикл и перебор всех вариантов. Вложенный цикл всё ещё обеспечивает приемлемое время. Нажмите Проверить ответ.
Масштабируемость алгоритмов
Квадратичный рост ускоряется быстрее линейного, и остаётся приемлемым по времени. Факториальный рост является неприемлемым.
Сложность 3/5 · 200 монет + небольшой бонус за первое завершение сегодня
Напишите процедуру scan_compares(data, target), которая возвращает количество сравнений, выполненных линейным поиском. Сравнивайте каждый элемент с ⟨target⟩, увеличивая счетчик на единицу каждый раз, и прекратите работу, как только найдете элемент. Если его нет в списке, вы сравнили каждый элемент. Пример: ⟨scan_compares([5, 8, 2], 8)⟩ → ⟨2⟩.
Нажмите Запустить, чтобы увидеть результат здесь.
Сложность 3/5 · 200 монет + небольшой бонус за первое завершение сегодня
Напишите процедуру pair_count(n), которая использует цикл внутри другого цикла (оба проходят по ⟨range(n)⟩) и возвращает количество раз, когда выполняется внутренний шаг. Это составляет ⟨n × n⟩. Пример: ⟨pair_count(3)⟩ → ⟨9⟩. Это растет гораздо быстрее, чем одиночный цикл.
Нажмите Запустить, чтобы увидеть результат здесь.
Сложность 3/5 · 200 монет + небольшой бонус за первое завершение сегодня
Напишите процедуру count_orderings(n), которая возвращает количество различных перестановок ⟨n⟩ элементов — то есть ⟨1 × 2 × ... × n⟩ (факториал n). Значение ⟨count_orderings(0)⟩ равно ⟨1⟩. Пример: ⟨count_orderings(3)⟩ → ⟨6⟩. Обратите внимание, как быстро это растет: ⟨count_orderings(10)⟩ превышает 3 миллиона.
Нажмите Запустить, чтобы увидеть результат здесь.