Java 数据结构与算法

---

---

算法概念

算法是一步一步的过程，它定义了一组指令，这些指令以一定的顺序执行以获得所需的输出。在数据结构方面，算法的类别如下。

• 搜索 - 在数据结构中搜索项目的算法。

• 排序 - 以特定顺序对项目进行排序的算法

• 插入 - 在数据结构中插入项目的算法

• 更新 - 更新数据结构中现有项目的算法

• 删除 - 从数据结构中删除现有项目的算法

算法分析

算法分析处理数据结构各种操作的执行时间或运行时间。操作的运行时间可以定义为每个操作执行的计算机指令的数量。由于任何操作的确切运行时间因计算机而异，因此我们通常将任何操作的运行时间分析为 n 的某个函数，其中 n 是数据结构中该操作处理的项目数量。

渐进分析

渐进分析是指用数学计算单位来计算任何操作的运行时间。例如，一个操作的运行时间计算为f(n)，另一个操作的运行时间计算为g(n²)。这意味着第一个操作的运行时间将随着 n 的增加而线性增加，而第二个操作的运行时间将随着 n 的增加而呈指数增加。同样，如果 n 非常小，则两个操作的运行时间几乎相同。

渐进符号

以下是计算算法运行时间复杂度时常用的渐进符号。

• Ο 符号

• Ω 符号

• θ 符号

大O符号，Ο

Ο(n) 是表示算法运行时间上界的正式方法。它衡量最坏情况下的时间复杂度或算法可能完成所需的最长时间。例如，对于函数f(n)

Ο(f(n)) = { g(n) : 存在 c > 0 和 n₀ 使得对于所有 n > n₀，g(n) ≤ c.f(n)。}

大O符号用于简化函数。例如，我们可以用Ο(f(nlogn))替换特定的函数方程 7nlogn + n - 1。考虑以下情况

7nlogn +n - 1 ≤ 7nlogn + n

7nlogn +n - 1 ≤ 7nlogn + nlogn

对于 n ≥ 2 使得 logn ≥ 1

7nlogn +n - 1 ≤ 8nlogn

它表明f(n) = 7nlogn + n - 1 在O(nlogn) 输出范围内，使用常数 c = 8 和 n₀ = 2。

欧米茄符号，Ω

Ω(n) 是表示算法运行时间下界的正式方法。它衡量最佳情况下的时间复杂度或算法可能完成所需的最短时间。

例如，对于函数f(n)

Ω(f(n)) ≥ { g(n) : 存在 c > 0 和 n₀ 使得对于所有 n > n₀，g(n) ≤ c.f(n)。}

西塔符号，θ

θ(n) 是表示算法运行时间上下界的正式方法。它表示如下。

θ(f(n)) = { g(n) 当且仅当g(n) = Ο(f(n)) 和g(n) = Ω(f(n)) 对于所有 n > n₀。}