0

これは、より良い方法があるかどうかを知りたいタスク固有のコードです。したがって、ロジックとコーディングが好きな人は、私を助けてください。

これは質問です：

A を n 個の正の整数の配列とします。すべての要素が異なります。A[i] > A[j] かつ i < j の場合、ペア (i, j) は A の特別なペアと呼ばれます。与えられた n から A の特別なペアの数を見つけます。

その非常にシンプルでまっすぐです。これが私が実装した次のソリューションです。ロジック部分。

         for(int j=0;j<nos.size();j++)
            {
                    for(int k=j+1;k<nos.size();k++)//always maintain condition that i<j and simply compare the numbers.
                    {
                            if(nos[j] > nos[k])
                            {
                                    spc++;//compute special pair.
                            }
                    }
            }

すべての nos[i] には、特別なペアが計算される配列が含まれています。単一のループを使用してこれを行う方法はありますか? または、時間を節約でき、より高速なその他のロジック。事前に感謝します。これからもっと学びたいと思います。

また、コードを実行せずにどのコードがより高速であるかを判断する方法を教えてください。あなたの意見は大歓迎です。

主な問題は、特別なペアの数を計算することです。したがって、spc の増分だけです。

4

3 に答える 3

2

二次ランタイムよりもうまくできるということですか? いいえ。これを確認するには、減少シーケンスを検討してくださいA = (N, N - 1, ..., 2, 1)。このシーケンスでは、のすべてのペア(i, j)がi < j特別であり、O(N^2)そのようなペアがあります。すべての特別なペアを出力する必要があるため、そのために二次時間が必要です。

于 2013-09-28T20:15:46.747 に答える
1

アルゴリズムを改善できるとは思いません。私の意見では、O(n²) の複雑さを示しています。長さ n の配列に対してプログラムが実行しなければならない内部ループの数を数えることで、それを証明できます。最初のループは n-1 回、2 番目のループは n-2 回、3 番目のループは n-3 回というように繰り返されます。最初の n 個の整数の合計の式を使用してそれを合計します (今回は後方のみで、1 から n ではなく 2 から n-1 から):

(n-1)+(n-2)+(n-3)+...3+2 = n*(n-1)/2 - 1. 比較する他の要素が残っていないため、最後に残った要素をループする必要はありません。実際、これはあなたのアルゴリズムに見られる唯一の改善です;-):

for(int j=0;j<nos.size();j++)

に

for(int j=0;j<nos.size()-1;j++)

大きな n を合計すると、式 n*(n-1)/2 - 1 は n² のように動作し、それが O(n²) の由来であると私は信じています。私が間違っている場合は、私を修正してください。

于 2013-09-28T21:12:44.747 に答える