面向考试说明复习1
需积分: 0 156 浏览量
2022-08-04
15:31:39
上传
评论
收藏 972KB PDF 举报
算法设计思想
蛮力
一种简单直接地解决问题的方法，直接基于问题的描述和涉及的概念定义
唯一一个能够应用于所有问题的策略
肯定会给出一种对应的解，不受数据规模的限制
可能比设计一个好的算法需要更少的时间
给出一个问题解的时间复杂度上界，衡量其它算法的时间效率
体现蛮力法的一些解决问题的方案
搜索所有解空间
找约束条件、找枚举范围：在搜索前尽可能减小搜索空间
搜索所有路径
直接计算
模拟和仿真
举例：选择排序、冒泡排序、交替放置的碟子
分治
将一个问题划分为同一类型的若干子问题，子问题最好规模相同
对这些子问题求解（一般采用递归方法）
有必要的话，合并这些子问题的解，以得到原始问题的答案
能够使用分治策略的问题一般具有如下特质：
问题规模缩小到一定程度就很容易解决
问题能够划分为多个相互独立的子问题
举例：归并排序、快速排序、螺丝螺母问题、棋盘覆盖、折半查找
主定理
剩余21页未读，继续阅读
评论0