算法的选择与应用
非数值算法1查找算法
???算法?????????? 复杂度???????????????????????????? 说明?
顺序查找??? 成功时(n+1)/2;失败时n+1?? 无
折半查找???? log2(n+1)??????????????????????? 适用排序后的内容
分块查找????无?????????????????????????????????????典型如文件系统
哈希查找????无???????????????????????????????????? 利用hash方法定位
?
?
2排序算法??
方法??????????????????????? 备注
插入排序???????????????? 顺序读取，对结果排序
选择排序???????????????? 选择读取，顺序排放结果
冒泡排序???????????????? 多趟，顺序读取，前后两两交换
快速排序???????????????? 多趟，分块交换
希尔排序???????????????? 多趟插入，每次插入利用前一次的结果
堆排序??????????????????? 多趟选择，每次选择一个最大值和一个最小值
归并排序???????????????? 多路排序
外排序??????????????????? 超出内存，利用磁盘的排序
数值算法?方法????????????? 备注
误差分析??????? 确定观测误差、截断误差等
穷举法?????????? 逐一枚举和检验
迭代法?????????? 通过重复执行一系列步骤，接近最终结果
递推法?????????? 利用递推关系式和初值，来求解想要的目标值
递归法?????????? 递归嵌套，如递归函数
分治法*?????????? 分解后的子问题彼此都是独立的
回朔法?????????? 深度优先搜索，遇到合适的结果结束
贪心法*????????? 利用自己已做出的选择，而不依赖于待选择的问题
动态规划法*???? 把分解后的子问题归纳为一些相似的子问题。而避免对所有子问题求解
随机模拟??????? 即构造试验模型，进行仿真
?
注，上述分治法、贪心法和动态规划法都是采用分解问题成子问题，再对子问题进行求解。
?
?