O(t/logN)というオーダーで表現されたものを実装したい場合、計算機上でどのように実装すると良いでしょうか？
参考文献を示してくださると助かります。
同様に、poly(t,logN)で値が示された場合の実装方法（計算方法）もご教示頂ければ、と思います。
オーダーやポリで示された状態よりも厳密な上界や近似で値を求めて使用したいので、よろしくお願いします。
No.1
82
13
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)なので、これをベースに処理を考えれば簡単に実装できるんじゃないでしょうか？
2
3
3
回答ありがとうございます。
定義を明確にしていなかったこちらに非がありますね、すみません。
今回の場合、Nは十分大きな自然数しか取らない前提です。また、logの底は２を取ります。
ちなみに提示したのはO(t/logN)だったのですが、まぁ同じようなものですね。
ここでは通常使われる意味の計算量ではなく、集合の要素数の上限や、スレッショルドとして与えたい境界値が上記のオーダーで与えられていて、その上限を知ることが実装の肝になっています。
ほかの部分では、O(logN*loglogN/t^2)=poly(logN, 1/t^2)と表現されているので、この辺をうまく数値的に解析して実装などできないものか、と思っています。
あと、訂正が一点ありました。poly(t,logN)はpoly(1/t, logN)です。申し訳ありませんでした。