算法介绍
麻省理工算法导论学习笔记（1）----算法介绍
我决定啃几个大块头，今天开始跟着公开课学习，一是巩固自己对算法理解，二是可以分享学习心得。
普林斯顿大学的算法课好像也讲完了，只有讲义，好像还没视频，下面我先学麻省理工的算法导论课。
我是一个懒孩子，希望大家监督我。没有监督，俺继续不下去，呃哈哈 。谢谢。
为什么学习算法？
（1）什么比性能更重要？正确性，简洁，可维护性，成本开销，功能性，模块化，安全，可扩展性，用户体验等。
（2）如果算法和性能不重要，为啥关注呢？为什么学习？性能与体验关联，实时性，性能是其他的基础，性能就像货币，你用java来代替c，损失三倍性能，为的是其他方面的优越性，比如对象化，exception机制等。
排序问题
（1）插入排序（Insert Sort）
插入排序分析：
运行时间依赖于输入，比如输入的个数，输入的排序情况。移动、比较的次数可作为衡量时间复杂性的标准。
最大时间（最坏情况，是一个承诺，一个保证）：输入逆序。
平均时间（时间的期望值）：n+假设的输入分布，比如均匀分布。
最少时间（最好情况）：输入正序。
插入排序快不快？当n很小的时候，挺快，当n很大，就会很慢，通常n<=8。
（2）归并排序（Merge Sort）
将两个已经排序的序列合并成一个序列的操作。归并排序算法依赖归并操作。
归并排序分析：
在实际中，当n>30的时候，归并排序将打败插入排序。
比较操作 的次数介于 和 。
赋值操作 的次数是 。
分类: 算法研究
作者： Leo_wl
出处： http://www.cnblogs.com/Leo_wl/
本文版权归作者和博客园共有，欢迎转载，但未经作者同意必须保留此段声明，且在文章页面明显位置给出原文连接，否则保留追究法律责任的权利。
版权信息