Java Big O Notationアルゴリズム

誰でもBig Oを見つけるのを手伝ってくれたら、それを私に説明してください。Java Big O Notationアルゴリズム

j = 1; 
    while (j <= n) 
    { 
     j = j + 2 
    }

ループがどのように機能するかを確認するためにランダムなn個を選択することがわかりました。しかし、私はクラスメートがいて、while（j < = n）はn/2回実行されますが、その答えにどのようになったのか分かりません。

2017-02-28 Anonymous

n = 10、n = 20で試してみてください。パターンが明確になるはずです。 – Thilo

あなたのループは単純に 'n/2'回実行されますが、' O（n/2） 'が正解であることを意味するものではありません。 –

さて、私は今それを見る。ありがとうございました。パターンを見つけるためにn = 7を使っていました。あなたはパターンを見つけるために数字を選ぶ方法に関するアドバイスを持っていますか？ –

アルゴリズムの漸近的複雑さを見つける必要がある場合は、常に最も高い成長順位を探します。

成長の順序は、アルゴリズムの最大多項式（P問題の場合、NP問題は異なる方法で処理されます）です。この順序は複雑さを定義します。

aループがあります。これは線形ループです。 Linearは1度のパワー/次数を意味します whileループで実行されているステートメントを見ると、次のように計算できます。

j = j + 2を実行する時間。 =回ループの実行のC
なし=任意の整数N

したがって、総コストは1
度の多項式であるC * N
しないため複雑さはO（N）

。注：ループがn/2回実行されるのは本当です。これは、1から3,5,7などのすべての反復でjを2ずつ増やしているからです。
アドバイスは、複雑さを見つけるために数字を選んではいけません。上記のコスト*反復法を使用してください。

2017-02-28 00:38:15 Araphel

'ループ回数=任意の整数Nです。これが線形であることを決定するためにループ条件を見るだけでは、反復の回数を把握する必要があります。この場合はですが、 'j = j * 2'を実行した場合、それは線形になります。 – Thilo

私はコードが線形時間で実行されると言っています。 j = j * 2の場合でも、コードはn回だけ実行されます。 – Araphel

'j = j * 2'の場合、O（log n）回の反復しかありません。 – Thilo

あなたのクラスメートはです。ほぼです。whileループはn/2回実行されますが、それほどではありません。 whileループ内のカウンタをインクリメントしてから、n = 0〜9で印刷してみてください。正解はn/2 +（モジュロを含むもの）です。

Big Oは実際の実行回数ではなく、可能な限り最大での実行回数の上限がであり、定数と低次の項は無視されます。したがって、 "/ 2 +（モジュロを含むもの）"は無視できます。

2017-02-28 00:59:32 runcoderun

答えて