中国网站为什么要备案,打开网页出现网站建设中,建设厅证书查询网站,福建省建设环卫协会网站算法策略和算法的区别
算法策略是面向问题的#xff0c;算法是面向实现的。二者又不可分割#xff0c;通过算法策略找到解决问题的算法#xff0c;而不同算法求解的问题算法策略是不一样。
算法的正确性分析
一个算法是正确的#xff0c;如果它对于每一个输入都是最终停…算法策略和算法的区别
算法策略是面向问题的算法是面向实现的。二者又不可分割通过算法策略找到解决问题的算法而不同算法求解的问题算法策略是不一样。
算法的正确性分析
一个算法是正确的如果它对于每一个输入都是最终停止而且产生正确的输出。 一个错误的算法包括在某一个输入上不停止或者对所有输入都停止但是对某一个输入产生不正确的结果。 算法正确性的证明 证明算法对所有的输入都停止证明对每个输入都能产生正确的结果。
算法的复杂性分析
目的预测算法对不同输入所需要的资源量 复杂性测度时间空间/O 等是输入大小的函数 用途为求解一个问题选择最佳算法、最佳设备 涉及到的数学学科离散数学组合数学概率论代数
算法复杂度的度量
时间复杂度一个算法特定输入的时间复杂性是指该算法对输入产生结果需要的原子操作或者步数 空间复杂度一个算法特定输入的空间复杂性是指该算法对该输入结果产生结果所需要的存储空间大小一般指内存 最坏复杂性比如插入排序逆序数组 最优复杂性比如插入排序有序数组 平均复杂性比如插入排序随机数组 比如一段代码 sum0; //执行1次 for(i1;in;i) //执行n次 for(j1;jn;j) //执行n2次 sum; //执行n2次 本程序段的T(n)2n2 n1时间复杂度应取指数级别最高的所以为O(n2)。
计算复杂性函数的阶
增长的阶如果描述算法的效率阶描述的是增长率忽略低阶项和常系数 常用的阶 O(1), O(N),O(N平方,O(lnN)
5大算法策略
算法策略的中心思想是用算法的基本工具循环机制或者递归机制实现算法
分治法
该问题的规模缩小到一定的程度就可以容易地解决 该问题可以分解为若干个规模较小的相同问题即该问题具有最优子结构性质 利用该问题分解出的子问题的解可以合并为该问题的解 应用场景 求解斐波那契数列 递归与HANOI塔问题 二分法求方程近似解 合并排序 求最大值和最小值的分治算法 快速排序 线性时间选择 最接近点对问题 循环赛日程表 大整数乘法 棋盘覆盖
最优化原理
问题中的状态必须满足最优化原理 问题中的状态必须满足无后效性。 所谓的无后效性是指“下一时刻的状态只与当前状态有关而和当前状态之前的状态无关当前的状态是对以往决策的总结”。 动态规划法的应用 最长公共子序列(LCS) 最长递增子序列(LIS) 背包问题 用动态规划实现导弹拦截 最大化投资回报问题的实现 矩阵连乘 走金字塔 凸多边形最优三角剖分 双调欧几里得旅行商问题
贪心算法
在对问题求解时总是做出在当前看来是最好的选择.一般来说贪心算法的证明围绕着整个问题的最优解一定由在贪心策略中存在的子问题的最优解得来的。 贪心算法应用 最小生成树之Prim算法 最小生成树之kruskal算法 Dijkstra算法求解最短路径) Huffman编码 再论背包问题 钱币找零问题 活动选择问题 小船过河问题 区间覆盖问题 销售比赛
回溯法
回溯法是一种选优搜索法按选优条件向前搜索以达到目标。但当探索到某一步时发现原先选择并不优或达不到目标就退回一步重新选择这种走不通就退回再走的技术为回溯法而满足回溯条件的某个状态的点称为“回溯点”.以深度优先方式搜索解空间并在搜索过程中用剪枝函数避免无效搜索。 数的划分 运动员最佳配对问题 解决汽车加油次数最少问题 找出n个自然数中取r个数的全排列 八皇后问题 图的着色问题 装载问题 批处理作业调度问题 再再论背包问题 最大团问题 连续邮资问题 符号三角形问题
分支限界法
分支限界法常以广度优先或以最小耗费最大效益优先的方式搜索问题的解空间树。 常见的两种分支限界法 队列式(FIFO)分支限界法 按照队列先进先出FIFO原则选取下一个节点为扩展节点。 优先队列式分支限界法 按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点。 应用场景 分支限界法之装载问题 分支限界法之布线问题 分支限界法之0 1背包问题 分支限界法之旅行售货员问题
