1. ホーム
  2. 質問と答え
  3. コードフラグメントの複雑さ

コードフラグメントの複雑さ

2011-07-19 15 views
1 
for(int i = 0; i < N; i++) 
    if(i < 2 || i > N - 3) 
    for(int j = 1; j <= 10N; j++) 
     a[i] = a[j - 1]/2;

したがって、答えはN(1 + 10N(1)) = n + 10n^2でしょうか？それともnですか？ 説明してください。コードフラグメントの複雑さ

出典

2011-07-19 Evgeny C

答えて

2

漸近的な上限... O（n^2）が必要な場合。それよりもピカピカしたい場合は、個々の命令の計算ウェイトを定義する必要があります。

編集：はい、それはO（n）です。私は初めて間違って読む。

出典

2011-07-19 18:31:07 Patrick87

+0

本当にですか？ 3つの回答のうち、間違ったものを選んで受け入れましたか？グンボと一緒にいたのは、正しいことと理由を説明するためでした。 – PengOne

+0

ああ。ええ、最初は完全に "2 Patrick87

4

これは私にとってO(N)と思われます。

i = 0,1,N-1,N-2については、ifステートメントはtrueです。一定のケースです。

出典

2011-07-19 18:33:32 PengOne

+0

^正解 – tskuzzy

4

あなたの結論は間違っています。 N回ループfor外側が、if条件は、4例（0、1、N -2、N -1）でのみ真です。そのため、実行時間の合計はむしろN + 4・10・NO（ n）です。

出典

2011-07-19 18:34:08 Gumbo

関連する問題

 関連する問題