0

この方法でアルゴリズムの正確な時間の複雑さを知りたいです。arrays.sort; を使っているので nlogn だと思います。

public static int largestElement(int[] num) throws NullPointerException // O(1)
    {
    int a=num.length; // O(1)
    Arrays.sort(num); // O(1)? yes

    if(num.length<1) // O(1)
    return (Integer) null;
    else
    return num[a-1]; // O(1)
    }
4

3 に答える 3

2

あなたは自分の投稿で自分自身にひどく矛盾しているようです。メソッドが O(nlogn) であるという点では正しいですが、次は正しくありません。

Arrays.sort(num); // O(1)? yes

あなたが正しければ、メソッドは O(1) です! 結局、一連の O(1) プロセスの束は O(1) のままです。実際にArrays.sort()は、メソッドの全体的な複雑さを決定する O(nlogn) です。

ただし、配列またはコレクション内の最大の要素を見つけることは、常に O(n) になる可能性があります。これは、各要素を単純に反復して最大値を追跡できるためです。

于 2013-11-06T01:17:46.220 に答える
1

さすが、O(nlogn)です。Arrays.sort() はマージソートを使用します。ただし、この方法を使用することは、最大値を見つける最良の方法ではない場合があります。代わりに要素を比較して、配列をループすることができます。

于 2013-11-06T01:13:32.230 に答える