Объясняя актуальность асимптотической сложности алгоритмов для практики проектирования алгоритмов

40

В алгоритмах и сложности мы фокусируемся на асимптотической сложности алгоритмов, то есть количестве ресурсов, которые алгоритм использует, поскольку размер входных данных уходит в бесконечность.

На практике необходим алгоритм, который бы работал быстро на конечном (хотя, возможно, очень большом) количестве экземпляров.

Алгоритм, который хорошо работает на практике на конечном количестве интересующих нас экземпляров, не обязательно должен иметь хорошую асимптотическую сложность (хорошая производительность на конечном числе экземпляров не подразумевает ничего относительно асимптотической сложности). Точно так же алгоритм с хорошей асимптотической сложностью может не работать на практике на конечном числе интересующих нас случаев (например, из-за больших констант).

Почему мы используем асимптотическую сложность? Как этот асимптотический анализ связан с разработкой алгоритмов на практике?

Кава
источник
Другой важный вопрос: почему мы игнорируем постоянные факторы ?
Рафаэль

Ответы:

24

Интересный вопрос: какова альтернатива? Единственный другой метод, который я знаю, это тестирование / бенчмаркинг. Мы программируем алгоритмы, позволяем им запускать (репрезентативную выборку) конечный входной набор и сравниваем результаты. Есть несколько проблем с этим.

  • Результаты не являются общими с точки зрения машин. Запустите свой эталонный тест на другом компьютере, и вы получите разные результаты точно, количественно и, возможно, даже качественно.
  • Результаты не являются общими с точки зрения языков программирования. Разные языки могут привести к очень разным результатам.
  • Результаты не являются общими с точки зрения деталей реализации. Вы буквально сравниваете программы , а не алгоритмы; Небольшие изменения в реализации могут вызвать огромные различия в производительности.
  • Если наихудший случай редкий, случайная входная выборка может не содержать плохой экземпляр. Это справедливо, если вас интересует средняя производительность случая, но в некоторых средах требуются гарантии наихудшего случая.
  • На практике входные наборы меняются. Как правило, входы становятся больше с течением времени. Если вы не будете повторять свой тест каждые шесть месяцев (да, некоторые данные растут так быстро), ваши результаты скоро станут бесполезными ».

При этом игнорирование всех видов эффектов и констант в анализе является типичным, но его можно назвать ленивым (по отношению к практике). Он служит для сравнения алгоритмических идей больше, чем для точного определения производительности данной (даже псевдокодовой) реализации. Сообществу хорошо известно, что это грубо и что часто необходим более тщательный анализ; например, быстрая сортировка менее эффективна, чем сортировка вставкой для (очень) небольших входных данных. Чтобы быть справедливым, более точный анализ обычно трудно ².

Другое, апостериорное обоснование формальной, абстрактной точки зрения состоит в том, что на этом уровне вещи часто более ясны. Таким образом, десятилетия теоретических исследований выявили множество алгоритмических идей и структур данных, которые могут быть использованы на практике. Теоретически оптимальный алгоритм не всегда тот, который вы хотите использовать на практике - есть и другие соображения, но производительность нужно сделать; думаю, кучи Фибоначчи - и этот лейбл может даже не быть уникальным. Типичному программисту, занимающемуся оптимизацией арифметических выражений, трудно придумать новую идею на этом уровне (не сказать, что этого не происходит); тем не менее, она может (и должна) выполнить эту оптимизацию ассимилированной идеи.

Существуют формальные теоретические инструменты, позволяющие в некоторой степени сократить разрыв в практике. Примеры

  • учитывая иерархию памяти (и другие операции ввода / вывода),
  • анализ среднего случая (где это уместно),
  • анализ количества отдельных отчетов (вместо абстрактных показателей затрат) и
  • определение постоянных факторов.

Например, Кнут известен буквальным подсчетом числа различных операторов (для данной реализации в данной модели), что позволяет проводить точное сравнение алгоритмов. Такой подход невозможен на абстрактном уровне, и его трудно реализовать в более сложных моделях (например, Java). См. [4] для современного примера.

