すべてのビットをゼロにインクリメントおよびリセットするという 2 つの操作をサポートするバイナリ カウンターがあるとします。単一ビットの変更または検査に Theta(1) 時間かかる場合、カウンターをビット配列として実装して、最初はゼロのカウンターでの一連のインクリメントおよびリセット操作に O(n) 時間かかるようにするにはどうすればよいでしょうか?
集計分析により、すべてのビットが毎回反転する必要はないという事実を考慮すると、インクリメントのみを許可するカウンターでは、n 回の操作に O(n) の時間がかかることがわかりました。しかし、インクリメント リセット カウンターの実装方法に行き詰まっています。私の知る限り、フリップはフリップであり、1111 が魔法のように通常より速く 0000 になることはありません。ただし、インクリメント操作を使用すると、非常に高価なすべて 1 の状況が頻繁に発生することはありません。
本当の問題は、リセットユーティリティで効率的なカウンターを実現する戦略が実際にあるのか、それともインクリメント操作だけでカウンターのようになることを証明しようとしているだけなのかということです。私が持っている唯一のヒントは、「上位1へのポインターを保持する」ことです。これは、前者を示唆しているようです。