跳到主要内容

東京大学 新領域創成科学研究科 メディカル情報生命専攻 2016年8月実施 問題7

Author​

zephyr

Description​

(1) Given an integer , we calculate a polynomial, . A single addition or multiplication of two values takes a unit time regardless of the number of the digits in the representation of the values.

  • (A) Let . Find the time complexity (with regard to ) of an algorithm that calculates individually and then calculates .

  • (B) Let . Notice that holds. Find the time complexity (with regard to ) of an algorithm that calculates , hence by calculating in this order.

(2) Given two -bit integers and , let be the highest bits of and , and the lowest bits of and , respectively. We calculate the product of and when is fairly large. Assume that computation time for addition or shift is negligible compared to that for multiplication.

  • (A) The multiplication of -bit integers can be constructed from the multiplication of -bit integers as follows: , where . We can recursively apply this reduction until every multiplication only involves integers small enough to fit in the machine word of the computer. Let be the number of machine-word multiplications required in the multiplication of two -bit integers. Express in terms of .

  • (B) Solve the recursive equation you answered in (A), and express in Landau's notation.

  • (C) We reduce the number of multiplications in the calculation in (A) by calculating as . Express in Landau's notation, and prove it.

(1) 给定一个整数 ，我们计算一个多项式，是自然数。两个值的单次加法或乘法的计算时间是一个单位时间，与值的表示形式中的位数无关。

  • (A) 令 。找到一个算法的时间复杂度（关于 ），该算法分别计算 ，然后计算 。

  • (B) 令 当时当时。注意 成立。找到一个算法的时间复杂度（关于 ），该算法计算 ，从而通过依次计算 得到 。

(2) 给定两个 位的整数 和 ，令 为 和 的最高 位， 为 和 的最低 位。我们在 较大时计算 和 的乘积。假设加法或移位的计算时间相对于乘法可以忽略不计。

  • (A) 位整数的乘法可以通过 位整数的乘法构造，如下所示：，其中 。我们可以递归地应用这种缩减，直到每次乘法仅涉及足够小的整数以适应计算机的机器字。设 为两个 位整数相乘所需的机器字乘法次数。用 表示 。

  • (B) 解答你在 (A) 中回答的递归方程，并用 Landau 符号 表示 。

  • (C) 我们通过计算 为 来减少 (A) 中的乘法次数。用 Landau 符号 表示 ，并证明它。

Kai​

(1)​

(A)​

First, consider calculating each term individually and then summing them to get .

  • To compute each :

    • Computing takes multiplications.
    • Therefore, the time to compute is .

  • Summing up the times for all :

Thus, the overall time complexity is .

(B)​

The recurrence relation for is:

We calculate in this order:

  • Calculating takes .
  • Calculating from involves one multiplication and one addition, so it takes .
  • Similarly, calculating each from takes .

Since there are such calculations, the overall time complexity is .

(2)​

(A)​

Given:

where:

This involves four multiplications of -bit integers:

(B)​

The recurrence relation is:

Let . Then we have:

Expanding this, we get:

Since is a constant , we get:

Therefore, in terms of :

(C)​

Using the optimized method for :

This involves three multiplications of -bit integers:

Solving this recurrence relation similarly:

Since is a constant , we get:

Therefore, in terms of :

knowledge​

时间复杂度 递归 复杂度分析

重点词汇​

  • polynomial 多项式
  • time complexity 时间复杂度
  • recurrence relation 递归关系
  • multiplication 乘法

参考资料​

  1. Introduction to Algorithms, Cormen et al., Chap. 2 (时间复杂度分析)
  2. Introduction to Algorithms, Cormen et al., Chap. 30 (多项式和大整数运算)