ベストケース時間配列がソートされていないかどうかを確認する複雑さ

Question

私は、指定された配列がソートされていないかどうかをチェックしながら、最良のケース時間の複雑さを調べようとしています。

これは、配列がソートされているかソートされていないかどうかを調べる最速の方法であり、時間の複雑さはO（n）でなければならないと思います。

for (i = 0; i < a.length-1; i++) { 
    if (a[i] < a[i + 1]) { 
    return true; 
    } else { 
    return false; 
    } 
} 

または間違っていますか？

Answer 1

はいこれは、O(n)となり、それはas fast as it getsです。

---

また、あなたはこれを変更する必要があります。これに

for (i = 0; i < a.length; i++) 

：

for (i = 0; i < a.length - 1; i++) 

あなたがa[i + 1にアクセスし、あなたが範囲外に行きたくないので。さらに、返品明細書を交換する必要があります。