ランダウの記号についての質問です。


O(t/logN)というオーダーで表現されたものを実装したい場合、計算機上でどのように実装すると良いでしょうか?
参考文献を示してくださると助かります。
同様に、poly(t,logN)で値が示された場合の実装方法(計算方法)もご教示頂ければ、と思います。

オーダーやポリで示された状態よりも厳密な上界や近似で値を求めて使用したいので、よろしくお願いします。

回答の条件
  • 1人3回まで
  • 登録:2009/12/22 19:08:06
  • 終了:2009/12/29 19:10:03

回答(1件)

id:t-wata No.1

t-wata回答回数82ベストアンサー獲得回数132009/12/23 03:56:49

ポイント60pt

> O(t/logN)というオーダーで表現されたものを実装したい場合、計算機上でどのように実装すると良いでしょうか?

無理です。

通常Nは処理対象の要素の数を表すわけですが、Nの数が1以下の場合は定義できず、2のときが一番処理量が多く、

Nの数が増えるにしたがって処理量が少なくなって、Nが無限大に近づくと処理量が0に近づいていく、というようなものは

計算機上の処理ではありえないです。

たぶんO(t*logN)=O(logN^t)なんだろうとは思いますが。この場合、簡単のために、底を2として考えるのがよいです。

つまり、O(t*logN)は、要素数が倍になると、処理ステップがt回増える、というような処理を考えればよい訳です。

たとえば2分探索は明らかにO(logN)なので、これをベースに処理を考えれば簡単に実装できるんじゃないでしょうか?

id:TSB

回答ありがとうございます。

定義を明確にしていなかったこちらに非がありますね、すみません。

今回の場合、Nは十分大きな自然数しか取らない前提です。また、logの底は2を取ります。

ちなみに提示したのはO(t/logN)だったのですが、まぁ同じようなものですね。

ここでは通常使われる意味の計算量ではなく、集合の要素数の上限や、スレッショルドとして与えたい境界値が上記のオーダーで与えられていて、その上限を知ることが実装の肝になっています。

ほかの部分では、O(logN*loglogN/t^2)=poly(logN, 1/t^2)と表現されているので、この辺をうまく数値的に解析して実装などできないものか、と思っています。

あと、訂正が一点ありました。poly(t,logN)はpoly(1/t, logN)です。申し訳ありませんでした。

2009/12/23 09:37:50

コメントはまだありません

この質問への反応(ブックマークコメント)

「あの人に答えてほしい」「この質問はあの人が答えられそう」というときに、回答リクエストを送ってみてましょう。

これ以上回答リクエストを送信することはできません。制限について

絞り込み :
はてなココの「ともだち」を表示します。
回答リクエストを送信したユーザーはいません