Существует ли основной список обозначений Big-O для всего?
https://stackoverflow.com/questions/180510
-
05-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Существует ли основной список обозначений Big-O для всего? Структуры данных, алгоритмы, операции, выполняемые для каждого, среднего случая, наихудшего случая и т. Д.
Решение
Словарь алгоритмов и структур данных представляет собой довольно полный список, включающий сложность (большой О) в описании алгоритмов. Если вам нужна дополнительная информация, она будет указана в одной из ссылок, и в качестве запасного варианта всегда есть Википедия.
Другие советы
книга Кормена больше рассказывает о том, как доказать, что такое Большой -O будет для данного алгоритма, а не для запоминания алгоритма до его производительности Big-O. Первое гораздо ценнее второго и требует вложений с вашей стороны.
Попробуйте Введение в алгоритмы " Кормен, Лейзерсен и Ривест. Если его там нет, его, вероятно, не стоит знать.
В c ++ стандарты STL определяются характеристиками алгоритмов Big-O, а также требованиями к пространству. Таким образом, вы можете переключаться между конкурирующими реализациями STL и при этом знать, что ваша программа имеет одинаковые характеристики времени выполнения. Особенно хорошие реализации STL могут даже списки особых случаев определенных типов быть лучше, чем стандартные требования.
Это позволило легко выбрать правильный итератор или тип списка для конкретной задачи, потому что вы могли легко взвесить между потреблением места и скоростью.
Ofcourse Big-O - это только направляющая линия, поскольку все константы удалены. Если алгоритм работает в k * O (n), он будет классифицирован как O (n), но если k достаточно высокий, он может быть хуже, чем O (n ^ 2) для некоторых значений n и m.
Введение в алгоритмы, второе издание , также известное как CLRS (Cormen, Leiserson, Rivest, Stein) , это самое близкое, что я могу придумать.
Если это не помогло, попробуйте Искусство компьютерного программирования Кнут. Если это не так, вам, вероятно, нужно провести какое-то реальное исследование.
Всем, кто подходит к этому вопросу из Google.
