複雜性的情況下優異的，平均和壞

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）。

我不知道它是計算平均複雜正確的方法，但似乎沒什麼問題。

Answer 2

複雜性通常報價在最壞的情況下，你的情況是O（n）。