1.2 算法的基本概念（书本定义，看下就好）

[!info] 基础概念 相关提炼内容见 algorithm-complexity。

重要特性

• 有穷性：步骤有穷，执行时间有穷
• 确定性：没有二义性
• 可行性：算法是可执行的
• 输入：有零个或多个输入
• 输出：有一个或多个输出

目标

• 正确性 Correctness
• 可读性 Readability
• 健壮性 Robustness
• 高效性 Efficiency

算法效率的度量 🤩

时间复杂度 Time Complex

• 定义：$T(n) = O(f(n))$

空间复杂度 Space Complexity

• 定义 $S(n) = O(g(n))$

示例：如何实现数组逆序？ 方案一：空间复杂度为 1 的情况，即$S(n) = O(1)$

for(i = 0; i < n / 2；i++) // 遍历半个数组
{
	t = a[i];              // 临时变量t
	a[i] = a[n-i-1];       // 交换数值
	a[n-i-1] = t;
}

方案二：空间复杂度为 n 的情况，即$S(n) = O(n)$

for(i = 0; i < n； i++)  // 辅助数组b逆序存储a
	b[i] = a[n-i-1];
for(i = 0; i < n, i++)   // 重新赋值给a
	a[i] = b[i];

思考：斐波那契数列，用递归算法和非递归算法的时间复杂度如何？😜

• 递归算法$O(2^n)$
• 非递归算法$O(n)$

参考资料

• Time Complex #todo
• Space Complexity #todo