《算法4第一章》笔记（六）基础理论相关

一个程序运行的总时间主要和两点有关：

1. 执行每条语句的耗时。
2. 执行每条语句的频率。

执行次数分析可能会产生复杂冗长的数学表达式。一般在这种表达式中，首相之后的其他项都相对较小。我们常常使用约等于号(~)来忽略较小的项。

典型的近似(数据量N)

一种典型的情况：许多程序的运行时间都只取决于其中的一小部分指令。

常见的增长数量级

数量增长级即为复杂度。f(N)~g(N)的正式定义为当N趋近于无穷大时，F(N)/g(N)=1。

可以用函数O(?)来表示复杂度性能的渐进上线。

复杂度分为时间复杂度和空间复杂度。

常数级别的增长数量级及可被称作时间复杂度为O(1)。

得到数学模型的步骤：

1. 确定输入模型，定义问题的规模。
2. 识别内循环。
3. 根据内循环中的操作确定成本模型。
4. 对于给定的输出，判断这些操作的执行频率。这可能用到数学分析。

常见函数

图

近似函数

图

常见算法复杂度假设

图

例子中的运行时间总结

算法设计中的注意事项

1. 大常数

   一般我们会忽略低级项中的常数系数。但这可能是错的，一旦低级项中的常熟系数足够大，该近似就是错误的。
   2. 非决定性的内循环
   > 错误的成本模型可能导致无法得到真正的内循环。
   3. 指令时间
   > 每条指令执行所需的时间总是相同的，这种假设并不总是正确的。例如，现在大多数系统都会使用缓存技术来组织内存。这种情况下方问答数组中的若干并不相邻的元素所需的时间可能很长。
   4. 系统因素
   > 多个程序之间抢占资源。
   5. 不分伯仲
   > 不同的运行环境影响执行效率。
   6. 对输入的强烈依赖
   > 有些问题会在输入为特定值时提前结束。
   7. 多个问题参量

如何处理对输入的依赖

1. 更小心的为输入建模。
2. 对最坏情况下的性能保障。
3. 随机化算法。(例，快速排序)
4. 考虑算法操作的步骤。
5. 均摊分析。

   通过记录所有操作的总成本并处以操作总数来讲成本均摊。