Is Big Oh the only notation used to measure complexity in STL
I have started reading C++ STL and also found a book for that!. while i was reading the complexity,which plays major role in choosing algorithms and data structures i have been seeing that the Big Oh notation was only used with different variables(O(n),O(log(n).,) and by further surfing i found the Big Oh denotes 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)
So my question is, if an algorithms time complexity always results equal to the growth of g(x), why we mention that complexity as f(x)=O(n)[Big oh of n] rather than using (theta), because when i read about (theta) that said f(x) = Θ(g(x)) (theta) means that the growth rate of f(x) is asymptotically equal to the growth rate of g(x)
Here the notation possibly be (theta) instead of O(N) wasn't it? or any reason for using big oh.
And what notation should we use to measure the space complexity.i don't see anything talks about space complexity regard STL in that book.
reference: What is the difference between Θ(n) and O(n)?
why we mention that complexity as f(x)=O(n)[Big oh of n] rather than using (theta)
Theta might be useful in describing how a particular algorithm behaves. But STL - or the C++ standard library in general - isn't a single implementation, so you can't describe how it behaves.
The description of STL is a set of requirements on how the algorithms chosen by an implementation must behave. The complexities are part of those requirements. It makes no sense to require that the complexity of an argument must be at least something. Only the upper limit is relevant. Therefore, the Big-O used.
And what notation should we use to measure the space complexity
Big-O notation can be used for space complexity as well.
So my question is, if an algorithms time complexity always results equal to the growth of g(x), why...
This is not true. For instance the complexity of the sort is Big-oh n*log(n) but may come down to linear in some cases.It is rare case that we can give theta approximation for an algorithm.
Also usually the standard gives big-oh guarantees for the functions, but I haven't seen any theta restrictions there.
And what notation should we use to measure the space complexity.
Big-oh is a notation for function growth and can be used both for space and time complexity.
一个原因是如果实现者想出了一个算法（例如）是线性的而不是O（n log n），那么如果函数被指定为Θ（n log n），则它们将不被允许使用它。
链接地址: http://www.djcxy.com/p/40154.html上一篇: 朴素贝叶斯：不平衡测试数据集
下一篇: Big Oh是衡量STL复杂性的唯一符号