斯坦福算法专项课程Course1 week1习题解析

这一部分将带来Course1 week1的习题解析。

选择题

选择题1

3-way-Merge Sort：假设在Merge Sort的每一步中不是分成两半，而是分成三分之一，对每部分进行排序，最后使用三向合并子程序将它们组合起来。这个算法的整体渐近运行时间是多少？（提示：请注意，合并步骤仍然可以在中实现$O(n)$时间。）

$n$
$n^2\log(n) $
$n ( \log(n))^2 $
$n\log(n) $

这里和课件中的区别为树状图为三叉树，即第$j$层有$3^j$个子问题，每个子问题的大小规模为$\frac{n}{3^j}$，由于长度为$m$的数组每次Merge操作需要的时间复杂度为$O(m)$，所以第$j$层的时间复杂度为

$O(3^j \times \frac{n}{3^j}) =O(n)$

因为为三叉树，所以一共有$O(\log n)$层，总共的时间复杂度为

$O(n\log n)$

选择题2

给你两个函数$f,g$满足$f(n) = O(g(n))$，那么$f(n)\times \log_2(f(n)^c) = O(g(n)\times\log_2(g(n))) $是否成立，其中$c$为正常数，你可以假设$f,g$非递减并且都大于$1$

有时是，有时不是，取决于$f$和$g$
错误
有时是，有时不是，取决于常数$c$
正确

因为$f(n) = O(g(n))$，所以存在$n_0,k$，使得当$n\ge n_0$时，

$f(n) \le k g(n)$

因为$f,g$都大于$1$，当$n\ge n_0$时

$\begin{aligned} f(n)*\log_2(f(n)^c) &= cf(n)*\log_2(f(n))\\ &\le ckg(n) *\log_2(kg(n)) \\ &= ckg(n) *(\log_2k+\log_2 g(n))\\ &\le m * g(n)*\log_2 g(n) \end{aligned}$

上述不等式关系可能不太严格，但是这里主要估计数量级，无伤大雅，所以这个结论是正确的。

选择题3

两个非递减的正函数$f,g$满足$f= O(g(n))$，是否满足$2^{f(n)} = O(2^{g(n)})$

正确，如果$f(n) \le g(n)$对于所有足够大的$n$
有时正确
从不正确
总是正确

先举一个例子：$f(n) =n ,g(n)=2n$，那么$f= O(g(n))$，但是

$\begin{aligned} 2^{f(n)} &= 2^n\\ 2^{g(n)} &= 2^{2n} =4^n \end{aligned}$

所以$2^{f(n)} = O(2^{g(n)})$成立

再举一个例子$f(n) =2n ,g(n)=n$，那么$f= O(g(n))$，并且

$\begin{aligned} 2^{f(n)} &= 2^{2n} =4^n\\ 2^{g(n)} &= 2^n \end{aligned}$

所以$2^{f(n)} = O(2^{g(n)})$不成立

所以选项$2$是对的，此外从上述两个例子可以看出，该结论成立与否与$f,g$的大小有关，现在假设$f(n) \le g(n)$对于所有足够大的$n$，那么

$2^{f(n)} \le 2^{g(n)}$

从而$2^{f(n)} = O(2^{g(n)})$

因此这题前两个选项均正确。

选择题4

k-way-Merge Sort。假设你得到了$k$个排好序的数组，每个都有$n$元素，并且你希望将它们组合成一个有$kn$个元素数组。考虑以下方法。使用讲座中讲授的merge方法，merge前$2$个数组，然后用merge后的前两个数组merge第$3$个数组，依此类推，直到你把第$k$个数组merge完。这个连续合并算法的运行时间是多少？作为$k,n$的函数（可选：您能想到更快的方式来进行k-way合并过程吗？）

$\theta(n^2k)$
$\theta(nk)$
$\theta(n \log (k))$
$\theta(nk^2)$

merge两个数组的时间和两个数组中较长的长度成正比，所以上述算法中，第$i$次merge的时间复杂度为

$\theta(in)$

总共的时间复杂度为

$\sum_{i=1}^k \theta(in) = \theta(k^2n)$

选择题5

按递增的顺序排列以下函数，$g(n)$在$f(n)$之后当且仅当$f(n)=O(g(n))$

a)$2^{2^n}$

b)$2^{n^2}$

c)$n^2 \log (n)$

d)$n$

e)$n^{2^n}$

由数学知识可知，顺序为

$dcbae$

编程题

实现Karatsuba乘法：

def Karatsuba(x, y):
    if x < 10 or y < 10:
        return x * y
    else:
        #计算位数
        k = min(len(str(x)), len(str(y))) // 2
        u = 10 ** k
        a = x // u
        b = x - a * u
        c = y // u
        d = y - c * u
        #递归
        ac = Karatsuba(a, c)
        bd = Karatsuba(b, d)
        abcd = Karatsuba(a + b, c + d)
        #合并结果
        adbc = abcd - ac - bd
        
        res = u ** 2 * ac + u * adbc + bd
        
        return res
    
x = 3141592653589793238462643383279502884197169399375105820974944592
y = 2718281828459045235360287471352662497757247093699959574966967627

print(Karatsuba(x, y))

8539734222673567065463550869546574495034888535765114961879601127067743044893204848617875072216249073013374895871952806582723184