"算法复习：基础概念、复杂度计量、分治法、动态规划"

山东科技大学算法复习题总结 一、简答题 1. 什么是算法？什么是程序？ 算法是对问题解题过程的一种描述，它是一个由基本操作构成的、用于解决特定问题的有穷指令序列。 程序是算法在计算机上的具体实现，是一系列指令和规则的有序集合。 2. 算法的特点是什么？ 算法具有以下特点： - 输入：算法有零个或多个输入。 - 输出：算法有一个或多个输出。 - 有穷性：算法在有限的步骤之后会结束。 - 确定性：算法的每一步都有确定的含义。 - 可行性：算法的每一步都是可以实现的，即能够通过执行有限次基本操作实现。 3. 给出算法复杂度计量符号 O 和 ε的定义。 - O符号表示算法的时间复杂度的上界，用于衡量算法的时间开销。 - ε符号表示算法的时间复杂度的下界，用于衡量算法的最低时间开销。 二、算法复杂度计算 已知某算法耗时为 T（n），且满足递归方程 T(n) = T(n/2) + O(n)，计算该算法的时间复杂度 T（n）。 根据递归方程，可以得到 T(n) = O(n log n)。 三、分治法和其算法设计模式 1. 分治法的基本思想是将一个复杂问题分解成多个相同或类似的子问题，分别处理子问题，然后将子问题的结果组合起来得到原问题的解决方案。 2. 分治法的一般算法设计模式（伪代码）： ``` Algorithm DivideAndConquer(问题): if 问题规模较小: 直接求解问题 else: 将问题分解为多个子问题 for 每个子问题: 解决子问题 将子问题的解合并为原问题的解 return 原问题的解 ``` 3. 设 n 个不同的整数排好序后存于 T[0..n-1]中。若存在一个下标 i，0≤i<n, 使得 T[i]=i，设计一个有效算法找到这个下标。要求算法在最坏情况下的计算时间为 O(logn)。 通过分支法，不断以中间位置为界限将问题分为两部分。如果当前位置的值小于当前位置，则问题的解必然在右半部分，反之在左半部分。根据此思路可以得到以下算法： ``` Algorithm FindIndex(T, low, high): if low > high: return -1 mid = (low + high) / 2 if T[mid] == mid: return mid else if T[mid] > mid: return FindIndex(T, low, mid - 1) else: return FindIndex(T, mid + 1, high) ``` 四、动态规划算法 1. 动态规划算法的两个基本要素是状态和状态转移方程。状态是指问题中需要求解的某种特定情况，状态转移方程则描述了状态之间的关系。 2. 动态规划算法解题的基本步骤： - 确定状态：确定需要求解的状态 - 设置初始条件：给定初始状态下的解 - 确定状态转移方程：描述状态之间的关系 - 递归求解或使用迭代方法：根据状态转移方程计算出所有状态的解 - 求解最优解：找出最优解对应的状态和解 3. 0-1背包问题：给定 n 个物品和一个背包。物品 i 的重量为 wi，价值为 vi。背包的最大承载重量为 W，求解将哪些物品放入背包可以使得背包中物品的总价值最大。这是一个经典的动态规划问题。 根据动态规划算法，可以得到以下算法： ``` Algorithm Knapsack(n, W, w, v): for i = 0 to n: dp[i][0] = 0 for j = 0 to W: dp[0][j] = 0 for i = 1 to n: for j = 1 to W: if w[i] > j: dp[i][j] = dp[i-1][j] else: dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i]) return dp[n][W] ``` 以上是对山东科技大学算法复习题的总结。通过对算法和复杂度计算的理解，以及分治法和动态规划算法的具体应用，可以更好地掌握和应用算法知识。