time - 時間の複雑さの説明

Question

誰かがこのアルゴリズムの時間の複雑さを見つける方法を説明してもらえますか?バイナリ分割のためにO(logN)だと思いますが、よくわかりません

    int findRotationCount(int a[], int sizeOfArray) //O(logN)
    {
        int start = 0;
        int endValue = sizeOfArray -1;

        while(start<endValue)
        {
            if(a[start] < a[endValue])
                return endValue+1;
            else
            {
                int mid = (start+endValue)/2;

                if(a[start]<=a[mid] && a[mid+1]<=a[endValue])
                    return mid+1;
                else if(a[start]<=a[mid])
                    start = mid+1;
                else
                    endValue = mid;
            }
        }
        return -1;
    }

ありがとう！

Answer 1

そうです、の各ループはwhile範囲startをendValue（ほぼ）半分のサイズに縮小するので、ですO(log n)。詳細が必要な場合は、同様の構造を持つバイナリ検索などの分析を探してください。