使用C语言的数据结构 - 算法

算法

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

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

• 排序 - 用于按特定顺序排序项目的算法

• 插入 - 用于将项目插入数据结构的算法

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

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

算法分析

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

渐近分析

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

渐近记号

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

• Ο 符号

• Ω 符号

• θ 符号

大O符号，Ο

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

例如，对于函数 f(n)

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

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

欧米茄符号，Ω

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

例如，对于函数 f(n)

西塔符号，θ

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