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. i=n=> 有n迭代，因此，你的函数的复杂性是O(n).
2. A[i] > A[i+1]=> 数组中有一个成员，大于下一个。在这里，您将不得不考虑您的功能的最坏情况。对于这个，它是一个按升序排序的数组。这意味着您将从第一个成员到最后一个成员遍历数组，并且永远找不到满足第二个条件。所以，在最坏的情况下，复杂度是O(n).

由于您的函数在至少满足条件 1 和条件 2 之一时结束，并且我们已经证明在这两种情况下复杂度都是 O (n)，那么您可以说函数的复杂度也是O(n). 请注意，这是最坏情况分析。

Answer 2

看起来O(N)对我来说，N你的sizeOfArray价值在哪里。