大きなシータを記述する正しい方法は何ですか？これらのコードについて

Question

：

CODE1：

arr[1] = 1; 
for(int i=1; i<=n; i++) 
    if(arr[i]==1) 
    break; 

コード2：

for(int i=1; i<=n; i++) 
    if(arr[i]==1) 
    break; 

CODE3：検索は、最初に必ず満足しているので、

for(int i=1; i<=n; i++) 
    for(int j=1; j<=i; j++) 
    //O(1) statement 

CODE1は、1の大きなシータを持っています繰り返し（一定時間）。

code2は1の大きなシータがあり、最悪の場合はnの大きなシータがありますが、「最悪の場合」の文章は「code2はnの大きなシータを持っています」とは言いません。またはそれに関連する複数のシナリオ（最高の場合、最悪の場合など）を持つコードの大きなシータを記述することは無効であり、特定のシナリオに関して大きなシータを記述する必要がありますか？

code3はn^2の大きなシータを持ち、その内側ループは1からnまでの範囲のiの大きなシータを持っています。実際の範囲でも内部ループはnの大きなシータを持っています1からnまで？

Answer 1

1）correct

2）最良のケースについて話すことはよくありません。多くのアルゴリズムであなたは幸運になるかもしれませんが、これがまれにしか起こらなければ、それは関係ありません。平均的なケースと最悪のケースについて話すほうが有用です。どちらもTheta（n）です。 3）O（1）文は約n * n/2回実行されるため、Theta（n * n）文は約n * n/2回実行されます。 ） 正しい。内側のループは平均n/2回実行されます。