时间复杂性检查

你会说这个函数的时间复杂度是多少？我认为它的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; 
     } 
    }

谢谢！

来源

2013-02-11 user1856602

对我来说看起来像O(N)，其中N是你的sizeOfArray值。

来源

2013-02-11 05:57:51

得到它并更改它，谢谢！ – user1856602 2013-02-11 06:11:31

我认为这是O(n)，其中n=sizeOfArray。这里的证明：如果满足下列条件中的至少一个满足

你的循环可以结束：

i=n =>有n迭代，因此，你的函数的复杂性O(n)。
A[i] > A[i+1] =>数组中存在一个成员，它大于下一个成员。在这里你必须考虑你的功能的最坏情况。对于这一个，它是一个按递增顺序排序的数组。这意味着你将遍历从第一个到最后一个成员的数组，并且永远不会找到满足的第二个条件。所以，在最坏的情况下，复杂性是O(n)。

因为你的函数结束时的条件1至少一到两个得到满足，我们已经证明了，在这两种情况下，复杂度为O (n)，那么你就可以说，功能的复杂性也是O(n)。请注意，这是最糟糕的情况分析。

来源

2013-02-11 10:35:59 Milos

时间复杂性检查

回答

相关问题