В алгоритмах и сложности мы фокусируемся на асимптотической сложности алгоритмов, то есть количестве ресурсов, которые алгоритм использует, поскольку размер входных данных уходит в бесконечность.
На практике необходим алгоритм, который бы работал быстро на конечном (хотя, возможно, очень большом) количестве экземпляров.
Алгоритм, который хорошо работает на практике на конечном количестве интересующих нас экземпляров, не обязательно должен иметь хорошую асимптотическую сложность (хорошая производительность на конечном числе экземпляров не подразумевает ничего относительно асимптотической сложности). Точно так же алгоритм с хорошей асимптотической сложностью может не работать на практике на конечном числе интересующих нас случаев (например, из-за больших констант).
Почему мы используем асимптотическую сложность? Как этот асимптотический анализ связан с разработкой алгоритмов на практике?
Ответы:
Интересный вопрос: какова альтернатива? Единственный другой метод, который я знаю, это тестирование / бенчмаркинг. Мы программируем алгоритмы, позволяем им запускать (репрезентативную выборку) конечный входной набор и сравниваем результаты. Есть несколько проблем с этим.
При этом игнорирование всех видов эффектов и констант в анализе является типичным, но его можно назвать ленивым (по отношению к практике). Он служит для сравнения алгоритмических идей больше, чем для точного определения производительности данной (даже псевдокодовой) реализации. Сообществу хорошо известно, что это грубо и что часто необходим более тщательный анализ; например, быстрая сортировка менее эффективна, чем сортировка вставкой для (очень) небольших входных данных. Чтобы быть справедливым, более точный анализ обычно трудно ².
Другое, апостериорное обоснование формальной, абстрактной точки зрения состоит в том, что на этом уровне вещи часто более ясны. Таким образом, десятилетия теоретических исследований выявили множество алгоритмических идей и структур данных, которые могут быть использованы на практике. Теоретически оптимальный алгоритм не всегда тот, который вы хотите использовать на практике - есть и другие соображения, но производительность нужно сделать; думаю, кучи Фибоначчи - и этот лейбл может даже не быть уникальным. Типичному программисту, занимающемуся оптимизацией арифметических выражений, трудно придумать новую идею на этом уровне (не сказать, что этого не происходит); тем не менее, она может (и должна) выполнить эту оптимизацию ассимилированной идеи.
Существуют формальные теоретические инструменты, позволяющие в некоторой степени сократить разрыв в практике. Примеры
Например, Кнут известен буквальным подсчетом числа различных операторов (для данной реализации в данной модели), что позволяет проводить точное сравнение алгоритмов. Такой подход невозможен на абстрактном уровне, и его трудно реализовать в более сложных моделях (например, Java). См. [4] для современного примера.
Между теорией и практикой всегда будет пропасть. В настоящее время мы работаем над инструментом3 с целью объединить лучшее из обоих миров, чтобы сделать надежные прогнозы как для алгоритмических затрат, так и для времени выполнения (в среднем), но до сих пор мы не смогли покончить со сценариями, в которых один алгоритм имеет более высокий стоит, но меньше времени выполнения (на некоторых машинах), чем эквивалент (хотя мы можем это определить и поддержать в поиске причины).
Я рекомендую практикам использовать теорию для фильтрации пространства алгоритмов перед запуском тестов:
источник
Я предполагаю, что этот вопрос возникает из преподавания курса, который включает в себя асимптотический анализ. Есть несколько возможных ответов относительно того, почему этот материал преподается на вводных занятиях:
Асимптотический анализ - это математическая абстракция, которая поддается анализу. Как (возможно) математики, мы хотим иметь возможность анализировать алгоритмы, и они могут только укротить их сложность, используя асимптотический анализ.
Оценка асимптотической эффективности алгоритма указывает на некоторые принципы, которые полезны на практике: например, сконцентрируйтесь на той части кода, которая занимает большую часть времени, и обесценивайте любую часть кода, которая занимает асимптотически незначительную часть времени ,
Некоторые из методов асимптотического анализа полезны. Я имею в виду, в основном, так называемую «основную теорему», которая во многих случаях является хорошим описанием реальности.
Существует также историческая причина: когда люди впервые начали анализировать алгоритмы, они искренне думали, что асимптотическая сложность отражает практическое использование. Однако в итоге они оказались неправы. То же самое произошло с P как классом эффективно решаемых задач и NP как классом неразрешимых проблем, которые на практике вводят в заблуждение.
Лично я считаю, что асимптотический анализ является разумной частью учебной программы. Более сомнительные части включают теорию формального языка и теорию сложности (все, что связано с машиной Тьюринга). Некоторые люди утверждают, что, хотя эти предметы бесполезны для потенциального программиста как такового, они внушают ей определенную мысль, которая необходима, чтобы быть хорошим практиком. Другие утверждают, что теория иногда влияет на практику, и этих редких случаев достаточно, чтобы оправдать преподавание этих довольно загадочных предметов широкой аудитории информатики. Я бы предпочел, чтобы они изучали историю или литературу или любой другой предмет, который им действительно интересен; оба имеют отношение к их будущим перспективам работы, и более важны для них, чем люди.
источник
Есть две серьезные причины использовать асимптотический анализ времени выполнения:
чтобы позволить математическую управляемость. Случаи, когда можно найти точные выражения для счетчика операций, являются исключительными. Изучение асимптотики открывает больше возможностей (например, удобны асимптотические приближения сложных функций).
И есть много других (например, независимость от машины, значимость, сопоставимость ...).
источник
Как отмечается в ответе Рафаэля, точное вычисление времени выполнения наихудшего случая может быть очень трудным. Точные вычисления также могут быть ненужными, так как модель RAM уже вводит приближения. Например, все ли операции занимают одинаковое время? Конкретные реализации (аппаратные средства, оптимизации) могут ускорить алгоритм за счет постоянных факторов. Мы хотим понять, насколько эффективен алгоритм независимо от этих факторов. Это большая мотивация для использования асимптотического анализа.
источник
Потому что асимптотика «проста» (ну, во всяком случае, проще, чем делать точный анализ для конечных случаев).
Сравните, например, энциклопедическую книгу «Искусство компьютерного программирования» Кнута, в которой подробно анализируются все важные алгоритмы (и многие не столь важные) с практическим анализом, которого часто бывает достаточно для получения асимптотической оценки ( или просто обязательный), как это практикуется в большинстве книг "алгоритмов".
Вы, конечно, правы. Если проблема достаточно важна, анализ Кнута (или, возможно, чуть менее подробный) вполне может быть оправдан. Во многих случаях достаточно намека на асимптотическую сложность (возможно, среднюю по дисперсии), подходящую для экспериментальных данных. В большинстве случаев , чтобы сделать грубую классификацию конкурирующих алгоритмов, в качестве первого раунда исключения асимптотики может быть достаточно точным. И если нет претендентов, получение плохих новостей о точной стоимости в мельчайших деталях - просто мазохизм.
источник
Здесь под асимптотическим анализом я предполагаю, что мы имеем в виду поведение алгоритма, поскольку размер входных данных уходит в бесконечность.
Причина, по которой мы используем асимптотический анализ, заключается в том, что он полезен для прогнозирования поведения алгоритмов на практике . Предсказания позволяют нам принимать решения, например, когда у нас есть разные алгоритмы для проблемы, какой из них мы должны использовать? (Быть полезным не значит, что это всегда правильно.)
Тот же вопрос можно задать о любой упрощенной модели реального мира. Почему мы используем упрощенные математические модели реального мира?
Подумай о физике. Классическая ньютоновская физика не так хороша, как релятивистская физика в предсказаниях реального мира. Но это достаточно хорошая модель для строительства автомобилей, небоскребов, подводных лодок, самолетов, мостов и т. Д. Есть случаи, когда это не достаточно хорошо, например, если мы хотим построить спутник или отправить космический зонд Плутону или предсказать движение массивных небесных объектов, таких как звезды и планеты, или очень высокоскоростных объектов, таких как электроны. Важно знать, каковы границы модели.
Обычно это достаточно хорошее приближение к реальному миру. На практике мы часто видим, что алгоритм с лучшим асимптотическим анализом работает лучше на практике. Редко случается, что алгоритм обладает лучшим асимптотическим поведением. Поэтому, если входные данные могут быть достаточно большими, мы обычно можем полагаться на асимптотический анализ в качестве первого предсказания поведения алгоритмов. Это не так, если мы знаем, что ввод будет небольшим. В зависимости от желаемой производительности нам может потребоваться провести более тщательный анализ, например, если у нас есть информация о распределении входных данных, будет предоставлен алгоритм, мы можем провести более тщательный анализ для достижения поставленных целей (например, быстро на 99 % входов). Дело в том, что в качестве первого шага асимптотический анализ является хорошей отправной точкой. На практике мы также должны проводить тесты производительности, но имейте в виду, что у этого также есть свои проблемы.
Короче говоря, асимптотическая сложность - это сравнительно легко вычисляемая аппроксимация реальной сложности алгоритмов для простых базовых задач (задач в учебнике по алгоритмам). По мере того как мы создаем более сложные программы, требования к производительности меняются и становятся все более сложными, и асимптотический анализ может оказаться не таким полезным.
Полезно сравнить асимптотический анализ с другими подходами для прогнозирования производительности алгоритмов и их сравнения. Одним из распространенных подходов является тестирование производительности на случайных или эталонных входных данных. Это обычно, когда вычисление асимптотической сложности является трудным или невыполнимым, например, когда мы используем эвристику, как, скажем, в решении SAT. Другой случай, когда требования более сложны, например, когда производительность программы зависит от внешних факторов, и наша цель может заключаться в том, чтобы что-то заканчивалось в определенные фиксированные временные рамки (например, подумать об обновлении интерфейса, показанного пользователю) на 99% входы.
Но имейте в виду, что анализ производительности также имеет свои проблемы. Он не предоставляет математических грантополучателей за меньшую производительность, но мы фактически запускаем тест производительности на всех входных данных, которые будут переданы алгоритму (часто в вычислительном отношении), и зачастую невозможно решить, что некоторые входные данные никогда не будут предоставлены). Если мы проводим тестирование на случайной выборке или эталоне, мы неявно предполагаем некоторую регулярность производительности алгоритмов, то есть алгоритм будет работать аналогично на других входных данных, которые не были частью теста производительности.
Вторая проблема с тестами производительности заключается в том, что они зависят от среды тестирования. Т.е. производительность программы определяется не одними входными данными, а внешними факторами (например, типом машины, операционной системой, эффективностью кодированного алгоритма, использованием ЦП, временем доступа к памяти и т. Д.), Некоторые из которых могут различаться в зависимости от разных прогонов тест на той же машине. Здесь мы снова предполагаем, что конкретные среды, в которых проводится тест производительности, аналогичны реальной среде, если только мы не проводим тесты производительности во всех средах, на которых мы можем запустить программу (и как мы можем предсказать, на каких машинах кто-то может выполнить сортировку). алгоритм на 10 лет?).
источник
Теперь представьте, что ожидание повторяется в коде столько раз, сколько вызывается код. Как математически оценить / оправдать это очевидное преимущество алгоритма быстрой сортировки? (т.е. действительно ли его название оправдано или это просто маркетинговый слоган?) с помощью асимптотических измерений сложности. остается только смотреть на анимацию, субъективно чувствуя, что пузырьковая сортировка является каким-то более слабым алгоритмом, и анализ асимптотической сложности может доказать это количественно. но обратите внимание, что асимптотический анализ сложности - это всего лишь один из инструментов для анализа алгоритмов, и он не всегда является окончательным.
и стоит также взглянуть на параллельный код. Пузырьковая сортировка концептуально проще и не использует рекурсию. Быстрая сортировка не так понятна, особенно принцип "медиана 3". пузырьковая сортировка может быть реализована просто в циклах без подпрограммы, тогда как быстрая сортировка обычно может содержать хотя бы одну подпрограмму. это показывает образец, что большая сложность кода иногда может улучшить асимптотическую сложность за счет простоты кода. иногда существует экстремальный обмен, похожий на концепцию уменьшения предельной доходности (происхождение из экономики), когда очень большие суммы сложности кода [требующие целых статей, полных thms и доказательств, чтобы оправдать], только покупают очень небольшие улучшения асимптотической сложности. это показывает в качестве примера ESP сматричное умножение и даже может быть рентгенографическим .
источник