Между теорией и практикой всегда будет пропасть. В настоящее время мы работаем над инструментом3 с целью объединить лучшее из обоих миров, чтобы сделать надежные прогнозы как для алгоритмических затрат, так и для времени выполнения (в среднем), но до сих пор мы не смогли покончить со сценариями, в которых один алгоритм имеет более высокий стоит, но меньше времени выполнения (на некоторых машинах), чем эквивалент (хотя мы можем это определить и поддержать в поиске причины).

Я рекомендую практикам использовать теорию для фильтрации пространства алгоритмов перед запуском тестов:

if ( input size forever bounded? ) {
  benchmark available implementations, choose best
  schedule new benchmarks for when machine changes
}
else {
  benchmark implementations of all asymptotically good algorithms
  choose the best
  schedule new benchmarks for when machine changes or inputs grow significantly
}

  1. Абсолютные и относительные характеристики могут привести к сумасшедшим изменениям, если количество пропущенных кешей возрастает, что обычно происходит при увеличении входных данных, но машина остается неизменной.
  2. Как, впрочем, ведущие исследователи в данной области не способны это сделать.
  3. Найдите инструмент здесь . Пример использования был опубликован в статье «Разработка двухуровневой быстрой сортировки Java 7 с использованием MaLiJAn» автора S. Wild et al. (2012) [ препринт ]
  4. Анализ среднего кейса двойной поворотной сортировки Java 7, выполненный S. Wild и M. Nebel (2012) - [ препринт ]
Рафаэль
источник
3
Можно утверждать, что сам процесс изучения теории алгоритмов обострит ваш глаз и обучит ваш мозг абстракции для алгоритмов, предоставляя вам еще один инструмент для оценки кода в повседневном программировании. Абстрагироваться от кода, оценить принцип, улучшить его и перевести обратно на код. Пример: «Ах, я вижу, вы хотите запрограммировать словарь. Но вы, по сути, программируете списки; почему бы не попробовать деревья?»
Рафаэль
Пределы асимптотического анализа становятся очевидными, когда вы копаете глубже; Быстрая сортировка является ярким примером .
Рафаэль
1
FWIW, я написал более свежий снимок моих мнений о нотации Ландау здесь .
Рафаэль
11

Я предполагаю, что этот вопрос возникает из преподавания курса, который включает в себя асимптотический анализ. Есть несколько возможных ответов относительно того, почему этот материал преподается на вводных занятиях:

  • Асимптотический анализ - это математическая абстракция, которая поддается анализу. Как (возможно) математики, мы хотим иметь возможность анализировать алгоритмы, и они могут только укротить их сложность, используя асимптотический анализ.

  • Оценка асимптотической эффективности алгоритма указывает на некоторые принципы, которые полезны на практике: например, сконцентрируйтесь на той части кода, которая занимает большую часть времени, и обесценивайте любую часть кода, которая занимает асимптотически незначительную часть времени ,

  • Некоторые из методов асимптотического анализа полезны. Я имею в виду, в основном, так называемую «основную теорему», которая во многих случаях является хорошим описанием реальности.

  • Существует также историческая причина: когда люди впервые начали анализировать алгоритмы, они искренне думали, что асимптотическая сложность отражает практическое использование. Однако в итоге они оказались неправы. То же самое произошло с P как классом эффективно решаемых задач и NP как классом неразрешимых проблем, которые на практике вводят в заблуждение.

Лично я считаю, что асимптотический анализ является разумной частью учебной программы. Более сомнительные части включают теорию формального языка и теорию сложности (все, что связано с машиной Тьюринга). Некоторые люди утверждают, что, хотя эти предметы бесполезны для потенциального программиста как такового, они внушают ей определенную мысль, которая необходима, чтобы быть хорошим практиком. Другие утверждают, что теория иногда влияет на практику, и этих редких случаев достаточно, чтобы оправдать преподавание этих довольно загадочных предметов широкой аудитории информатики. Я бы предпочел, чтобы они изучали историю или литературу или любой другой предмет, который им действительно интересен; оба имеют отношение к их будущим перспективам работы, и более важны для них, чем люди.

