第一节课

对于算法的分析是基于一个抽象的机器，分析的算法就不拘泥于某个特定的机器（RAM Model）

对于算法正确性的证明：数学归纳法。保证在输入的数量无穷多的情况，仍然可以保证输出的正确性

算法的性能分析：不能够使用时间这种精确的指标，应该也是采用一种足够抽象的度量工具：操作步的计数
测量条件：最好最坏和平均时间复杂度

第二节课

算法的评价

  1. 对于算法的分析不是计算详细的数据，而是统计关键步骤的数量
  2. 对于算法的分析是基于大的输入规模的
  3. 对于算法的分析只把握主体部分，忽略次要部分

image.png
利用Ω，O，θ来进行分析
对于这三个，本质是一个函数的集合，然后就是判断当前的函数是否属于集合

对于判断是否属于O，使用极限来考虑，通俗就是（不超过）
image.png

对于判断Ω也是利用极限判断（不低于）
image.png

同样的还有θ
image.png

这三个符号有一些关系，传递性，对称性，和性质
image.png

还有小写的符号，前面的O是对于一个f，当n足够大的时候有cg>f，这里的o是对于任意的c都存在n使得cg>f
image.png
同理还有一个
image.png

这里对于θ没有对应的小写，前面的大写的θ可以认为是O和Ω的交集，对于小写的而言，他们没有交集