2

そこで、2 つの並べ替えられた配列が与えられ、それらを新しい配列に結合して並べ替えを維持するという興味深い問題を見つけました。また、プログラムの効率を見つけます。コードは機能しましたが、効率についてはわかりません..配列のすべての要素を反復処理するために while ループを使用しているため、O(n) だと思います。任意のヒント？これをさらに効率的にする方法はありますか？O(n) は正しいですか? コードは次のとおりです。

class mergesorted{
    static void Main(string[] args){
        int[] x = { 1, 3, 7};
        int[] y = { 2, 4, 5, 6, 15};
        int[] retrieval =  answer(x, y);

        for (int i = 0; i < retrieval.Length; i++){
            Console.WriteLine(retrieval[i]);                
        }
        Console.ReadLine();
    }

    public static int[] answer(int[] x, int[] y)
    {
        int[] a = x;
        int[] b = y;
        int abc = 0; //counter for a
        int abc2 = 0; //counter for b
        int i = 0; //counter for index of new array
        Boolean flagA = true; //if flag changed, array is exhaused
        Boolean flagB = true;
        int[] newarray = new int[a.Length+b.Length]; //so size is 7

        while (abc < a.Length && abc2 < b.Length){
            if (a[abc] < b[abc2]){
                newarray[i] = a[abc];
                abc++;
            }
            else{
                newarray[i] = b[abc2];
                abc2++;
            }

            if (abc >= a.Length){
                flagA = true;
                flagB = false;
            }

            else if (abc2 >= b.Length){
                flagA = false;
                flagB = true;
            }
            i++;
        }

        if (flagA == false){
            while (abc < a.Length){
                newarray[i] = a[abc];
                abc++;
                i++;
            }
        }
        else if (flagB == false){
            while (abc2 < b.Length){
                newarray[i] = b[abc2];
                abc2++;
                i++;
            }
        }
        return (newarray);
    }
}
4

1 に答える 1

3

冗長なテストがたくさんあります。しかし、アルゴリズムは各要素に 1 回触れるため、O(N) です。最終的な配列の構築は O(N) であるため、(一般的なケースでは) それ以上のことはできません。

一方の配列が他方よりもはるかに大きく、O(1) の挿入 (または移動) 操作を行う特殊なケースでは、O(A log B) のアルゴリズムを作成できます。ここで、A は配列内のエントリの数です。小さい方のリストで、B は大きい方のリストのエントリ数です。たとえば、1 つの配列に 1,000,000 個のオブジェクトがあり、もう 1 つの配列には 2 個しかない場合、バイナリ検索を使用して、1,000,000 個のオブジェクト リストのどこに、2 つのオブジェクトをそれぞれ別のリストに移動するかを調べることができます。2 つのリストがほぼ同じサイズの場合、これは役に立ちません。

于 2013-09-23T04:57:23.503 に答える