Big Oh是衡量STL复杂性的唯一符号
我已经开始阅读C ++ STL，并为此找到了一本书！ 当我读到复杂性时，它在选择算法和数据结构中起主要作用，我已经看到Big Oh表示法只用于不同的变量（O（n），O（log（n）。），并且进一步冲浪我发现Big Oh表示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的书。
参考：Θ（n）和O（n）之间的区别是什么？
为什么我们提到复杂度为f（x）= O（n）[大哦]，而不是使用（theta）
Theta在描述特定算法的行为方面可能很有用。 但是STL（或通常的C ++标准库）不是一个单独的实现，因此您无法描述它的行为。
STL的描述是关于实现选择的算法如何表现的一组要求。 复杂性是这些要求的一部分。 要求争论的复杂性至少应该是某种东西是没有意义的。 只有上限是相关的。 因此，大O使用。
我们应该用什么符号来测量空间复杂度
大O符号也可用于空间复杂性。
所以我的问题是，如果算法时间复杂度总是等于g（x）的增长，为什么...
这不是真的。 例如，这种排序的复杂性就是Big-oh n * log（n），但在某些情况下可能会降低到线性。我们可以给出一个算法的theta近似值。
通常这个标准也为这个功能提供了很大的保证，但是我没有看到任何theta限制。
我们应该用什么符号来测量空间复杂度。
Big-oh是功能增长的符号，可用于空间和时间复杂性。
一个原因是如果实现者想出了一个算法（例如）是线性的而不是O（n log n），那么如果函数被指定为Θ（n log n），则它们将不被允许使用它。
链接地址: http://www.djcxy.com/p/40153.html上一篇: Is Big Oh the only notation used to measure complexity in STL
下一篇: What is the Difference between T(n) (reccurence relations), Big O and Big Theta