第一章
第一节：计算
1.1计算
计算机无非是工具和手段，计算才是我们本质的研究目的和目标。
从绳索计算机和尺规计算机的两个例子中看到：计算机无疑只是工具，而就计算 ：就是运用相应的工具，可以重复，机械的（完成问题解决）的过程。
1.2算法
所谓算法，即在特定的计算模型下，旨在解决特定问题的指令序列
具有以下几个特征;
1.输入
2.输出
3.正确性 的确可以解决指定问题
4.确定性 应当可以被描述为一个由基本操作组成的序列
5.可行性 每个操作是可以实现的 （不要犯大象塞冰箱的错误）
6.有穷性 对于任何输入，有穷次基本操作，都可以得到输出
1.3好算法
1.首先，它是正确的
2.可读的：结构化，注释，准确命名
3.最重要的：效率 ----- 速度尽可能的快，占用储存空间尽可能少
第二节 计算模型
2.1 性能测度
算法有有效性和高效性，前提是数据结构和算法的有机结合，统称DSA，而效率，则是区分不同DSA“好坏”，“优劣”的标准。而要定量的分析，则要用到下面的算法分析。
2.2 算法分析
1.前提：正确性
2.核心：成本：时间成本和空间成本，但要分辨两个DSA的成本大小，你必须保证两个计算成本一致，
通常，两个问题的规模一致时，我们的就可以视为两个问题的计算成本一致。
2.3最坏情况
我们在计算一个DSA的成本T(n)时，考虑的是最坏情况下的T(n)的值。
网友评论