7

一定時間内に数字の異なる桁を数えることは可能O(1)ですか？

個別の数字があるため、n=1519出力は次のようになります。33(1,5,9)

私は時間内にそれをしましO(N)たが、誰かが時間内にそれを見つける方法を知ってO(1)いますか？

4

2 に答える 2

6

Nの桁数だと思いnます。のサイズが無制限の場合、一般に O(1) 時間ではn実行できません。

n=11111...1112兆桁の数字を考えてみましょう。1数字の 1 つを a からaに切り替えた場合2、何らかの方法ですべての数字を調べずにこれを発見する方法はありません。Nしたがって、2 兆桁の数値を処理するには、少なくとも 2 兆回の操作が必要であり、一般に、桁のある数値は少なくとも 2 兆回の操作が必要Nです。

ただし、ほとんどすべての数値について、単純なO(N)アルゴリズムは非常に迅速に終了します。これは、10 桁になるとすぐに停止できるためです。十分な長さのほとんどすべての数はすべて 10 桁になります。たとえば、最初の 100 桁を見た後に答えが '10' で終わらない確率は約 0.00027 で、最初の 1000 桁の後では約 1.7e-45 です。しかし、残念なことに、最悪のケースになる奇妙な点がいくつかありO(N)ます。

于 2013-03-12T13:40:30.593 に答える
2

誰かがこの質問に対して真剣な回答を投稿したことを確認した後、ここで自分のチートを繰り返したいと思います。これは、@SimonNickerson が説明した回答の特殊なケースです。

基数 2 でない限り、O(1) は不可能です。そのようにすると、0 以外のすべての数値には 1 と 0 の両方が含まれるため、私の「解決策」は整数だけでなく...

編集

2^k - 1 はどうですか? 全部1じゃない？

ドラット！確かに...何かがとても簡単に見えるとき、それはどういうわけか欠陥があることを知っておくべきでした...すべて0のケースをカバーした場合、すべて1のケースもカバーする必要がありました。

幸いなことに、このケースは非常に迅速にテストできます (加算とビットごとの AND が O(1) 演算と見なされる場合): x がテストされる数値である場合、y を次のように計算しますy=(x+1) AND x。ならy=0、x=2^k - 1。これは、加算によってすべてのビットを反転する必要がある唯一のケースだからです。もちろん、これにはかなりの欠陥があります。ビット長がバス幅を超えると、ビット単位の演算子は O(1) ではなく、O(N) になります。

同時に、数値をバス幅サイズのチャンクに分割し、隣接するチャンクを AND 処理して、1 つだけが残るまで繰り返すことにより、O(logN) に下げることができると思います。テストされた数、最後のものも完全な1になります...

EDIT2：私は間違っていました...これはまだO（N）です。

于 2013-03-12T14:09:31.653 に答える