红魔馆

Introduction and Background

The Master Theorem is a powerful tool in the field of computer science, specifically in the analysis of algorithms. It is used to determine the time complexity of recursive algorithms, particularly those which follow a ‘divide and conquer’ approach¹².

主定理是计算机科学领域中的一个强大工具，特别是在算法分析中。它被用来确定递归算法的时间复杂度，尤其是那些遵循”分而治之”方法的算法¹²。

In divide and conquer algorithms, a problem is broken down into several smaller subproblems of the same type. These smaller problems are then solved independently and the solutions are combined to solve the original problem. Recursion is a common principle in such algorithms. Typical examples of divide and conquer algorithms include the binary search, merge sort, and quick sort algorithms³.

在分而治之的算法中，一个问题被分解成几个类型相同的较小的子问题。这些较小的问题随后被独立解决，并结合这些解决方案来解决原始问题。递归算法大都采用这种原则。分而治之算法的典型例子包括二分查找，归并排序，和快速排序算法³。

The Master Theorem provides a systematic method to calculate the time complexity of such divide and conquer algorithms. It can immediately give the time complexity in terms of Big O notation, thus providing a simple way to predict the efficiency of the algorithm³⁴.

主定理为计算此类分而治之算法的时间复杂度提供了一种系统性的方法。它可以直接以大O符号表示时间复杂度，提供了一种简单的方式来预测算法的效率³⁴。

The theorem was first presented in the textbook “Introduction to Algorithms” by Cormen, Leiserson, Rivest, and Stein¹. Since then, it has remained an integral part of the study of algorithms due to its practical use in analyzing the time complexity of recursive functions²³⁴.

这个定理首次在Cormen，Leiserson，Rivest和Stein的教科书 “算法导论” 中提出¹。自那时起，由于它在分析递归函数的时间复杂度的实际应用，主定理一直是算法研究的重要组成部分²³⁴。

Methodology and Results

Divide and conquer algorithm (分治算法)

Divide and conquer algorithm is a problem-solving method that decomposes a problem into several smaller, structurally similar subproblems, solves these subproblems recursively, and then merges their solutions to obtain the solution to the original problem.

分治算法是一种问题解决方法，它将问题分解成若干个规模较小、结构相似的子问题，并递归地解决这些子问题，然后将它们的解合并起来得到原问题的解。

How to set up recursive relations (如何设置递归关系式)

The overall idea for solving the problem is to establish a recurrence relation. Through the recurrence relation, the problem can be decomposed into smaller subproblems, and the solution to the original problem can be ultimately obtained.

解决问题的整体思路是建立一个递归关系式。通过递归关系式，可以将问题分解成规模更小的子问题，并最终求解原始问题。

Recurrence relations are usually represented in mathematical form, where T(n) represents the time taken to process an input of size n.

递归关系式通常以数学形式表示，其中 T(n) 表示处理大小为 n 的输入所花费的时间。

• Base Case: When the problem size is a small constant, the processing time is usually constant, represented as Θ(1). This is the basic termination condition for recursion.

  • 基本情况（Base Case）：当问题规模为某个较小的常数时，处理时间通常为常数时间，表示为 Θ(1)。这是递归的基本结束条件。

• Recursive Case: When the problem size exceeds the base case, the recurrence relation consists of two parts:

  • aT(n/b): Represents the time taken to process a total of a subproblems of size n/b recursively.
  • fdiv(n): Represents the time taken for the divide step, i.e., decomposing the problem into subproblems.
  • fcomb(n): Represents the time taken for the combine step, i.e., merging the solutions of subproblems.

    • 递归情况（Recursive Case）：当问题规模超过基本情况时，递归关系式会包含两个部分：
      • aT(n/b)：表示将原问题分解成 a 个规模为 n/b 的子问题，并递归地处理每个子问题，总共消耗的时间。
      • fdiv(n)：表示分解步骤的时间，即将问题分解成子问题的过程。
      • fcomb(n)：表示合并步骤的时间，即将子问题的解合并成原始问题的解的过程。

