首先我们要明确一点，在编程领域中我们需要考虑的因素很多，算法性能只是其一，甚至不能算是最优先考虑的因素，人们往往更优先考虑的方面包括：正确性、健壮性、可维护性、界面交互体验等等。但是为什么我们又要一而再强调算法？
有种观点是，算法是编程领域的「通用货币」，即：为了追求某种更需要优先考虑的因素，而需要支付的代价。怎么样理解呢？比如大家都知道C语言比Java语言的性能强至少3倍，但是由于Java语言的平台通用性、异常处理机制等诱人的feature，现如今的商业项目往往会选择Java作为开发语言，而不是C语言，而为了弥补这3倍的性能差异，所以必须支付一定的代价以维持较好的性能，也即重视编程算法。
如果程序的运行环境、编程语言等各方面针对同一段程序无显著差异、存储空间无限大、CPU性能无限高，又何须劳神费力去研究算法性能？
记号𝛩
𝛩记号表示时间复杂度的渐近紧接界，简单来说就是近似刻画一个程序算法的时间复杂度函数。既然是函数，那我们就必须给出它在数学逻辑上的严格定义：
𝛩(g(n))表示如下函数的集合：
𝛩(g(n)) = { f(n)：存在正常量、
和
，使得对所有
，有
}
画图表示可能更为清晰，如下图所示：
image-20200128204019199.png
跟平常我们学的极限是否有亲切感？
注意到f(n)表示一个集合，也就是说程序的时间复杂度可能不是确定的值，而是某一类值的函数集合。这也是必然，例如同样的插入排序针对输入规模的不同、已排序程度的不同呈现出不同的时间复杂度，例如：已经是升序的输入序列、已经是降序的输入序列其时间复杂度是不一致的
我们再举个例子予以更清晰的认识，假设我们设计了某个程序，经过计算它的时间复杂度：
则根据我们以往的经验，立马可以认为T(n)=𝛩()。直觉很重要，但是我们还是应该给予严格的数学证明，按上述的数学定义，假设我们认定T(n)=𝛩(
)，那我们来个数学验证，很容易根据(1)式得到如下的公式，即存在正常量
、
和
，使得对所有
，有：
对(2)两边除以，可得如下公式：
很明显为使右式成立，只需要，即可对所有的n有效；为使左式成立，则需要
，则可对任何
的值有效，由此我们可以说：当
，
，且
时可以证明
。当然常量的取值还存在其它选择。
记号𝛰
这个符号大家应该都不陌生，一般书上都有说过，它是刻画一个程序的最坏时间复杂度，也即渐近上界，它在数学上的逻辑定义如下：
𝛰(g(n))表示如下函数的集合：
𝛰(g(n)) = { f(n)：存在正常量c和}
画图表示如下：
image-20200128203950508.png
它相比𝛩，只突出了上界，也即最坏情况。这种记号是非常有意义的，它相当于一种承诺，比如某段程序至多在多长时间内会返回结果，这往往是我们关注的重点，所以很多算法书上都只体现大𝛰。正如书上告诉我们的，插入排序的时间复杂度T(n)=𝛰()
记号𝛺
同样类似的，𝛺刻画的是一个程序的最佳时间复杂度，也即渐近下界，我们一般很少用它，它很可能用于某种欺诈，因为它无法刻画全部输入场景下的时间复杂度。我们同样给出它的数学逻辑定义：
𝛺(g(n))表示如下函数的集合：
𝛺(g(n)) = { f(n)：存在正常量c和}
画图表示如下：
image-20200128203908438.png
用得比较少，所以暂不多述。
综上所述，我们可以认为插入排序的时间复杂度是界于𝛺(n)与𝛰()之间的。
记号𝛐与𝛚
最后两个记号，简述一下吧。
小𝛐与大𝛰都是刻画渐近上界，但是它与大𝛰的区别在于，针对所有的常量c有效，而大O只针对某个c>0成立。
同样，小𝛚和大𝛺都是刻画渐近下界，但是它与大𝛺的区别在于， 针对所有的常量c有效，而大𝛺只针对某个c>0成立。
网友评论