big-o - 擬似コードを使用した O 表記

Question

for i=1 to n       | n+1
  for j=1 to i^3   | ???
     x=x+1         |

問題: ステートメント x=x+1 が実行される n 回の O 表記を見つけます。ここで 2 番目の for ループと混同しています。実行する最初のステートメント n+1 がありますが、最初の for ループの i=1 は 2 番目の for ループ ステートメント i^3 に影響しますか?

これに対する私の答えは O=n+1 です。

Answer 1

内側のループi^3が for i の場合 Bitwise Xor 3 (11)
O 表記はO(n^2)

内側のループi^3の がi の 3 乗の
場合、 O 表記は次のようになります。O(n^4)

この場合、内側の for ループが実行されます

(1^3) + (2^3) + (3^3) + ... + (n^3) times
= (n^2 * (n+1)^2) / 4 times
so O(n^4)

Answer 2

for i=1 to n

明らかにn反復があります。2 行目:

for j=1 to i^3

各反復実行i^3時間。各反復でiは 1 から まで 1 ずつ増加するためn、アルゴリズムの実行時間はすべての内部ループ反復の合計として表すことができます。

Sum_i=1_i=n(i^3)

合計は次のようになります。

(n^2 * (n + 1)^2) / 4

(これについては、 http://en.wikipedia.org/wiki/Summationおよびhttp://polysum.tripod.comを参照してください。)

だからあなたは持っています：

O((n^2 * (n + 1)^2) / 4)

上記を可能な限り単純化すると (0 以外の定数による乗算または除算、または定数による加算は big-oh 表記法では無視されることに注意してください)、答えが得られます。

O(n^4)