• Meanings of Parameters:

  • In aT(n/b), a represents the number of subproblems after decomposition, and T(n/b) represents the time taken to process a single subproblem.
  • fdiv(n) represents the time taken for the divide step, usually related to the problem size n.
  • fcomb(n) represents the time taken for the combine step, also usually related to the problem size n.

    • 各项含义
      • aT(n/b) 中，a 表示分解后的子问题个数，T(n/b) 表示处理单个子问题的时间。
      • fdiv(n) 表示分解步骤的时间，通常与问题的规模 n 有关。
      • fcomb(n) 表示合并步骤的时间，也通常与问题的规模 n 有关。

• Recurrence Relation:

  • The entire recurrence relation describes the process of decomposition, processing, and merging of the problem, as well as the time consumed by each step.

    • 递归关系式
      • 整个递归关系式描述了问题的分解、处理和合并过程，以及每个步骤所消耗的时间。

The divide and conquer algorithm and recursive relations (分治算法和递归关系式的关系)

The relationship between the divide and conquer algorithm and recursive relations is closely intertwined. The divide and conquer algorithm is a method of breaking down a problem into smaller subproblems and recursively solving them. In the divide and conquer algorithm, the original problem is decomposed into multiple subproblems, and then the final solution is obtained by recursively solving these subproblems.

分治算法和递归关系式之间有密切的关系。分治算法是一种将问题分解成更小的子问题并递归地解决它们的方法。在分治算法中，原始问题被分解成多个子问题，然后通过递归地解决这些子问题来获得最终的解决方案。

Recursive relations describe the relationship between the size of the problem and its solution. In the divide and conquer algorithm, recursive relations are used to represent the process of decomposing the problem into subproblems and to calculate the time and resources required to solve these subproblems. Recursive relations are typically expressed in recursive form, where the size of the problem is a function of the size of the problem itself.

递归关系式描述了问题的规模与其解决方案之间的关系。在分治算法中，递归关系式用于表示将问题分解为子问题的过程，并计算解决这些子问题所需的时间和资源。递归关系式通常采用递归形式，其中问题的规模被表示为问题本身规模的函数。

By solving recursive relations, we can determine the time and space complexity of the divide and conquer algorithm. Through analyzing recursive relations, we can understand how the size of the problem decreases with each recursion and determine the time and space consumption of each recursive step. This helps us evaluate the efficiency of the algorithm and provides guidance for solving the problem.

通过解决递归关系式，我们可以确定分治算法的时间复杂度和空间复杂度。通过分析递归关系式，我们可以了解问题的规模如何随着递归的进行而减小，并确定每个递归步骤的时间和空间消耗。这有助于我们评估算法的效率，并为问题的解决提供指导。

Therefore, the relationship between the divide and conquer algorithm and recursive relations is that the divide and conquer algorithm solves the original problem by recursively solving subproblems, and recursive relations are used to describe the relationship between the size of the problem and its solution.

因此，分治算法和递归关系式之间的关系是，分治算法通过递归地解决子问题来解决原始问题，并且递归关系式用于描述问题规模与解决方案之间的关系。

Expansion Method (扩展法, 解决递归关系式的标准方法)

Expansion method is a commonly used approach for solving recursive relations. It decomposes the problem into smaller subproblems by expanding the recursive relations multiple times, and gradually obtains the solution to the original problem.

扩展法是解决递归关系式的一种常用方法。它通过多次扩展递归关系式，将问题分解成更小的子问题，并逐步求解得到原问题的解。

• Step 1: Expansion of Recursive Relations
  Firstly, expand the recursive relations to obtain the solution for each subproblem, and express them in the form of recursive expressions.

  • 第一步：展开递归关系式（Expansion）
    首先，将递归关系式进行展开，得到每个子问题的解，并将其写成一个递归式的形式。

• Step 2: Construction of Recurrence Tree
  Construct a recurrence tree with the expanded recursive expressions, where each level of the tree represents a different recursion level, and each node represents a solution to a subproblem.

  • 第二步：递归树的构建（Recurrence Tree）
    将展开后的递归式构建成一个递归树，其中树的每一层代表递归的不同层次，每个节点表示一个子问题的解。

