Алгоритмическая эффективность
| 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/ | эвристика |
Правильности недостаточно
- Два алгоритма могут быть оба правильными, но один может быть гораздо лучше для использования.
- Алгоритмическая эффективность сравнивает алгоритмы по используемым ими ресурсам — прежде всего времени и памяти.
- Правильный, но медленный алгоритм может быть бесполезен на больших объёмах данных.
- Поэтому нам нужен способ сравнить как они масштабируются.
Алгоритмическая эффективность сравнивает алгоритмы по:
Эффективность касается времени и памяти при росте входных данных.
Подсчёт шагов по мере роста n
- Оцените количество шагов, которые выполняет алгоритм, по мере роста размера его входа $n$.
- Линейный поиск занимает около $n$ шагов; двоичный поиск — около $\log_2 n$; сравнение каждой пары — около $n^2$.
- По мере того как $n$ становится большим, эти различия становятся огромными.
- Форма роста важна гораздо больше, чем хронометраж.
Как время выполнения растет вместе с n
Слайд n и сравните кривые: log n остается почти плоским, n растет steadily, n² взрывается. Вот почему мы сравниваем алгоритмы по тому, как они масштабируются, а не с помощью секундомера.
Соотнесите каждый алгоритм с примерным количеством шагов для входных данных размера n.
Эти скорости роста определяют, какой алгоритм масштабируется лучше.
Какой рост считается нелогичным при больших значениях n?
Экспоненциальный рост быстро становится слишком медленным.
Когда точный ответ получается слишком долго, эвристика ______ находит достаточно хорошее решение быстро.
Эвристика жертвует идеальным ответом ради скорости.
Разумное против неразумного
- Мы разделяем разумное время выполнения и неразумное.
- Грубо говоря, рост типа $n$ или $n^2$ считается разумным; удвоение количества шагов на каждый дополнительный элемент (как в $2^n$) — нет.
- Когда точный ответ слишком медленный, используйте эвристику — приемлемое решение, найденное быстро.
- Не идеальное, но полезное, когда идеальное невозможно найти за приемлемое время.
Бинарный поиск среди 1,000,000 отсортированных элементов требует не более скольких шагов? (2^20 ≈ миллион)
Поскольку 2^20 чуть больше миллиона, ~20 делений пополам достаточно.
Правильный алгоритм все равно может быть слишком медленным для использования на больших входах.
Он также должен завершиться за приемлемое время.
Слишком медленно для использования
- Вот почему некоторые правильные алгоритмы слишком медленны для практического применения на больших объёмах данных.
- Быть правильным недостаточно — алгоритм также должен завершаться за разумное время.
Миллион элементов. Линейный поиск по 1,000,000 отсортированным элементам может занять до 1,000,000 шагов. Бинарный поиск занимает не более примерно 20, так как $2^{20}$ лишь немного превышает миллион. На малых списках разница почти незаметна; на миллионе элементов бинарный поиск — единственный разумный выбор.
Эффективность алгоритма сравнивает алгоритмы по ресурсам по мере роста размера входных данных $n$: линейный $n$, бинарный $\log_2 n$, «все пары» $n^2$. Рост типа $n$ или $n^2$ считается разумным; $2^n$ — неразумным (используйте эвристику). Корректный алгоритм, который слишком медленен для больших входных данных, недостаточно хорош.