算法基本概念

需了解时间复杂度和空间复杂度的计算方法，是后续内容的基础。

什么是算法

算法 (Algorithm) 是一个明确规定了操作步骤的有限指令集，用于计算函数、处理数据、解决一个特定问题或执行某个任务。

算法的基本属性：

明确性：每一步骤必须有明确且不含糊的定义。
有输入和输出：算法应有0个或更多的输入和1个或更多的输出。输入是在算法开始之前提供的，而输出是在算法结束时产生的。
有限性：如果算法在执行完有限步骤后终止，那么它就是有限的。换句话说，一个算法必须总是在执行有限次操作后结束。
可行性：算法中的每一步都应该是简单且基本的，这样它们可以在有限的时间内完成并由计算机执行。
独立性：算法的指令应该有普适性，也就是说，它们不应依赖于任何特定的编程语言或模型。相反，算法应该足够通用，可以在任何编程环境中实现。

效率度量

时间复杂度

时间复杂度（Time Complexity）描述的是执行某个算法所需要的时间如何随着输入数据量的增长而变化。这是一个估计，通常只考虑最高阶的项，并忽略常数因子。常见的时间复杂度（按增长速度排序）有：

$O(1)$：常数时间。无论输入数据有多大，算法都在恒定的时间内完成。
$O(\log n)$：对数时间。例如：二分搜索。
$O(n)$：线性时间。例如：简单的搜索算法。
$O(n \log n)$：线性对数时间。例如：高效的排序算法，如归并排序。
$O(n^2)$、$O(n^3)$ …：多项式时间。例如：冒泡排序、插入排序和选择排序是 (O(n^2)$。
$O(2^n)$：指数时间。例如：计算斐波那契数列的递归实现。
$O(n!)$：阶乘时间。例如：旅行商问题的暴力解决方法。

空间复杂度

空间复杂度（Space Complexity）描述的是执行某个算法所需要的存储空间如何随着输入数据量的增长而变化。与时间复杂度类似，我们只关心增长的速度，并通常只考虑最高阶的项。

例如：

$O(1)$：算法使用恒定的额外空间。
$O(n)$：算法的存储需求与输入数据的大小成线性关系。