ChapterⅠ 算法在计算中的作用
1.NP完全问题是没有有效的解法
2.解决同一问题的各种不同算法的效率相差很大，这种影响往往比硬件和软件方面的差距影响还要大
Chapter Ⅱ 算法入门
1.插入排序
算法思路：类似对纸牌的整理（从左到右，一个一个过去，将下一个放到正确的位置）
算法实现（c++）：
for(int j=1; i<n; i++)
{
int key =A[j];
int i=j-1;
while(i>0 && A[i]>key)
{
A[i+1]=a[i];
i=i-1;
}
A[i+1]=key;
}
算法分析：就是对一个算法所需要的资源进行预测。
2.循环不变式帮助证明算法的正确性（3个性质）
初始化：在循环的第一次迭代开始之前是正确的
保持：某次迭代是正确的，那么下一次迭代开始之前也应该是正确的
**终止: ** When the loop terminates, the invariant gives us a useful property that helps show that the algorithm is correct.
网友评论