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. ↩

Introduction to Karatsuba Algorithm

The Karatsuba algorithm, a foundational method for performing efficient multiplication of large numbers in computer science¹. Taught in Week 1 of the Dynamic Programming and Greedy Algorithms course at CU Boulder, the algorithm stands as a testament to the power of a divide-and-conquer strategy.

Karatsuba算法是计算机科学中用于进行大数乘法的基础高效方法¹。在科罗拉多大学波尔德分校的动态规划和贪心算法课程的第一周里教授了这个算法。这个算法证明了分治策略的威力。

The Karatsuba algorithm, named after Anatolii Alexeevitch Karatsuba, strategically breaks down the task of multiplying two n-digit numbers into simpler subtasks, avoiding the traditional computational complexity of multiplication. This approach illustrates the multiplicative properties of numbers and the time-saving potentials of recursion and divide-and-conquer techniques in algorithm development.

Karatsuba算法是以Anatolii Alexeevitch Karatsuba命名的，该算法巧妙地将两个n位数的乘法任务分解为更简单的子任务，从而避免了乘法的传统计算复杂性。这种方法说明了数字的乘法性质，以及在算法开发中递归和分治技术的节省时间的潜力。

In the following sections, we will delve into the mechanics of the Karatsuba algorithm, discuss its complexity, and examine applications where this algorithm truly shines.

在以下部分，我们将深入研究Karatsuba算法的机制，讨论其复杂性，并检查这个算法真正发光的应用。

The Mechanics of Karatsuba Algorithm

The Karatsuba algorithm commences multiplication by splitting both numbers into two halves. The upper half (most significant digits) is labeled as ‘a’ and ‘c’, and the lower half (least significant digits) is correspondingly ‘b’ and ‘d’. The algorithm breaks the traditional multiplication into three main multiplications, namely, ac, bd, and (a+b)(c+d). Calculation of (a+b)(c+d) results in obtaining the sum of ac, bd, and a pair of cross products (ad+bc). To receive the final result, ac is shifted left by m digits (where m is the number of digits in smaller half), and bd stays unaltered. This makes the algorithm faster than classical multiplication for sufficiently large numbers.

Karatsuba算法首先通过将两个数字分为两半来开始乘法运算。上半部分(最显著的数字)被标记为’a’和’c’，下半部分(最不显著的数字)相应地被标记为’b’和’d’。该算法将传统的乘法运算分解为三个主要的乘法运算，即ac, bd, 和(a+b)(c+d)。计算(a+b)(c+d)的结果是获得ac, bd, 和一对交叉乘积(ad+bc)的和。为了得到最终的结果，ac被向左移m位(其中m是较小的一半中的数字的位数)，而bd保持不变。这使得对于足够大的数字，该算法比传统的乘法运算快。

Karatsuba Multiplication Example

Here is an example that demonstrates how to use Karatsuba’s algorithm to calculate the multiplication of larger numbers. Let’s take the example of multiplying two 4-digit numbers: let’s say we want to calculate 1234 * 5678.

这是一个示例，演示了如何使用Karatsuba算法来计算较大数字的乘法。我们以两个4位数相乘为例：假设我们要计算 1234 * 5678。

Input:

Let’s consider two numbers:

• a = 1234
• b = 5678

Step 1: Splitting the Numbers

1. Split each number into two halves:
   • a = 12, 34
   • b = 56, 78

Step 2: Calculate Three Products

1. Calculate ac: 12 * 56 = 672
2. Calculate bd: 34 * 78 = 2652
3. Calculate (a+b)(c+d): (12+34)(56+78) = 46 * 134 = 6164

Step 3: Calculate Cross Products (交叉乘积)

1. Subtract ac and bd from (a+b)(c+d):
   • 6164 - 672 = 5492
   • 5492 - 2652 = 2840

Step 4: Combine Results

1. Shift ac left by the number of digits in smaller half:
   • Shift 672 left by 2 digits: 67200
2. Add the results:
   • ac * 10^4 + (ad+bc) * 10^2 + bd = 67200 + 2840 * 100 + 2652 = 7006652

Output:

The product of 1234 and 5678 is 7006652.

Code Resources

• https://github.com/MisakaBit/CUBoulder-MSCS/blob/main/Karatsuba%20Multiplication%20Algorithm.ipynb

Wrapping Up the Discussion

In this course, we delved into the operations of addition and multiplication for large numbers. Large numbers refer to numbers longer than the computer’s word length, and they find wide applications in various real-world scenarios, particularly in fields like cryptography.

在本课程中，我们深入研究了处理大数的加法和乘法运算。大数是指比计算机字长更长的数字，它们在现实世界中的许多场景中都有着广泛的应用，尤其在密码学等领域中。

• Addition Algorithm

  • The addition algorithm involves adding digits starting from the least significant bit and considering carryovers. If there’s a carryover, it gets added to the next digit’s calculation. Eventually, we obtain the sum of two large numbers.

    加法算法从最低位开始，逐位相加，并考虑进位的情况。如果有进位，则将进位加到下一位的运算中。最终，我们得到的结果就是两个大数的和。

• Multiplication Algorithm

  • For multiplication, we employ a method known as “vertical multiplication.” Each digit of one large number is multiplied with every digit of the other, and the results are added up. Carryovers are handled similarly to addition. Ultimately, we arrive at the product of two large numbers.

• 乘法算法使用了一种称为“竖式乘法”的方法来进行乘法运算。我们将一个大数的每一位与另一个大数的每一位相乘，并将结果相加。如果有进位，则将进位加到下一位的运算中。最终，我们得到的结果就是两个大数的乘积。

• Karatsuba Algorithm
  • In addition to the traditional multiplication algorithm, we also introduced the Karatsuba algorithm. The Karatsuba algorithm utilizes the divide-and-conquer approach, breaking down the multiplication problem of large numbers into smaller subproblems. By recursively solving these subproblems, the final result is obtained. This algorithm can significantly reduce the number of multiplication operations in certain cases, thus enhancing efficiency.

除了传统的乘法算法外，我们还介绍了Karatsuba算法的思想。Karatsuba算法利用分治的思想，将大数的乘法问题分解为更小的子问题，并通过递归求解这些子问题来获得最终结果。这种算法在某些情况下可以显著减少乘法的运算次数，从而提高算法的效率。

These algorithms not only effectively handle operations with large numbers but are also frequently required in fields like cryptography. Mastering these algorithms not only deepens our understanding of numerical operations but also allows us to apply this knowledge to solve practical engineering and scientific problems.

这些算法不仅可以有效地处理大数运算，而且在密码学等领域中经常需要进行这样的计算。掌握这些算法不仅可以帮助我们更好地理解数字运算的本质，还可以应用于解决实际的工程和科学问题。

Reference

¹ Karatsuba, Anatolii Alexeevitch. “The Complexity of Multiplication in Generic Algebras.” Proceedings of Steklov Institute of Mathematics 211 (1995): 169-183. ↩

Welcome to Hexo! This is your very first post. Check documentation for more info. If you get any problems when using Hexo, you can find the answer in troubleshooting or you can ask me on GitHub.

Quick Start

Create a new post

1

$ hexo new "My New Post"

More info: Writing

Run server

1

$ hexo server

More info: Server

Generate static files

1

$ hexo generate

More info: Generating

Deploy to remote sites

1

$ hexo deploy

More info: Deployment