Algorithmic Efficiency
Введено| English | Значение |
|---|---|
| Algorithmic efficiency/ˌælɡəˈrɪθmɪk ɪˈfɪʃənsi/ | алгоритмическая эффективность |
| slow/sləʊ/ | медленный |
| steps/steps/ | шаги |
| reasonable/ˈriːzənəbl/ | разумный |
| unreasonable/ʌnˈriːzənəbl/ | неразумный |
| heuristic/hjuːˈrɪstɪk/ | эвристический метод |
Правильности недостаточно
- Два алгоритма могут быть оба правильными, но один может быть гораздо лучше для использования.
- Алгоритмическая эффективность сравнивает алгоритмы по используемым ими ресурсам — прежде всего времени и памяти.
- Правильный, но медленный алгоритм может быть бесполезен на больших объёмах данных.
- Поэтому нам нужен способ сравнить как они масштабируются.
Algorithmic efficiency compares algorithms by:
Сложность 1/5 · 100 монет + небольшой бонус за первое завершение сегодня
Efficiency is about time and memory as input grows.
Подсчёт шагов по мере роста n
- Оцените количество шагов, которые выполняет алгоритм, по мере роста размера его входа $n$.
- Линейный поиск занимает около $n$ шагов; двоичный поиск — около $\log_2 n$; сравнение каждой пары — около $n^2$.
- По мере того как $n$ становится большим, эти различия становятся огромными.
- Форма роста важна гораздо больше, чем хронометраж.

Как время выполнения алгоритма растёт с увеличением размера входа n
How running time grows with n
Slide n and compare the curves: log n stays almost flat, n rises steadily, n² explodes. This is why we compare algorithms by how they scale, not with a stopwatch.
Match each algorithm to its rough number of steps for input size n.
Сложность 2/5 · 140 монет + небольшой бонус за первое завершение сегодня
These growth rates decide which algorithm scales.
Which growth is considered unreasonable as n gets large?
Сложность 1/5 · 100 монет + небольшой бонус за первое завершение сегодня
Exponential growth quickly becomes far too slow.
When an exact answer is too slow, a ______ finds a good-enough solution fast.
Сложность 1/5 · 100 монет + небольшой бонус за первое завершение сегодня
A heuristic trades a perfect answer for speed.
Разумное против неразумного
- Мы разделяем разумное время выполнения и неразумное.
- Грубо говоря, рост типа $n$ или $n^2$ считается разумным; удвоение количества шагов на каждый дополнительный элемент (как в $2^n$) — нет.
- Когда точный ответ слишком медленный, используйте эвристику — приемлемое решение, найденное быстро.
- Не идеальное, но полезное, когда идеальное невозможно найти за приемлемое время.
A binary search of 1,000,000 sorted items needs at most about how many steps? (2^20 ≈ a million)
Сложность 2/5 · 140 монет + небольшой бонус за первое завершение сегодня
Because 2^20 is just over a million, ~20 halvings suffice.
If an algorithm is correct, it will always run fast enough on large inputs.
Сложность 1/5 · 100 монет + небольшой бонус за первое завершение сегодня
False. A correct algorithm can still be too slow on large inputs; it must also finish in a reasonable time.
Слишком медленно для использования
- Вот почему некоторые правильные алгоритмы слишком медленны для практического применения на больших объёмах данных.
- Быть правильным недостаточно — алгоритм также должен завершаться за разумное время.
Миллион элементов. Линейный поиск по 1,000,000 отсортированным элементам может занять до 1,000,000 шагов. Бинарный поиск занимает не более примерно 20, так как $2^{20}$ лишь немного превышает миллион. На малых списках разница почти незаметна; на миллионе элементов бинарный поиск — единственный разумный выбор.
Эффективность алгоритма сравнивает алгоритмы по ресурсам по мере роста размера входных данных $n$: линейный $n$, бинарный $\log_2 n$, «все пары» $n^2$. Рост типа $n$ или $n^2$ считается разумным; $2^n$ — неразумным (используйте эвристику). Корректный алгоритм, который слишком медленен для больших входных данных, недостаточно хорош.