CBMS-2017-07

题目来源：Problem 7 日期：2024-07-29 题目主题：CS-算法-时间复杂度分析

解题思路

1. 我们需要分别计算 $f={\sum }_{i=0}^n{a}_i{x}^i$ 的两种算法的时间复杂度。
2. 我们还需要分析两个大整数相乘的递归时间复杂度。

Solution

Part 1: Calculating Polynomial

(A) Individual Calculation of $f_i$ and Summation

First, consider calculating each term $f_i=a_i{x}^i$ individually and then summing them to get $f={\sum }_{i=0}^n{f}_i$.

• To compute each $f_i=a_i{x}^i$:

  • Computing $x^i$ takes $i$ multiplications.
  • Therefore, the time to compute $f_i$ is $O(i)$.

• Summing up the times for all $f_i$:

  ${\sum }_{i=0}^{n}O(i)=O(0+1+2+\cdots +n)=O\left(\frac{n(n+1)}{2}\right)=O(n^2)$

Thus, the overall time complexity is $O(n^2)$.

(B) Using Recurrence to Calculate $g_i$

The recurrence relation for $g_i$ is:

$$g_i=\{\begin{array}{ll}{a}_n& \text{when }i=n\\ g_{i+1}x+a_i& \text{when }i<n\end{array}$$

We calculate $g_n,g_{n-1},\dots ,g_0$ in this order:

• Calculating $g_n$ takes $O(1)$.
• Calculating $g_{n-1}$ from $g_n$ involves one multiplication and one addition, so it takes $O(1)$.
• Similarly, calculating each $g_i$ from $g_{i+1}$ takes $O(1)$.

Since there are $n+1$ such calculations, the overall time complexity is $O(n)$.

Part 2: Multiplying Large Integers

(A) Recursive Multiplication

Given: $ab=r_2{2}^{2n}+r_1{2}^n+r_0$ where:

• $r_2=a_{hi}{b}_{hi}$
• $r_1=a_{hi}{b}_{lo}+a_{lo}{b}_{hi}$
• $r_0=a_{lo}{b}_{lo}$

This involves four multiplications of $2^n$-bit integers: $T(2^{n+1})=4T(2^n)$

(B) Solving the Recursive Equation

The recurrence relation is: $T(2^{n+1})=4T(2^n)$

Let $k=n+1$. Then we have: $T(2^k)=4T(2^{k-1})$

Expanding this, we get: $T(2^k)=4^{k}T(2^0)$

Since $T(2^0)$ is a constant $C$, we get: $T(2^k)=4^{k}C$

Therefore, in terms of $n$: $T(2^n)=O(2^{2n})$

(C) Reducing Multiplications

Using the optimized method for $r_1$: $r_1=r_2+r_0-(a_{hi}-a_{lo})(b_{hi}-b_{lo})$

This involves three multiplications of $2^n$-bit integers: $T(2^{n+1})=3T(2^n)$

Solving this recurrence relation similarly: $T(2^k)=3^{k}T(2^0)$

Since $T(2^0)$ is a constant $C$, we get: $T(2^k)=3^{k}C$

Therefore, in terms of $n$: $T(2^n)=O(3^n)=O(2^{n{\log }_{2}3})$

知识点

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

重点词汇

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

参考资料

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