Юваль Фильмус
источник
Спасибо, Юваль. Мотивация в основном интересует то, как объяснить студентам полезность асимптотического анализа и его актуальность для практики разработки и использования алгоритмов в реальных приложениях (где в большинстве случаев ясно, что нас интересует только конечное, хотя, возможно, очень большое количество экземпляров), не обосновывающих учебную программу.
Каве
1
Я смущен вашей предпосылкой. Вы, кажется, предполагаете, что целевой группой являются как математики, так и начинающие программисты, что является странной комбинацией и не характеризует компьютерных ученых. (Кроме того, я не разделяю вашу точку зрения на формальные языки, но это уже другая тема.)
Рафаэль
Напротив, я предполагаю, что целевой группой являются начинающие программисты. Тем не менее, большая часть учебной программы существует ради теоретических компьютерных ученых. Конечно, эти две группы имеют противоречивые потребности. Поскольку большинство студентов являются потенциальными программистами, я думаю, что учебная программа должна быть ориентирована на них, но некоторые ученые не согласны. Возможно, они хотят учить будущих профессоров. Может быть, вы можете объяснить свою точку зрения.
Юваль Фильмус
3
@YuvalFilmus Я часто объяснял, что я не верю, что CS = TCS + Программирование. Если вы читаете курс CS (в университете) и большинство ваших студентов хотят стать программистами, что-то не работает (imho). Я бы сказал, что любой ученый-компьютерщик может получить хорошее образование в области алгоритмики, формальных языков и даже некоторой теории сложности (и многих других вещей, таких как работа компиляторов и процессоров).
Рафаэль
2
@Wildcard Компьютерная архитектура, компьютерная графика, AI, исследование языка программирования, ... - этот список бесконечен! TCS действительно ниша, а программирование - всего лишь инструмент для (большинства) исследователей КС.
Рафаэль
7

Есть две серьезные причины использовать асимптотический анализ времени выполнения:

  • N

  • чтобы позволить математическую управляемость. Случаи, когда можно найти точные выражения для счетчика операций, являются исключительными. Изучение асимптотики открывает больше возможностей (например, удобны асимптотические приближения сложных функций).

И есть много других (например, независимость от машины, значимость, сопоставимость ...).

Ив Дауст
источник
N
Ну, я не думаю, что это правило вообще. Чем больше данных вы выбрасываете, тем слабее могут быть высказывания. Асимптотическая (и, более того, "big-oh") перспектива создает операторы типа "Быстрая сортировка быстрее, чем Insertionsort", которая, если не ложно, либо не совсем верна. (Да, я говорю, что алгоритм анализа часто преподается неправильно, имхо.)
Рафаэль
6

Как отмечается в ответе Рафаэля, точное вычисление времени выполнения наихудшего случая может быть очень трудным. Точные вычисления также могут быть ненужными, так как модель RAM уже вводит приближения. Например, все ли операции занимают одинаковое время? Конкретные реализации (аппаратные средства, оптимизации) могут ускорить алгоритм за счет постоянных факторов. Мы хотим понять, насколько эффективен алгоритм независимо от этих факторов. Это большая мотивация для использования асимптотического анализа.

Юхо
источник
3

Потому что асимптотика «проста» (ну, во всяком случае, проще, чем делать точный анализ для конечных случаев).

Сравните, например, энциклопедическую книгу «Искусство компьютерного программирования» Кнута, в которой подробно анализируются все важные алгоритмы (и многие не столь важные) с практическим анализом, которого часто бывает достаточно для получения асимптотической оценки ( или просто обязательный), как это практикуется в большинстве книг "алгоритмов".

Вы, конечно, правы. Если проблема достаточно важна, анализ Кнута (или, возможно, чуть менее подробный) вполне может быть оправдан. Во многих случаях достаточно намека на асимптотическую сложность (возможно, среднюю по дисперсии), подходящую для экспериментальных данных. В большинстве случаев , чтобы сделать грубую классификацию конкурирующих алгоритмов, в качестве первого раунда исключения асимптотики может быть достаточно точным. И если нет претендентов, получение плохих новостей о точной стоимости в мельчайших деталях - просто мазохизм.

vonbrand
источник
2
Это только половина правды: во-первых, кажется, вы пишете с пометкой «о-о» (о чем вопрос не упоминается). Во-вторых, «большие-ой» асимптотики печально известны тем, что они проваливаются из-за «обходных раундов» при выборе алгоритмов: входные данные в реальности конечны.
Рафаэль
3

