java - 优秀、一般和糟糕情况下的复杂性

Question

我在 java 中创建了这个方法，用于指示整数数组是否已排序。它的复杂性是什么？我想如果好的是最坏情况下的 O(1) 是平均情况下的 O(n)？

static boolean order(int[] a){
  for(int i=0;i<a.length-1;i++){
    if(a[i]>a[i+1]) return false;
  }
 return true;
}

Answer 1

您没有透露任何有关您的输入的信息。所以假设它是完全随机的。因此，对于任何 2 个邻居对，我们有 50% 的机会对它们进行排序。这意味着我们进行 1 步的概率为 1，2 步为 0.5，3 步为 0.25，k 步通常为 2^(-k)。让我们计算预期的步数:

我不知道如何计算这个系列的总和所以我使用了 wolfram alpha 并得到了 answer: 2 , 所以它是一个常数。

据我了解，随机输入的平均情况是 O(1)。

我不确定这是计算平均复杂度的正确方法，但对我来说似乎没问题。