达内数据结构与算法.ppt

算法 算法的特性 有穷性 确定性 可行性 输入 输出 算法的要求 正确性 可读性 健壮性 效率与低存储量需求 算法效率的度量 度量算法的两种方法： 事后统计法 事前分析法 时间复杂度 T(n) = O(f(n)) 空间复杂度 S(n) = O(f(n)) 常见算法模型 贪心算法 在求最优解问题的过程中，依据某种贪心标准，从问题的初始状态出发，直接去求每一步的最优解 分治算法 “分而治之”之意，把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。如排序算法(快速排序，归并排序) 回溯算法 溯算法也叫试探法，它是一种系统地搜索问题的解的方法。回溯算法的基本思想是：从一条路往前走，能进则进，不能进则退回来，换一条路再试。 动态规划法 动态规划法是20世纪50年代由贝尔曼（R. Bellman）等人提出,用来解决多阶段决策过程问题的一种最优化方法。所谓多阶段决策过程,就是把研究问题分成若干个相互联系的阶段,由每个阶段都作出决策,从而使整个过程达到最优化 分支限界算法 是一种在问题的解空间树上搜索问题的解的方法。 查找算法 线性查找算法 二分查找算法 排序 冒泡 插入 选择 快速 归并