目录
此章节实际上是
数据结构与算法分析——C语言描述（第2章 算法分析）https://www.cnblogs.com/kirin-dev/p/Data-Structures_Chapter-2.html 的延展。
2.1 引言
所谓程序性能(program performance)，是指运行一个程序所需要的内存大小和时间。
可以采用两种方法来确定一个程序的性能，一个是分析的方法，一个是实验的方法。在进行性能分析(performance analysis)时，采用分析的方法，而在进行性能测量(performance measurement)时，借助于实验的方法。
程序的空间复杂性(space complexity)是指运行完一个程序所需要的内存大小。
对一个程序的空间复杂性感兴趣的主要原因如下：
- 如果程序将要运行在一个多用户计算机系统中，可能需要指明分配给该程序的内存大小。
- 对任何一个计算机系统，想提前知道是否有足够可用的内存来运行该程序。
- 一个问题可能有若干个内存需求各不相同的解决方案。
- 可以利用空间复杂性来估算一个程序所能解决的问题的最大规模。
程序的时间复杂性(time complexity)是指运行完该程序所需要的时间。
对一个程序的时间复杂性感兴趣的主要原因如下：
- 有些计算机需要用户提供程序运行时间的上限，一旦达到这个上限，程序将被强制结束。因此我们希望能提供一个稍大于所期望运行时间的时间上限。
- 正在开发的程序可能需要提供一个满意的实时响应。根据程序或程序模块的时间复杂性，可以决定其响应时间是否可以接受，如果不能接受，要么重新设计正在使用的算法，要么为用户提供一台更快的计算机。
- 如果有多种可选的方案来解决一个问题，那么具体决定采用哪一个主要基于这些方案之间的性能差异。对于各种解决方案的时间及空间复杂性将采用加权的方式进行评价。
2.2 空间复杂性(space Complexity)\(S_p(n)\)
2.2.1 空间复杂性的组成
- 指令空间(instruction space)——用来存储经过编译之后的程序指令所需的空间
- 数据空间(data space)——用来存储所有常量和所有变量值所需的空间
- 环境栈空间(environment stack space)——用来保存函数调用返回时恢复运行所需要的信息
- 指令空间
程序所需要的指令空间的数量取决于如下因素：
- 把程序编译成机器代码的编译器
- 编译时实际采用的编译器选项
- 目标计算机
- 数据空间
数据空间由两个部分构成：
- 存储常量和简单变量所需要的空间
- 存储复合变量所需要的空间（这一类空间包括数据结构所需的空间及动态分配的空间）
- 环境栈空间
每当一个函数被调用时，下面的数据将被保存在环境栈中：
- 返回地址
- 函数被调用时所有局部变量的值以及传值形式参数的值（仅对于递归函数而言）
- 所有引用参数及常量引用参数的定义
- 小结
至此，可以把一个程序所需要的空间分成两部分：
- 固定部分，它独立于实例的特征。
一般来说，这一部分包含指令空间（即代码空间）、简单变量及定长复合变量所占用空间、常量所占用空间等等。 - 可变部分，它由以下部分构成：
复合变量所需的空间（这些变量的大小依赖于所解决的具体问题）
动态分配的空间（这种空间一般都依赖于实例的特征）
递归栈所需的空间（该空间也依赖于实例的特征）。
所以，任意程序\(P\)所需要的空间\(S(P)\)可以表示为：
\(S(P)\) = \(c\) + \(S_p(实例特征)\)
2.2.2 举例
2.3 时间复杂性(time complexity)\(T(n)\)
2.3.1 时间复杂性的组成
类似的，任意程序\(P\)所占用的时间\(T(P)\)可以表示为：
\(T(P)\) = 编译时间 + \(t_p(实例特征)\)
在解析地分析时间复杂度时，使用以下两种时间单位并计算：
- 操作计数(operation count)：算法的基本操作
- 执行步数(step count)：分析全部程序
2.3.2 操作计数
估算一个程序或函数的时间复杂性的一种方式就是首先选择一种或多种操作 (如加、乘和比较等)，然后确定这种(些)操作分别执行了多少次。这种方法是否成功取决于识别关键操作的能力，这些关键操作对时间复杂性的影响最大。
最好、最坏和平均操作数
2.3.3 执行步数
程序步(program step)可以定义为一个语法或语义意义上的程序片段，该片段的执行时间独立于实例特征。
可以通过创建一个全局变量count (其初值为0 )来确定一个程序或函数为完成其预定任务所需要的执行步数——把count 引入到程序语句之中，每当原始程序或函数中的一条语句被执行时，就为count累加上该语句所需要的执行步数。当程序或函数运行结束时所得到的count的值即为所需要的执行步数。
2.4 渐进符号
定义：如果存在正常数\(c\)和\(n_0\)使得当\(N≥n_0\)时\(T(N)≤cf(N)\)，则记为\(T(N)=O(f(N))\)。（此时称\(f(N)\)为\(T(N)\)的上界(upper bound)）
定义：如果存在正常数\(c\)和\(n_0\)使得当\(N≥n_0\)时\(T(N)≥cg(N)\)，则记为\(T(N)=Ω(g(N))\)。（此时称\(g(N)\)为\(T(N)\)的下界(lower bound)）
定义：当且仅当\(T(N)=O(h(N))\)且\(T(N)=Ω(h(N))\)时，\(T(N)=Θ(h(N))\)。
定义：如果\(T(N)=O(p(N))\)且\(T(N)≠Θ(p(N))\)，则\(T(N)=o(p(N))\)。
对此定义进行数学推导，有以下3条结论。
法则1：如果\(T_1(N)=O(f(N))\)且\(T_2(N)=O(g(N))\)，那么
(a)\(T_1(N)+T_2(N)=max(O(f(N))，O(g(N)))\)。
(b)\(T_1(N)*T_2(N)=O(f(N)*g(N))\)。
法则2：如果\(T(N)\)是一个\(k\)次多项式，则\(T(N)=Θ(N^2)\)。
法则3：对任意常数\(k\)，\(\log^kN=O(N)\)。也就是说对数增长得非常缓慢。
可以通过计算极限\(\lim_{n\to \infty}f(N)/g(N)\)来确定两个函数的相对增长率。
- 极限是\(0\)：\(f(N)=o(g(N))\)。
- 极限是\(c≠0\)：\(f(N)=Θ(g(N))\)。
- 极限是\(\infty\)：\(g(N)=o(f(N))\)。
- 极限摆动：二者无关。