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

Question

我已经开始阅读 C++ STL 并且还找到了一本书!当我阅读复杂性时，它在选择算法和数据结构方面起着重要作用，我已经看到 Big Oh 符号仅用于不同的变量(O(n)，O(log(n)。，)并进一步冲浪我发现Big Oh 表示 f(x) = O(g(x))--(big-oh) 表示 f(x) 的增长率渐近小于或等于 g( x)

所以我的问题是，如果一个算法的时间复杂度总是等于 g(x) 的增长，为什么我们提到这个复杂度为 f(x)=O(n)[n 的大哦] 而不是使用 (theta)，因为当我读到 (theta) 时说 f(x) = Θ(g(x)) (theta) 意味着 f(x) 的增长率是渐近的等于 g(x) 的增长率

这里的符号可能是 (theta) 而不是 O(N) 不是吗？或使用大哦的任何原因。

我们应该使用什么符号来衡量空间复杂度。我在那本书中没有看到任何关于空间复杂度关于 STL 的讨论。

引用:What is the difference between Θ(n) and O(n)?

Answer 1

why we mention that complexity as f(x)=O(n)[Big oh of n] rather than using (theta)

Theta 可能有助于描述特定算法的行为方式。但是 STL - 或者一般的 C++ 标准库 - 不是一个单一的实现，所以你无法描述它的行为方式。

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

And what notation should we use to measure the space complexity

大 O 符号也可用于空间复杂度。