時間計算量とオーダーに関する問題がわかりません

質問

1.サイズnの入力に対する、あるアルゴリズムの時間計算量f(n)が、F(n)=2^(2n)であるとする。
このとき、f(n)がO(2^n)でないことを示しなさい。

2.サイズnの入力に対する、あるアルゴリズムの時間計算量f(n)が、f(n)=c^(2n)であるとする。ただし、CはC>1の実数とする。このとき、F(n)がO(c^n)であるといえるか否かを示しなさい。

この二つの問題ですが、全然分かりません。
導出方法を教えてください。お願いします。

回答No.1

okormazd · ベストアンサー

関数g(n)があるとして、O(g(n))の定義は、
lim(n→∞)f(n)/g(n)=const
のg(n)があること、だったか。
1.
f(n)=2^(2n)
g(n)=2^n
とすると、
lim(n→∞)2^(2n)/2^n=lim(n→∞)2^n*2^n/2^n=lim(n→∞)2^n=∞
だから、f(n)はO(2^n)じゃない。

2.
も同じように考えればいいのでは。

確認していないので、的外れかも。

補足

私の頭では理解ができません。。
もっと簡単な方法はないでしょうか、、

回答No.2

Tacosan

O(g(n)) の定義は (普通は違う形で書くけど)
「有限個の n を除いて f(n) ≦ c・g(n) であるような定数 c が存在する」
です＞#1. あるいは lim じゃなくて limsup ならだいたいそれで OK かな.

まあ #1 の本題には影響ありませんが.