ビッグ・シータ・ノーテーションのワースト・ケース・ランタイム

Question

ビッグ・シータ・ノーテーションの最悪の場合の実行時間は、以下のコードでどのくらいですか？コードは、最低スコアを落とした後の宿題のリストから宿題の平均を計算します。

m := 1 
for i := 2 to n 
    if h_i < h_m then m := i 
total := 0 
for j := 1 to n 
    if j != m then total := total + h_j 
return total/(n − 1) 

最悪の場合、これは最も低いスコアが最後の位置にあることを意味します。これは、最初のループでは、n-1回の反復を実行することを意味します。最初のループの上限と下限はそれぞれO（n）とΩ（n）です。これは、実行時間がΘ（n）であることを意味します。

2番目のループは、n回の繰り返しを除いて、ほとんど同じことです。

私はbig-O表記と同じようにmax（Θ（n）、Θ（n））=Θ（n）

m := 1 ; total = h_1 
for i := 2 to n 
    if h_i < h_m then m := i 
    total = total + h_i 
total = total - h_m 
return total/(n − 1) 

このコードはまた、N-1回の反復を実行します - ：？おそらく私だけONEループ上で実行するコードの上に修正するので、（O（1））= O（n）の

私はこの質問をしました=>Θ（n）。これは2番目のコードより長いランタイムを持っていることは明らかです。 ）、Θ（g（n））。

Answer 1

big-O/θの表記で実行時間が分かるという一般的な誤りにはまっています。それは実行時間がnの関数として（漸近的に）どのようにスケールされるかを示します。アルゴリズム1がnで直線的に増加し、アルゴリズム2がアルゴリズム1として実行するのに2倍の時間を要する場合、アルゴリズム2は依然として線形成長もします。そのため、big-O/θのスケーリング定数は無視されます。

Answer 2

あなたが常に完全なリストを通過することを意味する反復の終了前には戻りません

Answer 3

big-O表記と同じですが、定数は削除されます。ランタイム全体はΘ(2n) = Θ(n)です。

また、2つのループを持つと、実行時間が長くなることはありません。これは、ループの長さが短くなるか、反復回数が少なくなるためです。 2番目のプログラムは反復ごとに多くの処理を行い、合計実行時間はほぼ同じになります。