使用 C 的 DSA - 算法

算法

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

• 搜索 − 用于在数据结构中搜索项目的算法。

• 排序 − 用于按特定顺序对项目进行排序的算法

• 插入 − 用于在数据结构中插入项目的算法

• 更新 − 用于更新数据结构中现有项目的算法

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

算法分析

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

渐近分析

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

渐近符号

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

• Ο 符号

• Ω 符号

• θ 符号

大 O 符号，Ο

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

例如，对于函数 f(n)

Big Oh 符号用于简化函数。例如，我们可以用 Ο(f(nlogn)) 替换特定函数方程 7nlogn + n - 1。考虑以下场景 −

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

Omega 符号，Ω

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

例如，对于函数 f(n)

Theta 符号，θ

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