斯坦福算法专项课程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)\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,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乘法:
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