算法基础——基础知识

1、特性

• 输入、输出 —— >=0个输入，>=1个输出
• 有穷性 —— 有限步骤、有限时间内完成
• 确定性 —— 每一步都有确定的含义
• 可行性 —— 每一步都能通过执行有限次数完成

2、设计要求

• 正确性
• 可读性
• 健壮性
• 时间效率高、存储量低

3、度量方法

• 事后统计法（不科学、不准确）
• 事前分析估算

4、时间复杂度

• 常数阶 —— O(1)
• 线性阶 —— O(n)
• 对数阶 —— O(log n)
• 平方阶 —— O(n^2)

常见时间复杂度

常见时间复杂度消耗的时间从小到大：

5、空间复杂度

计算公式：S(n) = O(f(n))
其中n为问题规模，f(n)为语句关于n所占存储空间的函数。