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 并得到了答案： 2，所以它是一个常数。

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

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

Answer 2

通常在最坏的情况下引用复杂性，在您的情况下是 O(n)。