0

以下のコードは、数値が配列に表示される回数を見つけるためのものです。例えば：

1,2,2,2,3,4,5,5,5,5 number 2 = 3 times number 5 = 4 times.

以下のコードのJavaの時間計算量はどれくらいですか？時間計算量に関してこの問題を解決するための最良の方法は何ですか？

public static void main(String[]args)
    {
        int[] data = {1,1,2,3,4,4,4,5,6,7,8,8,8,8};
        System.out.println(count(data,8));


    }


public static int count(int[] a, int x)
{
    int count=0;
    int index=0;
    while(index<a.length)
    {
        if(a[index]==x)
        {
            count++;
        }
        index++;

    }
    return count;
}
4

6 に答える 6

3

それはo（n）、logNまたはそれ以外ですか？

すべての要素を一度見ると、O（n）になります。

o（n）の場合、LogNの共犯でこのタスクを実行できますか？

低い値と高い値を使用してバイナリ検索を実行し、検索する値よりも少し小さい値とそのすぐ上の値を検索します。これら2つの結果の違いから、いくつあるかがわかります。これはO（Log N）検索です。

于 2013-01-06T09:43:05.387 に答える
1

while(index<a.length)

このループは、の値ごとに1回実行されdataます。これはO（n）です。O（log n）でこれを実行する場合は、ソートされた配列とバイナリ検索が必要になります。ソートされた配列があるので、バイナリ検索を実行する必要があります。

于 2013-01-06T09:42:34.700 に答える
1

答えはO（n）です。

配列をループして、すべてのインデックスを1回確認します。

たとえば、配列サイズは10-> 10の比較、配列サイズは100->100の比較などです。

于 2013-01-06T09:42:43.587 に答える
1

配列の各要素を調べるため、コードにはO(n)時間計算量があります。

時間内にそれを行うにはO(log n)、配列がソートされているという事実を利用する必要があります。これは、二分探索の変形で行うことができます。これは宿題のように見えるので、ヒントを提供する前に少し考えてみましょう。

于 2013-01-06T09:42:46.310 に答える
0

O（n） このコードは、配列の各要素を使用します。

while(index<a.length)

あなたはそれを置き換えることができます

for(int index = 0; index < a.length; i++)
于 2013-01-06T09:44:42.617 に答える
0

O（n）。コードが配列のすべての要素を反復処理するとき、その0（n）。

于 2013-01-06T10:17:12.990 に答える