斯坦福算法专项课程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(\log n)$层,总共的时间复杂度为

选择题2

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

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

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

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

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

选择题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))$,但是

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

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

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

所以选项$2$是对的,此外从上述两个例子可以看出,该结论成立与否与$f,g$的大小有关,现在假设$f(n) \le g(n)$对于所有足够大的$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的时间复杂度为

总共的时间复杂度为

选择题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}$

由数学知识可知,顺序为

编程题

实现Karatsuba乘法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
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))
1
8539734222673567065463550869546574495034888535765114961879601127067743044893204848617875072216249073013374895871952806582723184