主要内容:大O表示法;(一句话:忽略常数因子和低阶项)
大O表示法的导入:我们常常会探讨一个运算过程它的时间复杂度。比如6nlog2(n)+6n.我们忽略低阶和常数项,得到一个更简单的表达式nlogn.精简它的运行时间是“nlogn的大O时间",我们记作O(nlogn).这样分类后我们会得到一些常用的时间算法。有线性(O(n)),(O(nlogn))时间算法,平方(O(n*2))时间算法,常数(O(1)时间算法等。
用我自己的话来说,就是你现在计算这个程序的运行时间假设是一个函数表式f(n).那么此时它需要转换成我们上述的几种常见的精简的表达形式。即我们的大O表示法,然而该怎么转换呢?先放一个数学表达式:T(n)<=c*f(n).
其中T(n)即大O表达式,T(n)=Of(n).博弈视角我觉得很好理解:我们自己选一个常数c和n0,然后对方试图找一个n>=n0的数满足T(n)>c*f(n).如果他找到了,那我们输了,这个T(n)不是它的大O表达式,如果他找不出来,那我们赢了,说明我们T(n)是他的大O表达式。总结就是T(n)的上界实际上是由f(n)的常数积确定的,所以我们可以说T(n)=Of(n)。