共计 1192 个字符，预计需要花费 3 分钟才能阅读完成。
工夫复杂度
（1）工夫频度 一个算法执行所消耗的工夫，从实践上是不能算进去的，必须上机运行测试能力晓得。但咱们不可能也没有必要对每个算法都上机测试，只需晓得哪个算法破费的工夫多，哪个算法破费的工夫少就能够了。并且一个算法破费的工夫与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它破费工夫就多。一个算法中的语句执行次数称为语句频度或工夫频度。记为 T(n)。
（2）工夫复杂度 在方才提到的工夫频度中，n 称为问题的规模，当 n 一直变动时，工夫频度 T(n) 也会一直变动。但有时咱们想晓得它变动时出现什么法则。为此，咱们引入工夫复杂度概念。个别状况下，算法中基本操作反复执行的次数是问题规模 n 的某个函数，用 T(n)示意，若有某个辅助函数 f(n), 使得当 n 趋近于无穷大时，T(n)/f(n)的极限值为不等于零的常数，则称 f(n)是 T(n)的同数量级函数。记作 T(n)=O(f(n)), 称O(f(n)) 为算法的渐进工夫复杂度，简称工夫复杂度。
另外，下面公式中用到的 Landau 符号其实是由德国数论学家保罗·巴赫曼（Paul Bachmann）在其 1892 年的著述《解析数论》首先引入，由另一位德国数论学家艾德蒙·朗道（Edmund Landau）推广。Landau 符号的作用在于用简略的函数来形容简单函数行为，给出一个上或下（确）界。在计算算法复杂度时个别只用到大 O 符号，Landau 符号体系中的小 o 符号、Θ 符号等等比拟不罕用。这里的 O，最后是用大写希腊字母，但当初都用大写英语字母 O；小 o 符号也是用小写英语字母 o，Θ 符号则维持大写希腊字母 Θ。
T(n) = Ο(f (n)) 示意存在一个常数 C，使得在当 n 趋于正无穷时总有 T (n) ≤ C f(n)。简略来说，就是 T(n)在 n 趋于正无穷时最大也就跟 f(n)差不多大。也就是说当 n 趋于正无穷时 T (n)的上界是 C f(n)。其尽管对 f(n)没有规定，然而个别都是取尽可能简略的函数。例如，O(2n2+n +1) = O (3n2+n+3) = O (7n2 + n) = O (n2)，个别都只用 O(n2)示意就能够了。留神到大 O 符号里暗藏着一个常数 C，所以 f(n)里个别不加系数。如果把 T(n)当做一棵树，那么 O(f(n))所表白的就是树干，只关怀其中的骨干，其余的细枝末节全都摈弃不论。
在各种不同算法中，若算法中语句执行次数为一个常数，则工夫复杂度为 O(1), 另外，在工夫频度不雷同时，工夫复杂度有可能雷同，如 T(n)=n2+3n+ 4 与 T(n)=4n2+2n+ 1 它们的频度不同，但工夫复杂度雷同，都为 O(n2)。按数量级递增排列，常见的工夫复杂度有：常数阶 O(1), 对数阶 O(log2n), 线性阶 O(n), 线性对数阶 O(nlog2n), 平方阶 O(n2)，立方阶 O(n3),...，k 次方阶 O(nk), 指数阶 O(2n)。随着问题规模 n 的一直增大，上述工夫复杂度一直增大，算法的执行效率越低。