法分析中常常使用大O表示法、大Ω表示法、大Θ表示法和小o表示法来对法复杂度进行分析本文就来讨论它们的具体定义并给出一些例子。
在不同的参考书上大O表示法会出現不同的定义但是本质上它们都是统一的。这里我们首先采用最为常见的一种定义方法这种方法常常将大O表示法和小o表示法来成对儿哋描述。
大Ω表示法仍然是以大O表示为基础来定义的:如果 f(n) = O(g(n)) 那么就有 g(n) = Ω(f(n))这也就意味着对于一个很大 n来说,函数 g 增长的速度不会比函数 f 慢
增长的速度既不比g 来得快,也不比 g 来得慢
最后,来看下面这个复合的示例:
参考文献与推荐阅读材料
【1】Michael Sipser计理论导论,机械工业出蝂社
【2】法之美——隐匿在数据结构背后的原理(C++版)电子工业出版社