Ресурс по вычислительной временной сложности алгоритмов

Есть ли хороший ресурс (книга, ссылка, веб-сайт, приложение...), в котором объясняется, как вычислить временную сложность алгоритма?

Потому что трудно сделать вещи конкретными в моем сознании. Иногда речь идет об итерации с временной сложностью lg n; а затем в соответствии с другим циклом он становится n.lg n; и иногда они используют большие обозначения омеги, чтобы выразить это, иногда большие-о и т.д.

Эти вещи довольно абстрактны для меня. Итак, мне нужен ресурс, который имеет хорошее объяснение и множество примеров, чтобы заставить меня посмотреть, что происходит.

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

Ответы

Ответ 2

Ребята, вы все рекомендуете книги теории сложности сложности - Arora и Barak содержат всевозможные вещи, такие как PCP, Interactive Proofs, Quantum Computing и темы на графиках Expander - то, что большинство программистов/разработчиков программного обеспечения никогда не слышали о или когда-либо будет использоваться. Papdimitriou находится в той же категории. Кнуту нечего читать (и я был главным математиком в CS/Math) и дает нулевую интуицию о том, как все работает.

Если вы хотите простой способ вычислить время автономной работы и получить вкус анализа, попробуйте первую главу или около того Клейнберга и Тардоса "Дизайн и анализ алгоритмов", который держит вас за руку с помощью основ, а затем вы можете работать над гораздо более сложными проблемами.

Ответ 3

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

Ответ 4

Я согласен, что Введение в алгоритмы - хорошая книга. Для получения более подробных инструкций, например. как решить рекуррентные отношения см. Knuth Конкретная математика. Хорошая книга по самой вычислительной сложности - это Papadimitriou. Но эта последняя книга может быть слишком тщательной, если вы хотите рассчитать сложность данных алгоритмов.

Краткий обзор о значении большой O/-Omega:

  • Если вы можете дать алгоритм, который решает проблему во времени T (c * (n log n)) (c - константа), то временная сложность этой проблемы O (n log n). Big-O избавляется от c, то есть любые постоянные факторы, не зависящие от размера ввода n. Big-O дает верхнюю границу в течение времени выполнения, потому что вы показали (предоставив алгоритм), что вы можете решить проблему за этот промежуток времени.
  • Если вы можете дать доказательство, что любой алгоритм, решающий задачу, занимает не менее времени T (c * (n log n)), чем проблема в Omega (n log n). Big-Omega дает нижнюю границу по проблеме. В большинстве случаев нижние оценки гораздо труднее доказать, чем верхние оценки, потому что вы должны показать, что любой возможный алгоритм для задачи занимает не менее T (c * (n log n). Зная нижнюю границу, не означает знание алгоритма, достигающего этой нижней границы.
  • Если у вас есть нижняя граница, например. Omega (n log n), и алгоритм, который решает проблему за это время (верхнюю границу), чем проблема в Theta (n log n). Это означает, что известен "оптимальный" алгоритм для этой проблемы. Конечно, это обозначение скрывает постоянный множитель c, который может быть довольно большим (поэтому я написал оптимальное значение в кавычках).

Обратите внимание, что при использовании этих обозначений вы обычно говорите о наихудшем времени работы алгоритма.

Ответ 6

Классический набор книг на эту тему - это Knuth Art of Computer Programming. Они тяжелы в теории и формальных доказательствах, поэтому расчистите свое исчисление, прежде чем приступать к ним.