Зачем изучать теорию сложности?

Question

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

В качестве примера известно, что разработка алгоритма для определения идеальной шахматной игры можно сделать в $ o (1) $ , как число законных Шахматные игры на 8 × 8 сетки ограничены сверху. Однако я слышал, что этот алгоритм займет больше возраста вселенной, чтобы прекратить. Это просит вопрос, почему теория сложности? Мне кажется, что поле принципиально ошибочно, и компьютерные ученые должны использовать лучший подход к изучению алгоритмов.

(Примечание: мои искренние извинения исследователям в поле. ☻)

Answer 1

Это не простой вопрос, и вы не должны ожидать простого ответа. В этом пространстве есть ряд подобных вопросов: почему мы изучаем асимптотическое время работы? Почему мы используем асимптотический анализ времени работы для анализа алгоритмов? Почему мы изучаем теорию сложности? Каждый из них имеет несколько ответов; Существует не только одна причина, по которой мы это делаем, и разные люди могут иметь разные причины.

Асимптотический анализ времени работы имеет преимущества и недостатки. Вы точно определили одно из недостатков: хорошее асимптотическое время работы не гарантирует хорошее время работы на практике. Но если вы сосредоточены только на одном преимуществе или недостатке, вы не собираетесь получить полную картину сильных и слабых сторон этого стиля анализа. Некоторые из преимуществ являются тот анализ относительно прочности, он не специфичен для конкретной архитектуры, оно обеспечивает полезную информацию о масштабируемости и, по крайней мере, некоторое время, которое она имеет полезную прогнозную мощность при идентификации алгоритмических узких мест. Например, разница между $ O (N ^ 2) $ Algorithm и $ O (n \ log n ) $ алгоритм времени часто может быть значительным, даже если мы игнорируем постоянные факторы. Некоторые из недостатков являются то, что постоянные факторы могут быть важны, эффекты иерархии кеша и памяти могут быть очень важны, все еще игнорируются асимптотическим анализом времени эксплуатации, и (например, любая метрика), оптимизирующая исключительно для асимптотического времени работы, может привести к абсурдным игре. Утилита (см. Галактические алгоритмы и Закон GoodHart ).

Я думаю, что это также полезно изучить альтернативу. Я рекомендую вам исследовать альтернативу асимптотическому анализу времени бега и работать через то, что вы предлагаете в целях. Если вы не пытаетесь придумать конкретное предложение, легко предположить, что это трудно найти что-то лучшее ... но когда вы вынуждены совершать что-то конкретное, вы можете обнаружить, что это более сложные, чем вы ожидали. Например, я рекомендую вам ознакомиться с анализом Алгоритма Knuth of AlgorithM Time On Ta Href="https://en.wikipedia.org/wiki/mix" rel="nofollow noreferrer"> Mix в его TaoCP Series. Там он делает бетонный анализ времени работы, без асимптотики с учетом постоянных факторов. Если вы заставляете себя работать через детали того, что вы быстро обнаружите недостатки этого: это сверхудомонтировано, очень специфичное для конкретной компьютерной архитектуры, и часто не гораздо более просвещается.

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

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

Поскольку вы попросили теоретические рамки, которые сосредоточены на потребностях в соблюдении индустрии, вы также можете быть заинтересованы в Word Ram Модель, Кэш-Облепляющие алгоритмы и Параллельная внешняя память модели.

Я настоятельно рекомендую вам прочитать следующие ресурсы, поскольку они тесно связаны с вашим вопросом: Поэтому называется полиномиальное время Эффективно "? , Объяснение актуальности асимптотической сложности алгоритмов для практики проектирования алгоритмов , Обоснование для пренебрежения постоянными факторами в Big O .