Algorithmic efficiency · Эффективность алгоритмов
What we'll do
- Two programs can both be correct but take very different time.
- This lesson is about efficiency: how the work grows as the input grows.
- Read and think about the ideas; then a few short tasks let you count the steps yourself.
Что мы сделаем
- Две программы могут быть обе правильными, но требовать совершенно разное время.
- Этот урок посвящён эффективности: тому, как растёт объём работы при увеличении входных данных.
- Прочитайте и обдумайте идеи; затем несколько коротких заданий позволят вам подсчитать шаги самостоятельно.
Counting the work
- We measure an algorithm by how many steps it does, not seconds.
- Steps in seconds depend on the computer; counting steps does not.
- More input usually means more steps. The question is how much more.
Подсчёт работы
- Мы измеряем алгоритм по количеству шагов, а не по секундам.
- Время в секундах зависит от компьютера; подсчёт шагов — нет.
- Больше входных данных обычно означает больше шагов. Вопрос в том, насколько больше.
Reasonable vs unreasonable run time
- Some algorithms grow slowly: double the input, do about double the work.
- Some algorithms grow fast: a little more input means a huge jump in work.
- "Reasonable" run time grows slowly enough to finish; "unreasonable" blows up.
Разумное и неразумное время выполнения
- Некоторые алгоритмы растут медленно: удвоение входных данных означает примерно удвоение работы.
- Некоторые алгоритмы растут быстро: небольшое увеличение входных данных вызывает огромный скачок объёма работы.
- «Разумное» время выполнения растёт медленно, позволяя завершиться; «неразумное» взрывается.
Input size: 10 20 40
Search a list: 10 20 40 (slow growth - reasonable)
Try all orders: 3,628,800 ... a number with 48 digits (explodes!)
A tiny demo: counting steps
- Below we count the comparisons a linear search makes.
- The count grows in step with the list size — slow, steady growth.
- Try changing the size to see the count follow it.
Маленький демо-пример: подсчёт шагов
- Ниже мы подсчитываем количество сравнений, которое делает линейный поиск.
- Счётчик растёт пропорционально размеру списка — медленный, стабильный рост.
- Попробуйте изменить размер, чтобы увидеть, как счётчик следует за ним.
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))
When fast is not enough
- Some problems have no known fast algorithm.
- The only methods try a huge number of possibilities — too slow for big input.
- For these, we often accept a good-enough answer instead of the perfect one.
Когда скорости недостаточно
- У некоторых задач нет известных быстрых алгоритмов.
- Единственные методы перебирают огромное количество вариантов — слишком медленно для больших входных данных.
- Для таких задач мы часто accepting a достаточного ответа вместо идеального.
Undecidable problems
- Worse than slow: some problems cannot be solved by any algorithm at all.
- These are called undecidable problems.
- No matter how fast computers get, no program can always give the right answer.
Неразрешимые задачи
- Хуже, чем медленные: некоторые задачи невозможно решить никаким алгоритмом.
- Они называются неразрешимыми задачами.
- Какими бы быстрыми ни становились компьютеры, ни одна программа не сможет всегда давать правильный ответ.
Fast : finishes quickly, even for big input
Slow but doable : finishes, but may take a very long time
Undecidable : no algorithm can solve it for every input
Key ideas to remember
- Efficiency is about how work grows with input size.
- Slow-growing algorithms scale to big inputs; fast-growing ones do not.
- Some problems are unreasonable to solve exactly, and some are undecidable.
Ключевые идеи для запоминания
- Эффективность заключается в том, как растёт объём работы с размером входных данных.
- Медленно растущие алгоритмы масштабируются на большие входные данные; быстро растущие — нет.
- Некоторые задачи невозможно решить точно, а некоторые являются неразрешимыми.
Common mistakes
- Big-O describes how the running time GROWS with the input size.
- A reasonable-time algorithm scales; an unreasonable one does not.
Распространенные ошибки
- Big-O описывает, как растёт время выполнения с размером входных данных.
- Алгоритм, работающий разумное время, масштабируется; неразумный — нет.
Now you try
- Write small functions that count steps to feel how the work grows.
- Compare a single loop, a nested loop, and "try all orders". Press Check answer.
Теперь попробуйте сами
- Пишите маленькие функции, которые подсчитывают шаги, чтобы почувствовать, как растёт объём работы.
- Сравните одиночный цикл, вложенный цикл и «перебор всех порядков». Нажмите Check answer.
How algorithms scale · Масштабируемость алгоритмов
As input grows, O(n²) explodes while O(log n) barely moves. · По мере роста входных данных O(n²) экспоненциально растет, тогда как O(log n) практически не меняется.
Write scan_compares(data, target) that returns how many comparisons a linear search makes. Compare each item to target, counting one each time, and stop as soon as you find it. If it is not in the list, you compared every item. Example: scan_compares([5, 8, 2], 8) → 2. · Напишите процедуру scan_compares(data, target), которая возвращает количество сравнений, выполненных линейным поиском. Сравнивайте каждый элемент с ⟨target⟩, увеличивая счетчик на единицу каждый раз, и прекратите работу, как только найдете элемент. Если его нет в списке, вы сравнили каждый элемент. Пример: ⟨scan_compares([5, 8, 2], 8)⟩ → ⟨2⟩.
Click Run to see the output here. · Нажмите Запустить, чтобы увидеть результат здесь.
Write pair_count(n) that uses a loop inside a loop (both over range(n)) and returns how many times the inner step runs. This is n × n. Example: pair_count(3) → 9. This grows much faster than a single loop. · Напишите процедуру pair_count(n), которая использует цикл внутри другого цикла (оба проходят по ⟨range(n)⟩) и возвращает количество раз, когда выполняется внутренний шаг. Это составляет ⟨n × n⟩. Пример: ⟨pair_count(3)⟩ → ⟨9⟩. Это растет гораздо быстрее, чем одиночный цикл.
Click Run to see the output here. · Нажмите Запустить, чтобы увидеть результат здесь.
Write count_orderings(n) that returns how many different orders n items can be placed in — that is 1 × 2 × ... × n (n factorial). count_orderings(0) is 1. Example: count_orderings(3) → 6. Notice how fast it explodes: count_orderings(10) is over 3 million. · Напишите процедуру count_orderings(n), которая возвращает количество различных перестановок ⟨n⟩ элементов — то есть ⟨1 × 2 × ... × n⟩ (факториал n). Значение ⟨count_orderings(0)⟩ равно ⟨1⟩. Пример: ⟨count_orderings(3)⟩ → ⟨6⟩. Обратите внимание, как быстро это растет: ⟨count_orderings(10)⟩ превышает 3 миллиона.
Click Run to see the output here. · Нажмите Запустить, чтобы увидеть результат здесь.