数据结构与算法——算法效率与度量

算法的时间和空间性能非常重要

一、算法的渐近分析

当 n 增大到一定值后，其他的常数项和低幂次项都可以忽略，只需确定是在什么量级（线性、n 方、指数级等）

1. 大 $\mathcal{O}$ 表式法

函数增长率上限

2. 大 $\Omega$ 表式法

函数增值率的下限

3. 大 $\Theta$ 表示法

当上、下限相同时则可用 $\Theta$ 表示法

二、增长率曲线

三、数据结构和算法的选择

• 仔细分析所要解决的问题
  • 特别是求解问题所涉及的数据类型和数据间逻辑关系（问题抽象、数据抽象）
  • 数据结构的初步设计往往先于算法设计
• 注意数据结构的可扩展性
  • 考虑当输入数据的规模发生改变时，数据结构是否能够适应求解问题的演变和扩展

三、思考题

1. 数据结构的三个要素任何一个发生改变，都是不同的数据结构，请举例讨论

   • 双向链表和二叉树的存储结构其实是一样的，他们的不同在于逻辑结构。
   • 数组和向量都是线性表，其存储形式不同，成为不同的数据结构。

2. 算法设计目标是什么？

   • 时间和空间的权衡
   • 易读
   • 易编码
   • 易调试
   • 易维护
   • 易扩展

3. 算法选择的过程？

4. 要求在时间复杂度 $\mathcal{O}(n)$、空间复杂度 $\mathcal{O}(1)$，使数组元素循环向右移动 K 位