• Step 3: Solving the Recurrence Tree
  Analyze and solve the recurrence tree to obtain the analytical solution or recurrence relation of the problem, thereby determining the algorithm’s time complexity.

  • 第三步：求解递归树（Solving the Recurrence Tree）
    通过对递归树进行分析和求解，得到问题的解析解或递推关系，进而确定算法的时间复杂度。

• Step 4: Verification
  Finally, verify whether the obtained time complexity satisfies the original recursive relations to ensure the correctness of the analytical solution.

  • 第四步：验证（Verification）
    最后，验证求解得到的时间复杂度是否满足原始的递归关系式，以确保解析解的正确性。

Examples of merge sort and maximum subarray problem (归并排序和最大子数组问题的举例)

• Algorithm Concept

  • Divide the original array into two subarrays, solve the maximum subarray problem for each subarray separately, and then merge them to obtain the maximum subarray of the original array.
  • The problem can be recursively solved until the size of the array is small enough to be solved directly.

    • 分治算法思路
      • 将原始数组分成左右两个子数组，分别求解左右子数组的最大子数组，并将其合并成原始数组的最大子数组。
      • 问题可以递归地求解，直到数组的规模足够小，可以直接求解。

• Process of Divide and Conquer Algorithm

  • Divide: Divide the original array into two subarrays and solve the maximum subarray problem for each subarray separately.
  • Combine: Merge the maximum subarrays of the left and right subarrays to obtain the maximum subarray across the middle position.
  • Recurrence: Recursively solve the maximum subarray problem for the left and right subarrays until the size of the array is small enough to be solved directly.

    • 分治算法解决过程
      • 分解（Divide）：将原始数组分成两个子数组，分别求解左右子数组的最大子数组。
      • 合并（Combine）：合并左右子数组的最大子数组，得到跨越中间位置的最大子数组。
      • 递归（Recurrence）：递归地对左右子数组进行求解，直到数组的规模足够小，可以直接求解。

• Application of Expansion Method

  • Use the expansion method to analyze the time complexity of the divide and conquer algorithm. Firstly, expand the recursive relations, then construct the recursion tree, and finally solve the recursion tree to obtain the time complexity of the algorithm.

    • 扩展法的应用
      • 使用扩展法来分析分治算法的时间复杂度，首先展开递归关系式，然后构建递归树，并对递归树进行求解，最终得到算法的时间复杂度。

• Analysis of Time Complexity

  • Time Complexity of Divide Step: Typically Θ(1).
  • Time Complexity of Combine Step: Typically Θ(n).
  • Time Complexity of Recursive Calls: O(logn).
  • Combining the above steps, the time complexity of the maximum subarray problem is O(nlogn).

    • 时间复杂度分析
      • 分解步骤的时间复杂度：通常是 Θ(1)。
      • 合并步骤的时间复杂度：通常是 Θ(n)。
      • 递归调用的时间复杂度：O(logn)。
      • 综合以上步骤，最大子数组问题的时间复杂度为 O(nlogn)。

• Efficiency Analysis of the Algorithm

  • The divide and conquer algorithm for the maximum subarray problem is efficient when handling large-scale arrays because it decomposes the problem into smaller subproblems, solves them recursively, and then merges the solutions.
  • The algorithm’s time complexity is O(nlogn), suitable for handling large-scale arrays.

    • 算法效率分析
      • 最大子数组问题的分治算法在处理大规模数组时效率较高，因为它将问题分解成较小的子问题并递归地求解，然后将子问题的解合并起来。
      • 算法的时间复杂度为 O(nlogn)，适用于处理大规模的数组。

Master theorem (主方法, 在一般情境下解决递归关系式的方法)

The Master Theorem is a method used to solve recursive relations, particularly applicable to recursive relations in divide and conquer algorithms. It provides a quick way to calculate the time complexity of recursive algorithms without the need for detailed expansion and solving of recursive relations.

主方法（Master Theorem）是一种用于解决递归关系式的方法，特别适用于分治算法中的递归关系式。主方法提供了一种快速计算递归算法时间复杂度的方法，而无需详细展开和求解递归关系式。

