time - 時間複雑度チェック

Question

この関数の時間計算量はどのくらいですか? O（logN）だと思いますが、確認できますか？そうでない場合、LogNにすることは可能ですか? 回転した配列のシフト量をカウントしようとしています

    int findRotationCount(int A[], int sizeOfArray) //O(logN)
    {
        int countOfShift = 0, i;
        for (i = 0; i < sizeOfArray; ++i)
        {
            ++countOfShift;
            if (i+1 == sizeOfArray)
                break;;
            if (A[i] > A[i+1])
                break;
        }
    }

ありがとう！

Answer 1

私はそれがO(n)どこにあると思いますn=sizeOfArray。証拠は次のとおりです。

次の条件の少なくとも 1 つが満たされた場合、ループを終了できます。

1. i=n=>n反復があったため、関数の複雑さは ですO(n)。
2. A[i] > A[i+1]=> 配列内に、次のメンバーより大きいメンバーが存在します。ここでは、関数の最悪のケースについて考える必要があります。これは、昇順で並べ替えられた配列です。つまり、最初のメンバーから最後のメンバーまで配列を反復処理し、この 2 番目の条件が満たされないことを意味します。したがって、最悪の場合、複雑さはO(n).

条件 1 と 2 の少なくとも 1 つが満たされたときに関数が終了し、どちらの場合も複雑さが O(n)であることが証明されているので、関数の複雑さも であると言えますO(n)。これは最悪のケースの分析であることに注意してください。

Answer 2

O(N)私のように見えNます、あなたのsizeOfArray価値はどこにありますか。