0

わかりました、まだ配列を学んでいます。「rand」という名前の配列を 0 から 1 までの乱数 (排他的) で埋めるこのコードを書きました。複雑さを学び始めたいです。For ループは O(1) 時間かかるたびに n 回 (100 回) 実行されるため、最悪のシナリオは O(n) ですよね? また、ArrayList を使用して 100 個の要素を格納し、「コレクション」をインポートして Collections.sort() メソッドを使用して要素を並べ替えました。

import java.util.Arrays;
    public class random
    {
        public static void main(String args[])
        {
            double[] rand=new double[10];

                    for(int i=0;i<rand.length;i++)
                    {
                        rand[i]=(double) Math.random();
                        System.out.println(rand[i]);
                    }   

                    Arrays.sort(rand);
                    System.out.println(Arrays.toString(rand));
        }
    }

配列リスト：

import java.util.ArrayList;
import java.util.Collections;

public class random
{
    public static void main(String args[])
    {
        ArrayList<Double> MyArrayList=new ArrayList<Double>();


        for(int i=0;i<100;i++)
        {               
            MyArrayList.add(Math.random());
        }

        Collections.sort(MyArrayList);


        for(int j=0;j<MyArrayList.size();j++)
        {
            System.out.println(MyArrayList.get(j));
        }

    }
}
4

1 に答える 1

2

はい、正解です。N 個のアイテムを追加する複雑さは O(N) です。ドキュメントによると、ほとんどの場合、並べ替えには追加の O(N * log(N)) が必要です。

ソート アルゴリズムは調整されたクイックソートであり、Jon L. Bentley と M. Douglas McIlroy の「Engineering a Sort Function」、Software-Practice and Experience、Vol. 23(11) P. 1249-1265 (1993 年 11 月)。このアルゴリズムは、多くのデータ セットで n*log(n) パフォーマンスを提供するため、他のクイック ソートでは 2 次パフォーマンスに低下します。

ArrayListはまだ配列に支えられているため、複雑さは同じになりますが、とにかく償却される時折のサイズ変更を除けば.

于 2012-09-01T15:48:46.673 に答える