Big Oh是唯一用于衡量STL复杂性的符号

Question

我已经开始阅读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]而不是使用(theta),因为当我读到(theta)时所说的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)之间有什么区别？

Answer 1

为什么我们把这种复杂性称为f(x)= O(n)[n的大哦]而不是使用(theta)

Theta可能有助于描述特定算法的行为方式.但是STL - 或者一般的C++标准库 - 不是单个实现,因此您无法描述它的行为方式.

STL的描述是关于实现选择的算法必须如何表现的一组要求.复杂性是这些要求的一部分.要求论证的复杂性必须至少是某种东西是没有意义的.只有上限是相关的.因此,Big-O使用.

我们应该使用什么样的符号来衡量空间复杂性

Big-O表示法也可用于空间复杂性.