使用 Java 的 DSA - 算法

算法概念

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

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

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

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

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

Ο( f (n)) = { g (n) ：存在 c > 0 且 n ₀使得g (n) ≤ c。f (n) 对于所有 n > n ₀。}

Big Oh 表示法用于简化函数。例如，我们可以将特定的函数方程 7nlogn + n - 1 替换为 Ο( f (nlogn))。考虑如下场景：

7nlogn +n - 1 ≤ 7nlogn + n

7nlogn +n - 1 ≤ 7nlogn + nlogn

当 n ≥ 2 时，logn ≥ 1

7nlogn +n - 1 ≤ 8nlogn

它表明，使用常数 c = 8 和 n _{0 = 2，}f (n) = 7nlogn + n - 1 在O (nlogn)的范围内。

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

例如，对于函数f (n)

Ω( f (n)) ≥ { g (n) ：存在 c > 0 且 n ₀使得g (n) ≤ c。f (n) 对于所有 n > n ₀。}

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

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