算法导论-Notes

习题答案所在网站

第一章 算法在计算中的作用

数据结构 是一种存储和组织数据的方式，旨在便于访问和修改.

1.2 作为一种技术的算法

时间和空间资源.

第二章 算法基础

2.1 插入排序

其对于少量元素的排序较为有效.

参数: 一个长度为 n 的数组.

用来比较的那个数用一个变量 key 表示. key 相当于是用来保存会被替换掉的那个量.

未排序的元素, 依次在已排序的元素中比较.

已排序好的元素中, 你只要比最后一个大, 那么就比前面的都大, 如果比最后一个小, 就要和前面比较, 如:

1 3 6

是已排序好的部分, 9 是下一个数, 9 比 6 大, 那就肯定比前面的 1 和 3 大. 若 2 是下一个数, 2 比 6 小, 那就需要再和 3 比较.

i+1 可以看作 i 右边的元素来理解.

感觉主要思路就是划分为已排序和未排序的两部分.

将元素右移, 直到找到 key 的合适位置.

2.2 分析算法

分析算法的结果意味着预测算法需要的资源.

当 k 是一个足够小的正整数时, 我们将把 $2^k$ 的计算看成一个常量时间操作.

一般来说, 算法需要的时间与输入的规模同步增长, 所以通常把一个程序的运行时间描述成其输入规模的函数.

输入规模 的最佳概念依赖于研究的问题, 如用输入的项数表示, 用输入图的顶点数和边数表示.

一个算法在特定输入上的 运行时间 是执行的基本操作数或步数. 每一 步 的时间和机器有关.

算法的运行时间是执行每条语句的运行时间之和.

往往只集中于 最坏的运行时间 .