配列内の反転をカウントしようとしています (a[i] > a[j] および i < j の場合、2 つの要素 a[i] および a[j] は反転を形成します)。O(n^2) でブルート フォースを使用し、O(nlgn) で Divide and Conquer を使用することで、これらの問題を簡単に解決できることを私は知っています。
私の質問は、データに関する知識で O(n) の効率を達成するために、バケット手法の形式を使用することは可能かということでした。たとえば、配列が 1-32 の順列であることはすでにわかっているため、最大要素は 32 です (バケット化で何かを行うことができます)。
私はこれについて考えていて、バケツに要素を挿入している場合、挿入時にそれよりも大きいすべてのバケツの合計がその反転カウントであることに気付きました。しかし、毎回各バケットに要素の数を追加すると、O(n) の効率が失われます。このペナルティを取り除くためにカウントを維持する方法についての提案。
順列は任意の長さにすることができますが、実行中に順列内の要素の数がわかっていることに注意してください。したがって、「n」の値は実行中に認識され、順列は「1」から「n」までの要素で構成されます。
並べ替え: 32 個のバケットを作成でき、各バケットには 1 つの要素があることがわかっているため、このデータ セットを O(n) 時間の複雑さで並べ替えることができます。したがって、O(n + M) であるバケット ソートの効率は、この特定の例では O(n + 1) = O(n) です。