オーダーの問題がさっぱりわかりません

質問

2^(n+1)=O(2^n)
2^2n=O(2^n)
の二つが正しいかどうかなんですけどさっぱりです
詳しい方いませんか？

回答No.1

cyototu · ベストアンサー

貴方のいうオーダーの定義が判りませんが、私なりに意を汲んで、回答らしきものを書いてみましょう。

2^(n+1)/2^n =2　ですから、nをどんなに大きくとってもその大きさは２倍きり違いません。この場合、物理学者は同じオーダーと言うのが普通です。

ただし、　x^(n+1)/x^n=x となるので、もしxが0.5や２や３など、１の程度ではなくて、１より大変小さい数だったり、その反対に１より大変大きな数だった場合、この二つの比は大変小さかったり、その反対に大変大きかったりするので、物理学者はこの二つのオーダーは違うと言います。

一方、　2^(2n) /2^n =2^n ですから、nを無限に大きくすると、この値は発散してしまいます。すなわち、2^(2n) の方が2^nより圧倒的に大きくなります。ですから、少なくとも物理学者にとっては、この２つのオーダーは違うものと考えます。

お礼

しばらくパソコンが使えない状況だったので返事が遅くなってすいません。大変参考になりました。そういう考え方をすればいいのですね。ありがとうございました。

回答No.3

cyototu

＃１です。
私の回答と＃２さんの回答を見ていて気が付いたのですが、物理屋さんと数学屋さんの発想は随分違いますね。

ある大学で数学者と物理学者を一つにまとめてある学部を作ったとき、その一員になった物理学者の友人がいます。彼の言うには
　「数学屋さんて面白い発想をするんですね。われわれ物理屋は、『無限大』とは今自分が考えている数よりめちゃくちゃに大きな『有限な数』のことだと思っているのに、数学屋さんて本気で無限に大きいな数（注）を考えているみたいですよ」

文化の違いって面白いですね。

（注）例えば、複素平面を球に投影したときの北極等の一点のように。

お礼

ちょっとよくわかりませんが、考え方が違うってことですね。

回答No.2

adinat

数学では次のように定義します。以下、f(n),g(n)>0とします。

f(n)がg(n)と（n→∞のとき）同位のオーダーである
⇔（ある0<α≦β<∞があって、）α≦f(n)/g(n)≦βが(十分大なる)任意のnで成立する

f(n)がg(n)と同位のオーダーのとき、f(n)=O(g(n))(n→∞)と書きます。明らかに同位のオーダーというときは、反射律が成り立ち、g(n)はf(n)と同位のオーダーです。

f(n)=2^(n+1)、g(n)=2^nとおくと、f(n)/g(n)=2より、α=β=2とすればよいですから、f(n)はg(n)と同位のオーダーです。
f(n)=2^(2n)、g(n)=2^nのときは、f(n)/g(n)=2^nですので、α=1とはできますが、β=∞にとらないと、α≦f(n)/g(n)≦βが任意のnで成り立ちません。したがって、f(n)はg(n)と同位のオーダーではありません。

下のケースは、f(n)はg(n)より(n→∞のとき)高位の無限大である、などといったりすることもあります。このとき、g(n)=o(f(n))(n→∞)と小文字の"o"で表します（もっとも記号的にはg(n)はf(n)よりも低位の無限大、と読みますが）。

お礼

こんな定義があるのですね。メモしときます。役に立ちました。ありがとうございました。