回答編集履歴
3
追記
test
CHANGED
|
@@ -25,3 +25,23 @@
|
|
|
25
25
|
|
|
26
26
|
|
|
27
27
|
以上からf(n) = 3 ^nはo(2^n)の要素ではないと言えました。
|
|
28
|
+
|
|
29
|
+
|
|
30
|
+
|
|
31
|
+
### 以下、質問がありましたので追記します。
|
|
32
|
+
|
|
33
|
+
|
|
34
|
+
|
|
35
|
+
**(3 ^ n) / (2 ^ n) = (3 / 2) ^ n <= c**ですので
|
|
36
|
+
|
|
37
|
+
f(n) = 3^nがO(2^n)の要素である条件は結局次の形にまで変形できます。
|
|
38
|
+
|
|
39
|
+
|
|
40
|
+
|
|
41
|
+
**n <= log c (底は3/2)**
|
|
42
|
+
|
|
43
|
+
**c,nはともに正の数であり、cはnよりも先に確定しなければならない**
|
|
44
|
+
|
|
45
|
+
|
|
46
|
+
|
|
47
|
+
この条件を満たせないことは自明です。cを先に確定した場合n = 1+ log c (底は3/2）とすれば不等号が逆転します。つまり、**f(n) = 3^nがO(2^n)の要素である条件は満たされない。**といえます。
|
2
誤字訂正
test
CHANGED
|
@@ -20,7 +20,7 @@
|
|
|
20
20
|
|
|
21
21
|
**(3 ^ n) / (2 ^ n) <= c **
|
|
22
22
|
|
|
23
|
-
この式のcはnよりも先に確定できません。cを確定した場合、nを充分大きい値にすれば左辺
|
|
23
|
+
この式のcはnよりも先に確定できません。cを確定した場合、nを充分大きい値にすれば左辺は右辺よりも大きくなってしまいます。
|
|
24
24
|
|
|
25
25
|
|
|
26
26
|
|
1
調整
test
CHANGED
|
@@ -1,3 +1,27 @@
|
|
|
1
|
-
### まずは基本ですがO(n
|
|
1
|
+
### まずは基本ですがO(2^n)もO(3^n）も集合です。
|
|
2
2
|
|
|
3
|
-
そしてO(n
|
|
3
|
+
そしてO(2^n) ⊂ O（3^n)です。ここまでは自明ですよね。あとはO（3^n)の要素であり、O（2^n)の要素でないものを一つ以上提示すれば証明終了です。
|
|
4
|
+
|
|
5
|
+
|
|
6
|
+
|
|
7
|
+
例えば、f(n) = 3^nを考えてみましょう。これは明らかにO(3^n)の要素です。それではO(2^n）の要素でしょうか？仮にO(2^n)の要素であると仮定します。すると以下の条件が満たされることになります。
|
|
8
|
+
|
|
9
|
+
|
|
10
|
+
|
|
11
|
+
**3 ^ n <= c * (2 ^ n) **
|
|
12
|
+
|
|
13
|
+
**ただし、c,nはともに正の数であり、cはnよりも先に確定しなければならない**
|
|
14
|
+
|
|
15
|
+
|
|
16
|
+
|
|
17
|
+
この条件式の両辺は明らかにプラスの数です。両辺からプラスの数(2 ^ n)を割ります。すると次の式が得られます。
|
|
18
|
+
|
|
19
|
+
|
|
20
|
+
|
|
21
|
+
**(3 ^ n) / (2 ^ n) <= c **
|
|
22
|
+
|
|
23
|
+
この式のcはnよりも先に確定できません。cを確定した場合、nを充分大きい値にすれば左辺を右辺よりも大きくなってしまいます。
|
|
24
|
+
|
|
25
|
+
|
|
26
|
+
|
|
27
|
+
以上からf(n) = 3 ^nはo(2^n)の要素ではないと言えました。
|