我从未看懂过的第二章

算法导论

2.2分析算法

什么是分析算法->分析算法用到的ziyuan
包括了内存，交流，带宽，硬件
重要的是计算时间（？）

RAM

一条指令执行完再执行下一条指令，不可能有两条指令同时发生。
不要滥用RAM比如说：一条指令完成排序，不存在的。
那么包括了什么呢？
1.计算：+、-、×、%、取下界、取上界
2.数据移动：载入、存储、复制
3.控制：条件和非条件的分支，子循环的开始和返回。
这些都占用了固定总量的时间。
RAM的数据类型：整数和浮点数（用来存实数）
该模型牺牲了精度。
假设限制了每一个定义变量的大小，固定的c>=1,被表示为c lg n的bit长（所以是为什么呢......）
c>=1所以word可以保持n值，我们可以去标记单独的输入元素，限制c的大小不变，word的长度不会任意增长
我们可以把求幂当做固定时间，比如2^k可以用位移来表示。
同时不模拟真实的内存等级制度，缓存？不存在的（他也说有些地方模拟了）
进行这些分析需要很多数学技能

分析插入排序

1.输入了几个数
2.这些数的混乱程度怎样
输入依赖于要解决的问题
比如说排序和离散傅里叶变化，都是自然地看有多少个输入
而相乘两个整数，最好的办法是输入二进制的bit（wait......）
输入图表，可以描述为每一列数字（edge？）

running time

原始的操作数或步骤执行固定总量的时间。
第i行的执行时间是c_i，然后再看执行了多少次这条语句
如果里面还有子程序（循环？），会更加复杂
出现while的嵌套，在第i行的时间还是c_i，次数设为t_j次（就是当那个计数值是多少时......），然后把时间和次数乘起来，得到结果。
这个结果很复杂，我们需要化简。假设输入的是一个排好序的序列，就会用最少的时间，很多东西可以消掉，最后得到n。