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