Здесь под асимптотическим анализом я предполагаю, что мы имеем в виду поведение алгоритма, поскольку размер входных данных уходит в бесконечность.

Причина, по которой мы используем асимптотический анализ, заключается в том, что он полезен для прогнозирования поведения алгоритмов на практике . Предсказания позволяют нам принимать решения, например, когда у нас есть разные алгоритмы для проблемы, какой из них мы должны использовать? (Быть полезным не значит, что это всегда правильно.)

Тот же вопрос можно задать о любой упрощенной модели реального мира. Почему мы используем упрощенные математические модели реального мира?

Подумай о физике. Классическая ньютоновская физика не так хороша, как релятивистская физика в предсказаниях реального мира. Но это достаточно хорошая модель для строительства автомобилей, небоскребов, подводных лодок, самолетов, мостов и т. Д. Есть случаи, когда это не достаточно хорошо, например, если мы хотим построить спутник или отправить космический зонд Плутону или предсказать движение массивных небесных объектов, таких как звезды и планеты, или очень высокоскоростных объектов, таких как электроны. Важно знать, каковы границы модели.

  1. Обычно это достаточно хорошее приближение к реальному миру. На практике мы часто видим, что алгоритм с лучшим асимптотическим анализом работает лучше на практике. Редко случается, что алгоритм обладает лучшим асимптотическим поведением. Поэтому, если входные данные могут быть достаточно большими, мы обычно можем полагаться на асимптотический анализ в качестве первого предсказания поведения алгоритмов. Это не так, если мы знаем, что ввод будет небольшим. В зависимости от желаемой производительности нам может потребоваться провести более тщательный анализ, например, если у нас есть информация о распределении входных данных, будет предоставлен алгоритм, мы можем провести более тщательный анализ для достижения поставленных целей (например, быстро на 99 % входов). Дело в том, что в качестве первого шага асимптотический анализ является хорошей отправной точкой. На практике мы также должны проводить тесты производительности, но имейте в виду, что у этого также есть свои проблемы.

  2. AAAимеет лучшую асимптотическую сложность. Чем ни один из них не лучше другого во всех входах? Тогда это становится более сложным и зависит от того, что нас волнует. Мы заботимся о больших входах или маленьких входах? Если мы заботимся о больших входных данных, то не часто алгоритм имеет лучшую асимптотическую сложность, но ведет себя хуже всего при больших входных данных, которые нас интересуют. Если мы больше заботимся о небольших входах, то асимптотический анализ может оказаться не таким уж полезным. Мы должны сравнить время работы алгоритмов на входах, которые нас интересуют. На практике для сложных задач со сложными требованиями асимптотический анализ может быть не таким полезным. Для простых основных задач, которые рассматриваются в учебниках по алгоритму, это весьма полезно.

Короче говоря, асимптотическая сложность - это сравнительно легко вычисляемая аппроксимация реальной сложности алгоритмов для простых базовых задач (задач в учебнике по алгоритмам). По мере того как мы создаем более сложные программы, требования к производительности меняются и становятся все более сложными, и асимптотический анализ может оказаться не таким полезным.


Полезно сравнить асимптотический анализ с другими подходами для прогнозирования производительности алгоритмов и их сравнения. Одним из распространенных подходов является тестирование производительности на случайных или эталонных входных данных. Это обычно, когда вычисление асимптотической сложности является трудным или невыполнимым, например, когда мы используем эвристику, как, скажем, в решении SAT. Другой случай, когда требования более сложны, например, когда производительность программы зависит от внешних факторов, и наша цель может заключаться в том, чтобы что-то заканчивалось в определенные фиксированные временные рамки (например, подумать об обновлении интерфейса, показанного пользователю) на 99% входы.

Но имейте в виду, что анализ производительности также имеет свои проблемы. Он не предоставляет математических грантополучателей за меньшую производительность, но мы фактически запускаем тест производительности на всех входных данных, которые будут переданы алгоритму (часто в вычислительном отношении), и зачастую невозможно решить, что некоторые входные данные никогда не будут предоставлены). Если мы проводим тестирование на случайной выборке или эталоне, мы неявно предполагаем некоторую регулярность производительности алгоритмов, то есть алгоритм будет работать аналогично на других входных данных, которые не были частью теста производительности.

