-3 
package com.sort;

public class ArraySel {

    private Long[] a;
    private int nElems;

    public ArraySel(int max)
    {
        a = new Long[max];
        nElems = 0;
    }

    public void insert(long max)
    {
        a[nElems] = max;
        nElems++;
    }

    public void display()
    {
        for(int j = 0; j < nElems; j++)
        {
            System.out.print(a[j]+ "  ");
        }
        System.out.println();
    }

    public void insertionSort()
    {
        int in , out, flag = 0;
        long temp;
        for(out = 1; out < nElems; out++)
        {
            temp = a[out];
            in = out;
            while(in > 0 && a[in - 1] >= temp )
            {
                if(a[in] == a[in - 1 ])
                {
                    flag++;
                    in--;
                }
                else
                {
                    a[in] = a[in-1];
                    in--;
                }
            }
            a[in] = temp;
        }
    }

}

このコードは、並べ替えられていない配列を受け取り、挿入並べ替えを使用して並べ替えます。重複が並べ替えられていない配列で一緒に配置されると、複数のシフトの複雑さが原因で、重複が一緒に配置された場合に複数回移動するアイテムがないことを確認して作成O(N^2)しようとしました。O(N)

しかし、重複が一緒に配置されていない場合、複雑さが残りO(N^2)ます。O(N)この場合も複雑にできますか？

4

2 に答える 2

2

複雑さは、移動の数ではなく、全体的な操作の数 (この場合は比較も) によって決まります。

挿入ソートは O(n^2) 平均の複雑さです。それより速くすることはできません。O(n) で動作するのは、入力文字列が既にソートされている場合 ( http://en.wikipedia.org/wiki/Insertion_sort ) の最良のシナリオでのみです。

于 2014-06-23T09:48:45.240 に答える
1

基礎となるデータに関する詳細情報がなければ、ソート アルゴリズムで実現できる最適な 時間の複雑度O(n log n)は( nは要素の数) です。

挿入ソート、バブル ソート、選択ソートなどのソート アルゴリズムはすべて、O(n²)ループが 2 つあるため、時間的に複雑です。実際、すでにソートされた要素のリストを取得する場合は、よりうまく機能する傾向があります。たとえば、挿入ソートO(n)には、完全にソートされたリストの時間の複雑さがあります。

これらのアルゴリズムに固有の時間の複雑さを変更するためにできることは何もありません。できる唯一のことは、着信リストで事前に並べ替えられた領域を見つけるときにアルゴリズムをショートカットすることです。

于 2014-06-23T09:53:43.307 に答える