《算法导论》笔记一

看《Introduction to Algorithms, Second Editon》，里面提到插入排序和选择排序，这两个算法的时间复杂度是一样的。比较这两个算法的时候，我发现其实它俩是一回事。插入排序是把新元素插入到已经排好了序的序列里，我们知道执行当前操作需要插入的数字；而在选择排序中，需要插入的新元素是未知的（需要选取），但是插入的位置是已知的。插入排序是插入的元素已知，选择排序是插入的位置已知，插入排序插入新元素的过程与选择排序选择元素的过程相同。

书中描述算法的时候，元素都是放在数组中的，所以插入排序的时间复杂度为n的2次方，其中大部分时间用在了移动数组原素上。如果我们用链表而不是数组来存储数据，花在移动数据上的时间省掉了，时间复杂度是不是变为n了？难道这就是传说中的以空间换时间？

书里提到的loop invariants证明方法对理清思路很有帮助，divide-and-conquer的方法来解决问题也很有启发，不过我目前还不能说完全掌握了它们。另外，在计算复杂度时，数学知识就派上用场了，而以前，我对数学有相当的排斥，原因是觉得背数学公式没有用。现在看来，数学还是有她用处的（这简直是废话），所以要好好学习并使用她。