Вторая проблема с тестами производительности заключается в том, что они зависят от среды тестирования. Т.е. производительность программы определяется не одними входными данными, а внешними факторами (например, типом машины, операционной системой, эффективностью кодированного алгоритма, использованием ЦП, временем доступа к памяти и т. Д.), Некоторые из которых могут различаться в зависимости от разных прогонов тест на той же машине. Здесь мы снова предполагаем, что конкретные среды, в которых проводится тест производительности, аналогичны реальной среде, если только мы не проводим тесты производительности во всех средах, на которых мы можем запустить программу (и как мы можем предсказать, на каких машинах кто-то может выполнить сортировку). алгоритм на 10 лет?).

Θ(NЛ.Г.N)Θ(N2)Θ(Л.Г.N)О(N)

Кава
источник
Мне нравится этот ответ достаточно, чтобы проголосовать сейчас. Два замечания: 1) Я бы использовал здесь «стоимость» вместо «сложность». Частично по причинам, вызывающим раздражение домашних животных, а также потому, что существует множество возможных затратных мер (что усложняет все упомянутые вами соображения). 2) Возможно, вы захотите пройти языковой проход. ;)
Рафаэль
@ Рафаэль, спасибо. Я планирую сделать еще одно редактирование в ближайшее время. :)
Kaveh
-2

О(N2)О(NжурналN)О(N2) чтобы закончить по сравнению с быстрой сортировкой.

Теперь представьте, что ожидание повторяется в коде столько раз, сколько вызывается код. Как математически оценить / оправдать это очевидное преимущество алгоритма быстрой сортировки? (т.е. действительно ли его название оправдано или это просто маркетинговый слоган?) с помощью асимптотических измерений сложности. остается только смотреть на анимацию, субъективно чувствуя, что пузырьковая сортировка является каким-то более слабым алгоритмом, и анализ асимптотической сложности может доказать это количественно. но обратите внимание, что асимптотический анализ сложности - это всего лишь один из инструментов для анализа алгоритмов, и он не всегда является окончательным.

и стоит также взглянуть на параллельный код. Пузырьковая сортировка концептуально проще и не использует рекурсию. Быстрая сортировка не так понятна, особенно принцип "медиана 3". пузырьковая сортировка может быть реализована просто в циклах без подпрограммы, тогда как быстрая сортировка обычно может содержать хотя бы одну подпрограмму. это показывает образец, что большая сложность кода иногда может улучшить асимптотическую сложность за счет простоты кода. иногда существует экстремальный обмен, похожий на концепцию уменьшения предельной доходности (происхождение из экономики), когда очень большие суммы сложности кода [требующие целых статей, полных thms и доказательств, чтобы оправдать], только покупают очень небольшие улучшения асимптотической сложности. это показывает в качестве примера ESP сматричное умножение и даже может быть рентгенографическим .

ВЗН
источник
Между «просмотром анимации» и формальным анализом существует множество территорий, таких как обширные тесты во время выполнения. На самом деле они являются действительной областью, так как у нас нет теории, чтобы объяснить все, что влияет на время выполнения.
Рафаэль
@raphael, вы рассмотрели тестирование в своем ответе; это хороший ответ. но обратите внимание, что анимация / визуализация могут быть тесно связаны с тестированием. на самом деле существует множество объяснений того, что влияет на время выполнения [описано в других ответах], но в некоторой степени его «шум» и асимптотическая сложность «сглаживают / усредняют шум». Это еще одно упражнение, чтобы увидеть, как это на самом деле.
2012 года
Анимации не фильтруют шум, хотя. Кроме того, человеческий глаз легко обмануть, и просто невозможно просмотреть анимацию для выборки разумных размеров списков разумного размера (скажем, 1000 списков для размеров в миллионах для сравнения алгоритмов сортировки) и решить, какой алгоритм был быстрее (в среднем).
Рафаэль
Пример «пузырчатая сортировка против быстрой сортировки» предназначен для того, чтобы показать необходимость / превосходство асимптотического анализа над сравнительным анализом в некоторых очевидных случаях. Вы можете увидеть резкую разницуNN
N