算法和函数

算法： 算法是解决问题的逐步方法。

算法的特性

算法通常具有以下特性

1. 输入：算法接收输入。 从外部提供零个或多个量。
2. 输出：算法产生输出。 至少产生一个量。
3. 精确性：步骤被精确地陈述。 每条指令清晰明确。
4. 可行性：必须可以执行每条指令。
5. 灵活性：也应该可以在算法中进行更改，而无需花费太多精力。
6. 通用性：该算法适用于一组输入。
7. 有限性：算法必须在执行有限数量的指令后完成。

算法分析（复杂度）

算法分析是指推导执行算法所需的时间和空间估计的过程。

估计算法所需的时间（例如，步骤数）和空间（例如，变量数）非常重要。 了解算法所需的时间和空间使我们能够比较解决同一问题的算法。 例如，如果一个算法需要 n 步来解决一个问题，而另一个算法需要 n^2 步来解决同一个问题，我们将更喜欢第一个算法。 对执行算法所需的时间和空间进行估算称为算法的时间复杂度和空间复杂度。

      执行算法所需的时间是输入的函数。 我们不直接处理输入，而是使用参数来描述输入的大小。 例如，如果输入是包含 n 个元素的集合，则输入的大小为 n。 由于很难确定算法的准确时间复杂度，因此关于算法的时间复杂度有三种值得注意的情况。

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

渐近记号

渐近表示法用于描述算法的执行时间。 这些表示法显示了函数的增长顺序。 在这里，算法所花费的时间是关于数学函数的映射。 有许多渐近表示法，如 0、θ、Ω、w，每个都具有其重要性。

1. 大 O 符号：函数 f (n) =O (g (n)) [读作 "f of n is big-oh of g of n"] 当且仅当存在正常数 c 和 n₀ 使得

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

示例 1：函数 4n + 3 = O (n) 因为对于所有 n ≥，4n + 3 ⩽ 5n。

示例 2：函数 20n² + 5n + 2 = O (n²) 因为对于所有 n ≥，20n²+ 5n +2⩽21n²。

2. Omega (Ω) 符号：函数 f (n) = Ω (g (n)) [读作 "f of n is omega of g of n"] 当且仅当存在正常数 c 和 n₀ 使得

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

示例 1：函数 4n + 3 = Ω (n) 因为对于所有 n ≥1，4n + 3 ≥ 4n。

示例 2：函数 20n²+ 5n +2 = Ω (n) 因为对于所有 n ≥1，20n²+ 5n +2 ≥ 20n²。

3. Theta (θ)：函数 f (n) = θ (g (n)) [读作 "f is the theta of g of n"] 当且仅当存在正常数 k₁、k₂ 和 k₀ 使得

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

示例 1：函数 4n + 3 = θ (n) 因为对于所有 n ≥ 3，4n + 3 ≥ 4n，并且对于所有 n ≥ 3，4n + 3 ≤ 5n。

示例 2：函数 20n²+ 5n +2 = θ (n²) 因为对于所有 n ≥1，20n²+ 5n +2 ≤ 21n²，并且对于所有 n ≥ 1，20n²+ 5n +2 ≥ 20n²。