The Master Theorem is applicable to recursive relations of the following form:

T(n) = aT(n/b) + f(n)

Here, ‘a’ is the number of recursive steps, ‘n/b’ is the size of each recursive step, and ‘f(n)’ represents the workload other than the recursive steps.

主方法适用于此形式的递归关系式:

T(n) = aT(n/b) + f(n)

其中，a是递归步骤的数量，n/b是每个递归步骤的规模，f(n)是除了递归步骤外的其他工作量。

The basic idea of the Master Theorem is to determine the time complexity of the recursive algorithm by comparing the number of recursive steps ‘a’, the ratio of sizes ‘n/b’, and the growth rate of the workload ‘f(n)’.

主方法的基本思想是通过比较递归步骤的数量a和规模的比例n/b以及其他工作量f(n)的增长速度，来确定递归算法的时间复杂度。

The Master Theorem has three cases:

1. If f(n) = O(n^c), where c < log_b(a), then the time complexity of the recursive algorithm is T(n) = Θ(n^log_b(a)).
2. If f(n) = Θ(n^c log^k n), where k ≥ 0 and c = log_b(a), then the time complexity of the recursive algorithm is T(n) = Θ(n^c log^(k+1) n).
3. If f(n) = Ω(n^c), where c > log_b(a), and af(n/b) ≤ kf(n) (for some constant k < 1 and sufficiently large n), then the time complexity of the recursive algorithm is T(n) = Θ(f(n)).

   主方法有三种情况

   1. 如果f(n) = O(n^c)，其中c < log_b(a)，则递归算法的时间复杂度为T(n) = Θ(n^log_b(a))。
   2. 如果f(n) = Θ(n^c log^k n)，其中k ≥ 0，且c = log_b(a)，则递归算法的时间复杂度为T(n) = Θ(n^c log^(k+1) n)。
   3. 如果f(n) = Ω(n^c)，其中c > log_b(a)，且af(n/b) ≤ kf(n)（对于某个常数k < 1和足够大的n），则递归算法的时间复杂度为T(n) = Θ(f(n))。

It’s important to note that the Master Theorem is only applicable to specific forms of recursive relations, and may not provide accurate time complexity for other forms of recursive relations.

需要注意的是，主方法只适用于特定形式的递归关系式，并且对于其他形式的递归关系式可能无法提供准确的时间复杂度。

Discussion and Conclusion

In this lesson, the instructor introduced

• how to solve recursive relations, focusing on divide-and-conquer algorithm.
• Demonstrated relationship between divide-and-conquer algorithm and recursive relations through examples.
• Explained setting up recursive relations.
• Introduced standard method for solving recursive relations, known as expansion method.
• Showed solving recursive relations by expanding them multiple times.
• Provided solutions for merge sort and maximum subarray problem.
• Mentioned solution method for recursive relations in general context, called master theorem.
• Master theorem offers solutions to recursive relations based on different scenarios.

  这节课上，讲师介绍了

  • 如何解决递归关系式，重点关注分治算法。
  • 通过示例演示了分治算法与递归关系式的关系。
  • 解释了如何设置递归关系式。
  • 引入了解决递归关系式的标准方法，称为扩展法。
  • 展示了通过多次扩展递归关系式来解决它们。
  • 提供了归并排序和最大子数组问题的解决方案。
  • 提及了在一般情境下解决递归关系式的方法，称为主方法。
  • 主方法根据不同情况给出了递归关系式的解决方案。

Reference

¹ Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. “Introduction to Algorithms,” Third Edition. The MIT Press, 2009. ↩
² Michael T. Goodrich, Roberto Tamassia, Michael H. Goldwasser. “Data Structures and Algorithms in Python,” Wiley, 2013. ↩
³ Sedgewick, Robert, Wayne, Kevin. “Algorithms,” Fourth Edition. Addison-Wesley Professional, 2011. ↩
⁴ Dasgupta, Papadimitriou, Vazirani. “Algorithms,” McGraw-Hill Science/Engineering/Math, 2008. ↩