Рубрики

Анализ алгоритмов | Набор 1 (Асимптотический анализ)

Почему анализ производительности?
Есть много важных вещей, о которых нужно позаботиться, таких как удобство использования, модульность, безопасность, удобство обслуживания и т. Д. Зачем беспокоиться о производительности?
Ответ на этот вопрос прост, мы можем иметь все вышеперечисленное, только если у нас есть производительность. Так что производительность — это как валюта, через которую мы можем купить все вышеперечисленное. Еще одна причина для изучения производительности — скорость это весело!
Подводя итог, производительность == масштаб. Представьте себе текстовый редактор, который может загружать 1000 страниц, но может проверять орфографию 1 страницу в минуту ИЛИ редактор изображений, который занимает 1 час, чтобы повернуть изображение на 90 градусов влево ИЛИ… вы получите его. Если программная функция не может справиться с масштабом задач, которые необходимо выполнить пользователям — она ничтожна.


Учитывая два алгоритма для задачи, как мы узнаем, какой из них лучше?

Один наивный способ сделать это — реализовать оба алгоритма и запустить две программы на вашем компьютере для разных входов и посмотреть, какая из них занимает меньше времени. Существует много проблем с этим подходом для анализа алгоритмов.
1) Возможно, что для некоторых входов первый алгоритм работает лучше, чем второй. И для некоторых входов второй работает лучше.
2) Возможно также, что для некоторых входов первый алгоритм работает лучше на одной машине, а второй работает лучше на другой машине для некоторых других входов.

Асимптотический анализ — это большая идея, которая решает вышеуказанные проблемы при анализе алгоритмов. В Асимптотическом анализе мы оцениваем производительность алгоритма с точки зрения размера ввода (мы не измеряем фактическое время выполнения). Мы вычисляем, как время (или пространство), занимаемое алгоритмом, увеличивается с размером входного сигнала.
Например, давайте рассмотрим проблему поиска (поиск по заданному элементу) в отсортированном массиве. Одним из способов поиска является линейный поиск (порядок роста линейный), а другим — бинарный поиск (порядок роста логарифмический). Чтобы понять, как асимптотический анализ решает вышеупомянутые проблемы при анализе алгоритмов, скажем, мы запускаем линейный поиск на быстром компьютере и бинарный поиск на медленном компьютере. При небольших значениях размера входного массива n быстрый компьютер может занять меньше времени. Но после определенного значения размера входного массива бинарный поиск определенно начнёт занимать меньше времени по сравнению с линейным поиском, даже если бинарный поиск выполняется на медленной машине. Причина в том, что порядок роста двоичного поиска по отношению к размеру входных данных логарифмичен, тогда как порядок роста линейного поиска является линейным. Таким образом, машинно-зависимые константы всегда можно игнорировать после определенных значений входного размера.

Асимптотический анализ всегда работает?
Асимптотический анализ не идеален, но это лучший способ анализа алгоритмов. Например, скажем, есть два алгоритма сортировки, которые требуют 1000nLogn и 2nLogn времени соответственно на машине. Оба этих алгоритма асимптотически одинаковы (порядок роста nLogn). Таким образом, с помощью асимптотического анализа мы не можем судить, какой из них лучше, поскольку игнорируем константы в асимптотическом анализе.
Кроме того, в асимптотическом анализе мы всегда говорим о входных размерах, превышающих постоянное значение. Вполне возможно, что эти большие входные данные никогда не передаются вашему программному обеспечению, и алгоритм, который асимптотически медленнее, всегда работает лучше для вашей конкретной ситуации. Таким образом, вы можете в конечном итоге выбрать алгоритм, который будет асимптотически медленнее, но быстрее для вашего программного обеспечения.

Далее — Анализ алгоритмов | Набор 2 (худшие, средние и лучшие случаи)

Ссылки:
Видеолекция MIT 1 «Введение в алгоритмы» .

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

Рекомендуемые посты:

Анализ алгоритмов | Набор 1 (Асимптотический анализ)

0.00 (0%) 0 votes