简介与渐近分析

简介

数据结构与算法是计算问题求解的基础。要设计高效的计算机程序，必须选择合适的数据结构，并据此设计相应的算法。

算法

算法 是一组有限且无歧义的步骤或指令，用于解决特定问题。掌握算法知识有助于我们在合适的情境下应用恰当的算法，从而更快地获得期望结果。随着经验积累，解决新问题会变得更加容易。通过学习各种问题求解的算法或技术，我们逐渐形成一种思维模式，这将帮助我们应对类似的问题。

算法具有以下特性：

1. 可以接受零个或多个输入。
2. 至少产生一个输出。
3. 必须是确定性的：对于相同的输入，总是产生相同的输出。
4. 必须是正确的：能够正确处理所有给定的输入，并给出正确的输出。
5. 必须在有限时间内终止。
6. 必须是高效的：在解决问题时应具备较快的速度和良好的优化性。

算法的 复杂度 是指算法处理输入并生成输出所需的时间或空间资源。

复杂度分为两种类型：

• 时间复杂度：算法对规模为 'n' 的输入生成输出所需的时间。用函数 T(n) 表示，即输入规模为 n 时所需的时间。
  时间复杂度越低，算法效率越高。

• 空间复杂度：算法对规模为 'n' 的输入生成输出所消耗的内存空间。用函数 S(n) 表示，即输入规模为 n 时所使用的内存大小。

渐近分析或渐近符号

渐近分析（或渐近符号）用于在不依赖具体数据集的情况下比较算法的效率。我们通常关注的是算法运行时间的增长趋势，而非其精确的执行时间。这种时间也称为渐近运行时间。