Algorithm Quizzes

Quiz 1Permalink

Sort the following terms from slowest growing to fastest growing.

这题其实非常 tricky。

首先要注意两点：

• $2^{{\log }_{2}n}=n$
• $5^{{\log }_{3}n}=n^{{\log }_{3}5}$

所有我们上来可以排列成 3 组：

• $({\log }_{2}n+1{)}^3<1000({\log }_{2}n{)}^3$
• $n^{\frac{1}{2}}<2^{{\log }_{2}n}<n\log n$
• $5^{{\log }_{3}n}<n^{{\log }_{3}7}<7^{2n}<2^{7n}$

我们事后诸葛亮一下：这个问题可以转化为证明下面两个不等式：

• $1000({\log }_{2}n{)}^3<n^{\frac{1}{2}}$
• $n\log n<5^{{\log }_{3}n}$

1. 不等式一Permalink

令 $f(n)=1000({\log }_{2}n{)}^3-n^{\frac{1}{2}}$。令 $n=2^{2k}$，于是得到：$f(n)=8000k^3-2^k$

这个很明显 $\underset{k\to +\mathrm{\infty }}{lim}8000k^3-2^k=-\mathrm{\infty }$

所以：$({\log }_{2}n{)}^3<n^{\frac{1}{2}}$

2. 不等式二Permalink

令 $f(n)=n\log n-5^{{\log }_{3}n}=n\log n-n^{{\log }_{3}5}$。令 $n=2^k$，于是得到：$f(n)=2^{k}k-2^{k\times {\log }_{3}5}=2^k(k-2^{({\log }_{3}5-1)\times k})$

因为 ${\log }_{3}5-1>0$，所以 $\underset{k\to +\mathrm{\infty }}{lim}k-2^{({\log }_{3}5-1)\times k}=-\mathrm{\infty }$

所以：$n\log n<5^{{\log }_{3}n}$

3. 综上Permalink

Quiz 2Permalink

求以下两段代码各自的 computational cost：

(1) while (n > 2)
	n = sqrt(n); 
(2) while (n > 2) 
	n = log(n)

解：(1) 假设 while 运行 $i$ 次时 $n$ 的值为 $n(i)$，有：

• $n(1)=n^{\frac{1}{2}}$
• $n(2)=n^{\frac{1}{4}}$
• ……
• $n(i)=n^{\frac{1}{2^i}}$

假设 $n(k)=p\le 2$，while 结束，有：

• $p=n^{\frac{1}{2^k}}$，两边同时 $2^k$ 次方，得：
• $p^{(2^k)}=n$，两边同时取对数，得：
• $(2^k)\times \log p=\log n$，两边再次取对数，得：
• $\log 2^k+\log \log p=\log \log n$，即：
• $k\times \log 2+\log \log p=\log \log n$

$\because$ $\log \log p$ 和 $\log 2$ 都是常数，$\therefore k\in O(\log \log n)$ ，即算法复杂度为 $O(\log \log n)$

解：(2) 这题需要一个引入概念，叫 iterated logarithm:

根据这个定义：${\log }_2^{\ast }2=1,{\log }_2^{\ast }{2}^2=2,{\log }_2^{\ast }{2}^{2^2}=3,\dots$

假设 while 运行 $i$ 次时 $n$ 的值为 $n(i)$，有

• $n(1)=\log n$
• $n(2)=\log \log n$
• ……
• $n(i)=\log \log \cdots \log n$ ($i$ 个 $\log$)

假设 $n(k)=p\le 2$，while 结束，根据 iterated logarithm，有：

$\because$ $lo{g}^{\ast }(p)$ 为常数，$\therefore k\in O({\log }^{\ast }n)$ ，即算法复杂度为 $O({\log }^{\ast }n)$

Quiz 3Permalink

如何判断一个正整数是不是 2 的 n 次方？

解：设 $x=2^n$，$x$ 有 $m$ bits，则 $x$ 的最高位为 1，后 $m-1$ 位为 0

同时 $x-1$ 的最高位为 0，后 $m-1$ 位为 1，所以做 AND 运算有 x & (x - 1) == 0