浅谈时间复杂度

复杂度"/>

浅谈时间复杂度

渐进时间复杂度的含义

时间复杂度有多种，大O表示法是代表渐进时间复杂度。
在这里大O是渐近上界的记号。除了渐进上界O，还有渐近下界记号Ω,紧渐近界记号Θ。
假设，对所有n，f(n) >= 0，g(n) >= 0。
O(g(n)) = { f(n) | 存在正常数c和n0使得对所有n>= n0有：0 <= f(n) <=cg(n) }。
用图片表示就是：

在这种情况下，我们一般习惯记为f(n)=O(g(n))，实际上这里是等号的滥用，更应该是记录为f(n)∈O(g(n))，因为这里表示是函数f(n)是O这个集合中的一个元素。但是我们还是依照约定的习惯记法，记作等号。
在实际算法分析中，O(g(n))的值等于循环最多次数的代码块的次数。
比如：某个方法的计算步与数据规模x的关系是x²+2x+10,那么这个方法的渐进时间复杂度就为n²。

渐进时间复杂度的比较

既然计算出了渐进时间复杂度，就是为了比较不同代码的效率。时间复杂度越小的代码越好。
渐进时间复杂度的比较如下图：也就是：Log n<n<nlog n<n²<2^n。