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). 寻找例如二分搜索的分析，如果您需要更多详细信息，它具有类似的结构。