• Motivation
• Standard Approach
• Examples
• Simplifying with Worst Case and Big-O
• Recursive Examples

动机 Motivation

算法分析的目的是为了量化和评价算法在处理大量数据时的性能，以便在不同算法之间做出合理选择。通过将算法资源需求表述为输入大小的函数，我们可以更好地理解和预测算法在实际应用中的表现。我们希望比较不同的算法，尤其是那些能够解决任意大规模实例的算法。

标准处理流程 Standard Approach

渐近分析：关注的是随着输入规模增加，成本（如运行时间、内存等）如何增长。

标准（默认）方法包括：

• 考虑成本函数的渐近增长。
• 考虑最坏情况（成本最高）的输入。
• 考虑运行时间成本，即基本操作的数量。

还有其他方法，例如：

• 情况分析：考虑算法在所有可能输入上的平均性能。
• 空间（内存）成本：评估算法在运行过程中所需的内存空间。

这些分析方法提供了不同的视角来评估算法的效率，帮助我们了解在不同情况下算法可能的表现。

基本操作被非正式地定义为一个计算步骤，它在计算过程中占用固定数量的计算周期。 一些基本操作的例子包括：

• 算术运算（如加、减、乘、除）
• 两个值的比较
• 赋值操作，即将一个值赋给一个变量
• 访问数组元素
• 调用一个函数
• 返回一个值
• 打印一个字符

在进行算法分析时，应将操作计数为常数因子，$O(1)$，而不是精确数字。这意味着在分析算法的复杂度时，我们不关心具体执行了多少次基本操作，而是关注基本操作的总体趋势。

例子 Examples

运行时间 vs 执行时间 Running time vs Execution time

• 运行时间是对算法执行时间的一种估计，它基于简化的假设，比如忽略基本操作的具体耗时。
• 在大O记号中通常会隐藏常数因子，这意味着我们关注的是算法性能的增长趋势，而非确切的执行时间。
• 大O记号着重于当输入规模 $n$ 变得非常大时的性能限制。

例如：

一个计算平方的实现，即下文中的 square(n)，随着 $n$ 的增大其运行时间会变长。

一个“解决棋类问题”的程序可能会在 $O(1)$ 时间内运行，这意味着不论棋盘的大小，它的解决时间都被认为是常数。这可能指的是对于一个确定的棋局，如固定的开局或结束局面，程序能够立即给出解决方案。

具体示例

使用最坏情况估计和大O进行问题简化 Simplifying with Worst Case and Big-O

最坏情况估计

在本例中，直接使用 $n$ 替换 $i$。

使用大O简化问题

在本例中，没有固定的循环执行的次数，只知道该次数为在0-n中间，即 $O(n)$，那么直接使用 $O(n)$ 替换：

其他方式

最坏情况假设和大O记号的结合可以简化分析，但这种简化可能会导致非最优的界限。为了得到最好的界限，可能需要进行更细粒度的上界分析，或者分析特定情况以找到匹配的下界（大Omega记号）。

大Omega记号用于分析最坏情况的下界，它不是最佳情况分析。也就是说，当我们说某算法的性能是大Omega记号的某个函数时，我们是在说即使在最坏的输入情况下，算法的性能也至少有这么好。

递归例子 Recursive examples

例子 1

可以假设对于 fact(n) 来说，所需要的时间为 $T(n)$，那么：

例子 2

例子 3

例子 4