Dsa Using Java 简明教程

DSA using Java - Algorithms

Algorithm concept

算法是一个按步骤执行的过程，其中定义了一组要以特定顺序执行的指令以获取所需的输出。在数据结构方面，以下是对算法的分类。

  1. Search − 搜索数据结构中某个项的算法。

  2. Sort − 按特定顺序对项进行排序的算法

  3. Insert − 将项插入数据结构中的算法

  4. Update − 更新数据结构中现有项的算法

  5. Delete − 从数据结构中删除现有项的算法

Algorithm analysis

算法分析涉及到数据结构执行时间或各种操作的运行时间。操作的运行时间可定义为：每个操作执行的计算机指令数。由于任何操作的确切运行时间因计算机不同而异，我们通常会分析任何操作的运行时间作为 n 的某个函数，其中 n 为该操作在数据结构中处理的项数。

Asymptotic analysis

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

Asymptotic Notations

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

  1. Ο Notation

  2. Ω Notation

  3. θ Notation

Big Oh Notation, Ο

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

它表明 f(n) = 7nlogn + n - 1 在 O(nlogn) 的输出范围内，常数 c = 8 且 n0 = 2。

Omega Notation, Ω

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

例如，对于一个函数 f(n)

Theta Notation, θ

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