算法分析算法复习题(中英文).docVIP

（有翻译） The O-notation provides an asymptotic upper bound. The ?-notation provides an asymptotic lower bound. The Θ-notation asymptotically a function form above and below. O型符号提供一个渐近的上限。Θ符号提供一个渐近下界。?Θ-符号渐近函数形式的上方和下方。 To represent a heap as an array，the root of tree is A[1], and given the index i of a node, the indices of its parent Parent(i) { return ?i/2?; }，left child, Left(i) { return 2*i; }，right child, right(i) { return 2*i + 1; }. 代表一个堆中的一个数组，树的根节点是A[1]，并且给出一个节点i，那么该节点的父节点是 左孩子 右孩子 Because the heap of n elements is a binary tree, the height of any node is at most Q(lg n). 因为n个元素的堆是一个二叉树，任意节点的树高最多是 In optimization problems , there can be many possible solutions. Each solution has a value, and we wish to find a solution with the optimal (minimum or maximum) value. We call such a solution an optimal solution to the problem. 在 最优化问题 中，有很多可能的解，每个解都有一个值，我们希望找到一个最优解（最大或最小），我们称这个解为最优解问题。 optimal substructure if an optimal solution to the problem contains within it optimal solutions to subproblems. 最优子结构 中问题的最优解，至少包含它的最优解的子问题。 A subsequence of X if there exists a strictly increasing sequence i1,i2, ..., ik of indices of X such that for all j = 1, 2, ..., k, we have xij = zj . Let X = x1, x2, ..., xm and Y = y1, y2, ..., yn be sequences, and let Z = z1, z2, ..., zk be any LCS of X and Y. (1). If xm = yn, then zk = xm = yn and Zk-1 is an LCS of Xm-1 and Yn-1. (2). If xm ≠ yn, then zk ≠ xm implies that Z is an LCS of Xm-1 and Y. (3). If xm ≠ yn, then zk ≠ yn implies that Z is an LCS of X and Yn-1. A greedy algorithm always makes the choice that looks best at the moment. That is, it makes a locally optimal choice in the hope that this choice will lead to a globally optimal solution. 贪心算法 经常需要在某个时刻寻找最好的选择。正因如此，它在当下找到希望中的最优选择，以便引导出一个全局的最优解。 The greedy-choice property and optimal sub-structure are the two key ingredients of greedy algorithm. 贪心选择 和最优子结构是贪心算法的两个重要组成部分。 When a recursive algorithm revisits the same problem over and