1

コードフォースの問題を解決しています。社説によると、次のコードの複雑さは O(n) である必要があります。

for(int i = n - 1; i >= 0; --i) {
    r[i] = i + 1;
    while (r[i] < n && height[i] > height[r[i]])
        r[i] = r[r[i]];
    if (r[i] < n && height[i] == height[r[i]]) 
        r[i] = r[r[i]];
}

ここで、height[i]は - 番目の丘の高さであり、は よりも高い右から 1i番目の丘r[i]の位置であり、height 配列の他の値の中で常に最大です。height[i]height[0]

私の質問は、内側の while ループが存在するにもかかわらず、コードの複雑さが O(n) であることをどのように保証できるでしょうか?

内側の while ループで、コードは>にr[i]なるまで値を更新します。更新の数は、高さの配列によって異なります。たとえば、非減少順でソートされた高さ配列の更新回数は、非増加順でソートされた高さ配列の更新回数とは異なります。(どちらの場合も、この問題では が常に最大であるため、を除く配列をソートします)。height[i]height[r[i]]height[0]height[0]

そして、このような入力データによって変化するアルゴリズムを分析する方法はありますか? 償却分析は答えの1つになりますか？

PS。私の質問をもっと明確にしたいと思います。ループ内に配列 r[] を設定します。そして、これはどうですか？配列height = {5,4,1,2,3}とi=1, ( r[2]=3, r[3]=42 は 1 より大きい最初の値であり、3 は 2 より大きい最初の値であるため) の場合、4 と 1 を比較し、4>1 であるため、比較を試み続けます。 4 と 2(= height[r[2]])、4 と 3(= height[r[3]])。この場合、r[1] を設定するために 4 回比較する必要があります。の場合とは比較回数が異なりますheight = {5,1,2,3,4}。コードの複雑さが O(n) であることを保証できますか? 見逃した場合はお知らせください。ありがとうございました。

4

2 に答える 2

0

あなたのアルゴ（それがあなたの問題を解決するかどうかはわかりません）は実際にはO（n）ですが、内部ループがありますが、ほとんどの場合、条件が与えられているため内部ループは実行されません。したがって、最悪の場合2n、O(n) である時間のように実行されます。

この仮定は、yourMethod内側のループが実行された回数を返す次のようなメソッドでテストできます。

   int arr[] = {1, 2, 3, 4, 5};
    do {
        int count = yourMethod(arr, 5);
    }while(next_permutation(arr, arr+5));

これにより、最悪のケース、平均的なケースなどを確認できます。

于 2013-05-29T11:41:27.930 に答える