[算法学习笔记]算法基础知识
算法基础知识
算法的五大要素
- 有穷性：算法必须能够在有限个步骤内完成。
- 确定性：算法的每一步必须有确定的定义。
- 输入
- 输出
- 可行性：算法的每个步骤都必须能分解为基本的可执行操作，每个步骤都必须能在有限时间内完成
循环不变式
循环中的循环不变式可以帮助我们理解算法的正确性。为了证明算法的正确，必须证明循环不变式的三个性质：
1. 初始化：循环不变式在循环开始之前是正确的。
2. 保持：循环不变式在循环的每一次迭代开始之前是正确的。
3. 终止：在循环结束时，不变式会给出一个可以对判断算法是否正确有帮助的性质。
插入排序分析
下面是插入排序的一个简单的c++实现
void insert_sort(std::vector<int>& vec) {
for (int i = 1; i < vec.size(); i++) {
int key = vec[i];
//将vec[i]插入到已经排好序的vec[0...i-1]中
int j = i;
while(j > 0) {
if(key >= vec[j - 1])break;
vec[j] = vec[j - 1];
--j;
}
vec[j] = key;
}
}这里有两个循环不变式，一个是外层循环的 i < vec.size()，我们可以来证明循环不变式的三个性质：
1. 初始化 ：在第一次迭代开始之前，i = 1，由于vec不少于1个元素（不然就不用排序了），显然成立。
2. 保持：在循环结束之前，i显然也是小于vec.size()的。
3. 终止：当将所有的元素排好序之后，i = vec.size() - 1，进行i++之后，循环终止，表明已经排好序了。
第二个循环则是内层的while循环。我们同样可以证明循环不变式的三个性质：
1. 初始化：在刚开始的时候，i = j = 1，所以，j > 0 显然成立，如果key < vec[j-1]，则进入循环。不变式j > 0 && key < vec[j-1]成立。
2. 保持：在找到key应该插入的位置之前，如果未到vec首位(j = 0)的话，则key < vec[j-1]必须成立。
3. 终止：循环结束之后，循环不变式不再成立，j指向的正好是key应该插入的位置。
结合看两个循环，则可以看出整个算法是正确的。
郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
