复杂性的情况下优异的，平均和坏

我创建在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; 
}

2013-02-11 Enzo

你问平均？因为你的好和最坏的情况对我来说似乎是正确的。 – 2013-02-11 14:38:26

平均情况取决于您输入的统计属性...也许您想补充一点，您希望假设输入的均匀分布情况下的平均情况？ – thang 2013-02-11 14:38:58

是的，在平均情况下？ – Enzo 2013-02-11 14:39:34

你没有告诉你输入任何东西。所以假设它是完全随机的。因此，对于任何2个邻居对，我们有50％的机会被订购。这意味着我们有1步的概率为1，2步为0.5，3步为0.25，k步的概率为2 ^（ - k）。让我们来计算步数预计：

enter image description here

我不知道如何计算这一系列的总和，所以我使用Wolfram Alpha的，并得到answer: 2，所以这是一个常数。

因此，正如我理解为随机输入平均情况是O（1）。

我不知道它是计算平均复杂正确的方法，但似乎没什么问题。

2013-02-11 14:53:42

你是不是指进行1次比较的概率1/2，进行2次比较的1/4等等？ – thang 2013-02-11 15:04:25

还有一个错字？在你的方程中......（1 /（2^-k））= 2^k。这件事会爆炸......这不是你在文中所描述的。 – thang 2013-02-11 15:05:32

@thang是的，我的意思是1/2 1 1/4 2等我会解决错字关于式，由于 – 2013-02-11 15:06:16

复杂性通常报价在最坏的情况下，你的情况是O（n）。

2013-02-11 14:37:05 Qwerky

是的，我知道，但我也知道在一般情况下！ – Enzo 2013-02-11 14:38:25

@Enzo如果你认为平均案例是相关的，那么你需要考虑你的投入，我们无法预测会发生什么。 – Qwerky 2013-02-11 14:41:38

@Qwerky在分析“平均情况”时，您通常使用随机输入进行计算，并计算成本的*期望值*（平均值） - 这会给您提供平均情况下的复杂度。例如，在这种情况下，应该用所有可能的排列来完成，给出1/n的每个置换概率！被选中。 – amit 2013-02-11 16:27:43

回答