CLRS Chapter 3 - 壊れた計算機

ビール飲んできた。うまかった。
Introduction to Algorithms / アルゴリズムイントロダクション
Theta,Big-O,Omega表記の定義、floor,ceiling,...などの表記の定義

Exercise 3.1-1

$c_1 = \frac{1}{2}\;,\;c_2 = 1$
とすればよい

Exercise 3.1-2

$c_1 = {\mathrm ceiling}(\frac{a}{n}) + 1\;,\;c_2 = 1$
とすればよい

Exercise 3.1-3

$0 \in O(n^2)$
だから

Exercise 3.1-4

$2^{n+1} \leq 2\cdot 2^n$
なので真
$2^{2n} = 4^n \;\;,\;\; \frac{4^n}{2^n} = 2^n \rightarrow \infty \; (n \rightarrow \infty)$
なので偽

Exercise 3.1-5

$f(n) = \Theta(g(n)) \;\Rightarrow \; \exists c_1,\;c_2,\;n_0\; s.t. \; \forall n > n_0 \;\; f(n) \leq c_1 g(n) \;\wedge\; f(n) \geq c_2g(n) \;\Rightarrow\; f(n) = O(n) \;\wedge \; f(n) = \Omega(n)$
逆はそれぞれのn0のmaxを取ればよい。

Exercise 3.1-6

不等号の遷移律を使用するだけ

Exercise 3.1-7

f(n)/g(n)のlimの先が0とInfになることから矛盾を導く

Exercise 3.1-8

Omegaは、cg(n,m)とf(n,m)をひっくり返して定義
Thetaは、Omega かつ Big-Oで定義

Exercise 3.2-1

略

Exercise 3.2-2

$a^{\log_b c} = b^{\log_b a \:\cdot\: \log_b c} = b^{\log_b c \:\cdot\: \log_b a} = c^{\log_b a}$

Exercise 3.2-3

Stirlingの近似でちょめちょめ

Exercise 3.2-4

ceil(lg n)! : おさえられない。簡単のため、n = 2^mの時を考えると、ceil(lg n)!はStirlingの近似より(m/e)^(m/e)以上になる。これはC^mではおさえられない
ceil(lg lg n)! : おさえられる。簡単のため、n=2^2^mの時を考えると、ceil(lg lg n)!はStirlingの近似より、O(m^(m+1))。これはC^2^mでおさえられる。（なぜなら両辺のlogをとれば、左：mlog(m),右：2^mとなるので）

Exercise 3.2-5

$\lg *(\lg n) = \lg * n \;- 1$
なので、lg*(lg n)のほうが漸近的に大きい。

Exercise 3.2-6

計算するだけ

Exercise 3.2-7

するだけ

Exercise 3.2-8

定数倍を無視して十分大きいnについて
$\frac{n}{\log n} \leq \frac{n}{\log\left(k\log k\right)} \leq \frac{n}{\log k} \leq k \leq \frac{n}{\log k} \leq \frac{n}{\log \frac{n}{\log n}} \leq \frac{n}{\log n}$

Problem 3-1

略

Problem 3-2

$A$	$B$	$O$	$o$	$\Omega$	$\omega$	$\Theta$
$\lg^k\:n$	$n^\epsilon$	yes	yes	no	no	no
$n^k$	$c^n$	yes	yes	no	no	no
$\sqrt{n}$	$n^{\sin n}$	no	no	no	no	no
$2^n$	$2^{n/2}$	no	no	yes	yes	no
$n^{\lg\:c}$	$c^{\lg\:n}$	yes	no	yes	no	yes
$\lg (n!)$	$\lg(n^n)$	yes	no	yes	no	yes

Problem 3-3

a

一時間くらいかかった
$1 = n^{1 / \lg n} < \lg(\lg *n) < \lg *(\lg n) = \lg *n < 2^{\lg *n} < \ln(\ln n) < \sqrt{\lg n} < \ln n < \lg ^2 n < 2^{\sqrt{2 \lg n}} < \sqrt{n} < n = 2^{\lg n} < \lg(n!)$
$= n\ln n < n^{\lg(\lg n)} < n^2 = 4^{\lg n} < n^3 \lt (\lg n)! < (\lg n)^{\lg n} < \frac{3}{2}^n < 2^n < n \cdot 2^n < e^n < n! < (n + 1)! <2^{2^n} < 2^{2^{n+1}}$

b

$2^{2{^{2^n}}}*(\sin(n)+1)$

Problem 3-4

a

b

$f(n) = 1,\;g(n)=n$
が反例

c

正しい

d

e

asymptotically positiveの定義による。f(n)にある部分列が存在してAn->inf かつ f(An) -> 0になってよいならば偽だと思う。そうでないならば真。

f

正しい

g

f = 2^x

h

正しい

Problem 3-5

a

f(n) != O(g(n))のとき、全てのc,n0について、あるnが存在してn>n0かつf(n) >= cg(n) >= 0となる。
c = 1, A0 = 1とする。An = 「c,An-1を上の命題に適用して得られたn」とおくことで、無限個のf(n) >= cg(n) >= 0を満たすnが{An}として得られる。