人力検索はてな
モバイル版を表示しています。PC版はこちら
i-mobile

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

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

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

●質問者: TSB
●カテゴリ:コンピュータ 学習・教育
✍キーワード:ランダウ 表現 計算 計算機
○ 状態 :終了
└ 回答数 : 1/1件

▽最新の回答へ

1 ● t-wata
●60ポイント

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

無理です。

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

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

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

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

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

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

◎質問者からの返答

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

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

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

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

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

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

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

関連質問


●質問をもっと探す●



0.人力検索はてなトップ
8.このページを友達に紹介
9.このページの先頭へ
対応機種一覧
お問い合わせ
ヘルプ/お知らせ
ログイン
無料ユーザー登録
はてなトップ