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

Ответ 1

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

Ответ 2

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

Ответ 3

Попробуйте " Введение в алгоритмы" Cormen, Leisersen и Rivest. Если его там нет, то его, вероятно, не стоит знать.

Ответ 4

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

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

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

Ответ 5

Введение в алгоритмы, второе издание, aka CLRS (Cormen, Leiserson, Rivest, Stein), самое близкое, что я могу придумать.

Если это не удается, попробуйте "Искусство компьютерного программирования" от Кнута. Если это не так, вам, вероятно, нужно провести какое-то настоящее исследование.

Ответ 6

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

http://bigocheatsheet.com/