算法基础:分治、递归到动态规划解析

需积分: 10 3 下载量 53 浏览量 更新于2024-07-13 收藏 1.06MB PPT 举报
"计算机常用算法简介-计算机常用算法" 在计算机科学中,算法是解决特定问题的步骤或一组明确指令,是计算机程序的基础。本资源主要介绍了计算机常用的几种算法及其相关概念,包括算法概述、分治策略、动态规划、贪心算法、回溯法和分限界法。 1. **算法概述** - 算法有输入和输出,能够将输入数据转换为所需结果。 - 算法具有确定性,每个步骤都有明确的意义。 - 算法必须在有限步骤内结束,但程序可能无限运行(例如操作系统)。 - 评估算法时,关注其正确性、直观性、容错性、分级性和高效性(时间和空间复杂性)。 - 时间复杂性通过最少次数、最坏次数、平均次数和渐近阶来衡量,常见的有O(1)、O(n)、O(nlog2n)和O(n^2)。 - 算法可以通过自然语言、高级语言、伪代码或N-S图进行描述。 2. **分治与递归** - 分治策略是将大问题分解为小问题,然后分别解决,最后合并结果。例如,排序算法中的快速排序和归并排序。 - 递归算法是直接或间接调用自身以解决问题的方法,如计算阶乘、斐波那契数列等。 3. **动态规划** - 动态规划用于解决具有重叠子问题和最优子结构的问题,通过存储和重用子问题的解来避免重复计算,如背包问题、最长公共子序列等。 4. **贪心算法** - 贪心算法每次选择局部最优解,期望得到全局最优解,适用于没有回溯的优化问题,如霍夫曼编码和Prim最小生成树算法。 5. **回溯法** - 回溯法是一种试探性解决问题的方法,当发现当前路径无法达到目标时,会退回一步尝试其他路径,常用于求解组合优化问题,如八皇后问题、数独求解。 6. **分限界法** - 分限界法是回溯法的一种优化,通常用于求解最优化问题,通过剪枝减少搜索空间,提高效率,如旅行商问题的解决方案。 以上知识点是计算机科学中的基础内容,理解和掌握这些算法对于编程和问题解决至关重要。通过深入学习和实践,可以提升编程能力,解决实际工程中的复杂问题。