本节书摘来自异步社区《趣题学算法》一书中的第0章0.6节算法运行时间的渐近表示，作者徐子珊,更多章节内容可以访问云栖社区“异步社区”公众号查看。
0.6 算法运行时间的渐近表示
由于计算机技术不断地扩张其应用领域，所要解决的问题输入规模也越来越大，所以对固定的n来计算T(n)的意义并不大，我们更倾向于评估当n→∞时T(n)趋于无穷大的快慢，并以此来分析算法的时间复杂性。我们往往用几个定义在自然数集N上的正值函数Ỹ(n)：幂函数nk（k为正整数），对数幂函数lgkn（k为正整数，底数为2）和指数函数an（a为大于1的常数）作为“标准”，研究极限
lim_{ntoinfty}frac{T(n)=lambda }{widetilde{Y}(n)} （0-1）
若λ为一正常数，我们称Ỹ(n)是T(n)的渐近表达式，或称T(n)渐近等于Ỹ(n)，记为T(n)=Θ(Ỹ(n))，这个记号称为算法运行时间的渐近Θ-记号，简称为Θ-记号。例如，算法0-1的运行时间为T(n)=2n2+4n+3，取Ỹ(n)=n2，由于
lim {}_{nto infty }^{{}} frac{T(n)}{widetilde{Y}(n)}=lim_{nquad}^{{}} frac{2{{n}^{2}}+4n+3}{{{n}^{2}}}=2ne 0
所以，我们有T(n)=Θ(n2)，即此T(n)渐近等于n2。其实，在一个算法的运行时间T(n)中省略最高次项以外的所有项，且忽略最高次项的常数系数，就可得到它的渐近表达式。例如，用此方法也能得到算法0-1的运行时间T(N)=3N2/2+N/2+2=Θ(N2)，算法0-2的运行时间T(N)= 3N2/2+N/2=Θ(N2)。在这个意义上，我们可以再次断言——算法0-1和算法0-2是等价的。
如果两个算法的运行时间的渐近表达式相同，则将它们视为具有相同的时间复杂度的算法。显然，渐近时间为对数幂的算法优于渐近时间为幂函数的算法，而渐近时间为幂函数的算法则优于渐近时间为指数函数的算法。我们把渐近时间为幂函数的算法称为具有多项式时间的算法。渐近时间不超过多项式的算法我们称其为有效的算法。通常认为运行时间为指数式的算法不是有效的。
渐近记号除了Θ外，还有两个常用的记号O和Ω。它们的粗略意义如下：
考察定义域为自然数集N的正值函数Ỹ(n)和T(n)构成的极限式0-1的值λ，若λleqslant1为一常数，则称函数T(n)渐近不超过函数Ỹ(n)，记为T(n) = O (Ỹ(n))；若λ>1为常数或为+∞，则称函数T(n)渐近不小于函数Ỹ(n)，记为T(n)= Ω(Ỹ(n))。例如lgkn=O(nk)，反之，lgkn=Ω(nk)。显然，T(n)=Θ(Ỹ(n))当且仅当T(n) = O (Ỹ(n))且T(n)= Ω(Ỹ(n))。对算法运行时间的深入讨论读者可参考配书的短视频“算法的运行时间”。
下面我们用以上讨论过的概念、术语、记号和方法再讨论一个计算问题。
问题描述
假定在坦佩雷〔芬兰城市〕地区的第四代移动电话基站如下述方式运行。该地区划分成很多四方块，这些四方形的小区域形成了S×S矩阵。该矩阵的行、列均从0开始编码至S-1。每个方块区域包含一个基站。方块内活动的手机数量是会发生变化的，因为手机用户可能从一个方块区域进入到另一个方块区域，也有手机用户开机或关机。每个基站会报告所在区域内手机活动数的变化。
写一个程序，接收这些基站发来的报告，并应答关于指定矩形区域内的活动手机数的查询。
输入
输入从标准输入设备中读取表示查询的整数并向标准输出设备写入整数以应答查询。输入数据的格式如下。每一行输入数据包含一个表示指令编号的整数及一些表示该指令的参数。指令编号及对应参数的意义如下表所示。
终止程序。该指令也仅发送一次，且必为最后一条指令
假定输入中的各整数值总是在合法范围内，无需对它们进行检验。具体说，例如A是一个负数，它不可能将某一方块区域中的手机数减小到0以下。下标都是从0开始的，即若矩阵规模为4×4，必有0leqslantXleqslant3且0 leqslantYleqslant3。
我们假定：
矩阵规模：1×1leqslantS×Sleqslant1024×1024。
任何时候方块区域内的活动手机数：0leqslantVleqslant32767。
修改值：−32768leqslantAleqslant32767。
不存在指令号：3leqslantUleqslant60002。
整个区域内的最大活动手机数：M= 230。
输出
你的程序对除了编号为2以外的指令无需做任何应答。若指令编号为2，程序须向标准输出设备写入一行应答的答案。
输入样例
0 4
1 1 2 3
2 0 0 2 2
1 1 1 2
1 1 2 -1
2 1 1 2 3
3
输出样例
3
4
解题思路
（1）数据的输入与输出
根据输入文件的格式，测试案例由若干条指令组成，每条指令占1行。依次读取各条指令存放于数组cmds中。指令3为结束标志。对指令序列cmds逐一执行，对指令2保存执行结果于数组result中。所有指令执行完毕后，将result中的数据逐行输出到输出文件。
1 打开输入文件inputdata
2 创建输出文件outputdata
3 创建指令序列cmds←Ø
4 从inputdata中读取案例数据cmd
5 while cmd≠3
6 do if cmd=0
7 then 从inputdata中读取S
8 INSERT(cmds, (cmd, S))
9 else if cmd=1
10 then 从inputdata中读取X, Y, A
11 INSERT(cmds, (cmd, X, Y, A))
12 else 从inputdata中读取L, B, R, T
13 INSERT(cmds, (cmd, L, B, R, T))
14 从inputdata中读取cmd
15 result←MOBIL-PHONE(cmds)
16 for each rresult
17 do 将r作为一行写入outputdata
18 关闭inputdata
19 关闭outputdata
其中，第15行调用计算指令序列cmds显示结果的过程MOBIL-PHONE(cmds)是解决一个案例的关键。
（2）解决一个案例的算法过程
首先创建数组result用来存储查询指令（指令2）的执行结果。cmds[1]是指令0，它的参数s决定了坦佩雷地区移动通信网的规模。用S创建一个二维数组tampere[0..S-1, 0..S-1]，并将所有元素初始化为0。从i=2开始逐一执行指令cmds[i]。若cmds[i]是指令1，则用其参数x, y, a在tamperex累加a。若cmds[i]是指令2，则在其参数l，b，r，t指定的（l, b）为左下角，（r, t）为右上角的范围内计算移动电话的数量，将计算结果加入数组result中。所有指令执行完毕后，返回result。
MOBIL-PHONE(cmds)
1 n←length[cmds]
2 析取指令cmds[1]的参数S
3 创建二维数组tampere[0..S-1, 0..S-1]并将元素初始化为0
4 创建数组result←Ø
5 for k←2 to n
6 do 从cmds[k]中析取cmd
7 if cmd=1
8 then 从cmds[k]中析取参数X, Y, A
9 tampere[X][Y] ← tampere[X][Y]+A
10 if tampere[X][Y]<0
11 then tampere[X][Y]=0
12 else从cmds[k]中析取参数L, B, R, T
13 count←0
14 for i←L to R
15 do for j←B to T
16 do count←count+tampere[i][j]
17 INSERT(result, count)
18 return result
算法0-3 解决“移动电话”问题的算法过程
这个算法的代码结构类似于算法0-1，算法的结构主体是嵌套在一起的若干个循环。由于我们用渐近表达式表示算法的运行时间，所以对这种结构的算法，在算法分析时循环之外常数时间完成的操作可以不予考虑。例如，本算法中第1～4行及第18行的操作，分析时可忽略。我们把目光聚焦于第5～17行的for循环。这个循环共重复Θ(n)（准确地说是n−1，但作为渐近式与n等价）次。循环体中是一个分支结构，分支之一是处理指令1的第8～11行操作，耗时为常数Θ(1)（准确地说是4，渐进等价于1）。另一分支是处理指令2的第12～17行，该分支中，除了第12、13、17行的常数时间操作外（第17行是在数组result的尾部添加新的元素，耗时亦为Θ(1)），第14～16行是一个两重嵌套for循环。这两重循环分别重复r-l和t-b次。循环体内的操作耗时Θ(1)（1次赋值操作）。所以这两重循环的耗时为Θ((R-L)(T-B))。这个结果看起来似乎很精致，但实际上我们并不知道L，B，R，T的具体值，但我们知道0leqslantL，B，R，TleqslantS。也就是说必有0leqslantR-L, T-BleqslantS。因此，用渐近表达式我们可以将这个嵌套循环的耗时记为O(S2)（意味着耗时不差过S2）。再由于它内嵌于第5～17行的最外层for循环之内，若n条指令中指令2数目m占有一定比例（即存在常数c使得n=cm）则第12～17行的操作耗时可表为O(nS2)。于是，我们得出算法0-3的运行时间为O(nS2)。
