Есть ли главный список нот Big-O для всего?

Question

Есть ли главный список нот Big-O для всего? Структуры данных, алгоритмы, операции, выполняемые в каждом случае, в среднем случае, в худшем случае и т. Д.

Answer 1

Dictionary of Algorithms and Data Structures - довольно полный список и включает в себя сложность (Big-O) в описаниях алгоритмов. Если вам нужна дополнительная информация, она будет в одной из связанных ссылок, и всегда есть Wikipedia в качестве резервной копии.

Answer 2

Попробуйте «Introduction to Algorithms» от Cormen, Leisersen и Rivest. Если его там нет, то его, вероятно, не стоит знать.

Answer 3

Introduction to Algorithms, Second Edition, aka CLRS (Cormen, Leiserson, Rivest, Stein), является ближайшей вещью, о которой я могу думать.

Если это не удается, попробуйте The Art of Computer Programming, от Knuth. Если это не так, вам, вероятно, нужно провести какое-то настоящее исследование.

Answer 4

Cormen book больше о том, как научить вас, как доказать, что Big-O будет для данного алгоритма, а не записывать алгоритм в его производительность Big-O. Первый гораздо более ценен, чем последний, и требует инвестиций с вашей стороны.

Answer 5

В C++ стандарты STL определяются характеристиками алгоритма Big-O, а также требованиями к пространству. Таким образом, вы можете переключаться между конкурирующими реализациями STL и все еще знать, что ваша программа имеет те же самые характеристики времени выполнения. Особо хорошими реализациями STL могут быть даже специальные списки конкретных типов, чтобы быть лучше стандартных требований.

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

Ofcourse Big-O - это только направляющая линия, так как все константы удалены. Если алгоритм работает в k * O (n), он будет классифицирован как O (n), но если k достаточно высоко, он может быть хуже O (n^2) для некоторых значений n и m.

Answer 6

Кому, кто подходит к этому вопросу из Google.

http://bigocheatsheet.com/