Является ли Big Oh единственным обозначением, используемым для измерения сложности в STL
Я начал читать C ++ STL, а также нашел книгу для этого! в то время как я читал сложность, которая играет главную роль в выборе алгоритмов и структур данных, я видел, что нотация Big Oh использовалась только с различными переменными (O (n), O (log (n).,)) и другими я нашел серфинг
Большой О обозначает f(x) = O(g(x))--(big-oh) means that the growth rate of f(x) is asymptotically less than or equal to to the growth rate of g(x)
Поэтому мой вопрос: если временная сложность алгоритмов всегда равна росту g (x), почему мы упоминаем эту сложность как f(x)=O(n)[Big oh of n] вместо того, чтобы использовать (тета), потому что, когда я прочитал о (тета), что сказал f(x) = Θ(g(x)) (theta) means that the growth rate of f(x) is asymptotically equal to the growth rate of g(x)
Здесь обозначение может быть (тета) вместо O (N), не так ли? или любая причина для использования большой ой.
И какие обозначения мы должны использовать для измерения сложности пространства. Я не вижу ничего, что говорило бы о сложности пространства относительно STL в этой книге.
Решение
почему мы упоминаем эту сложность как f (x) = O (n) [Big oh of n] вместо использования (тета)
Тета может быть полезна для описания поведения конкретного алгоритма. Но STL — или стандартная библиотека C ++ в целом — не единственная реализация, поэтому вы не можете описать, как она ведет себя.
Описание STL — это набор требований к тому, как должны вести себя алгоритмы, выбранные реализацией. Сложности являются частью этих требований. Нет смысла требовать, чтобы сложность аргумента была хоть чем-то. Актуален только верхний предел. Поэтому Big-O использовали.
И какие обозначения мы должны использовать для измерения сложности пространства
Обозначение Big-O также может использоваться для пространственной сложности.
Другие решения
Поэтому мой вопрос: если временная сложность алгоритмов всегда приводит к росту g (x), почему …
Это неправда. Например, сложность сортировки — Big-oh n * log (n), но в некоторых случаях может быть линейной. В редких случаях мы можем дать тета-аппроксимацию для алгоритма.
Также обычно стандарт дает большие гарантии для функций, но я не видел там никаких тэта-ограничений.
И какие обозначения мы должны использовать для измерения сложности пространства.
Big-oh — это обозначение для роста функций и может использоваться как для пространственной, так и для временной сложности.
Одна из причин заключается в том, что, если разработчик придумал алгоритм, который был (например) линейным, а не O (n log n), им было бы запрещено использовать его, если функция была указана как Θ (n log n).