算法与函数

本文概述

• 算法分析（复杂度）
• 渐近符号

算法：算法是解决某些问题的分步方法。

算法特点：

算法通常具有以下特征：

1. 输入：算法接收输入。零数量或更多数量从外部供应。
2. 输出：该算法产生输出。至少产生一个数量。
3. 精度：步骤已明确说明。每条指令都清晰明确。
4. 可行性：执行每条指令必须可行。
5. 灵活性：还可以在不花太多精力的情况下对算法进行更改。
6. 通用性：该算法适用于一组输入。
7. 有限性：必须在执行了有限数量的指令后才能完成算法。

算法分析（复杂度）

算法分析指的是对执行算法所需的时间和空间进行估算的过程。

重要的是估计算法所需的时间（例如, 步数）和空间（例如, 变量数）。了解算法所需的时间和空间后, 我们就可以比较解决相同问题的算法。例如, 如果一种算法需要n个步骤来解决一个问题, 而另一种算法需要n ^ 2个步骤来解决一个相同的问题, 我们将更喜欢第一种算法。执行算法所需的时间和空间的这种估计称为算法的时间和空间复杂度。

执行算法所需的时间取决于输入。使用参数来表征输入的大小, 而不是直接处理输入。例如如果输入是包含n个元素的集合, 则输入n的大小。由于确定了困难任务中算法的确切时间复杂度, 因此有三种情况需要注意算法的时间复杂度。

• 最坏情况：f（n）表示在大小为n的任何实例上采取的最大步数。
• 最佳情况：f（n）表示在大小为n的任何实例上执行的最小步骤数。
• 平均情况：f（n）表示在大小为n的任何实例上采取的平均步骤数。

渐近符号

渐进符号用于描述算法的执行时间。符号表示功能的增长顺序。在此, 算法所花费的时间与数学函数有关。有许多渐近符号, 如0, θ, Ω, w都有其重要性。

1.大数表示法：函数f（n）= O（g（n））[读作“ n的f是n的g的大数”]]当且仅当存在正常数c和n0使得

f (n) ⩽ C x g (n) for all n, n ≥ n0

例1：对于所有n≥, 函数4n + 3 = O（n）为4n + 3⩽5n。

示例2：对于所有n≥, 函数20n2 + 5n + 2 = O（n2）为20n2 + 5n +2⩽21n2。

2. Omega（Ω）表示法：函数f（n）=Ω（g（n））[读作“ n的f是n的g的欧米茄””, 当且仅当存在正常数c和n0使得

f (n) ≥ C* g (n) for all n, n ≥ n0

示例1：对于所有n≥1, 函数4n + 3 =Ω（n）为4n + 3≥4n。

示例2：对于所有n≥1, 函数20n2 + 5n +2 =Ω（n）为20n2 + 5n +2≥20n2。

3. Theta（θ）：函数f（n）=θ（g（n））[读作“ f是n的g的θ”], 当且仅当存在正常数k1, k2和k0使得

k1* g (n) ≤ f (n)≤k2* g(n)for all n, n≥n0

示例1：对于所有n≥3的函数4n + 3≥4n, 函数4n + 3 =θ（n）, 对于所有n≥3的函数4n + 3≤5n

示例2：对于所有n≥1的函数20n2 + 5n +2 =θ（n2）为20n2 + 5n +2≤21n2, 对于所有n≥1的函数20n2 + 5n +2≥20n2