

O（k*N^2）kがNと同じと考えられる場合O(N^3)のようにまとめることは出来ますか？  
例えばNxNの行列とN次元ベクトルの掛け算の場合O（N^2）となりますが  
N回行った場合O(N^3)のようにまとめてもいいのですか？


CC BY-SA 3.0
2015-02-21T19:18:34.243
6888
2015-02-21T23:16:32.850
2015-02-21T23:16:32.850
question
計算量
O（k*N^2）kがNと同じと考えられる場合


k=cN+e(N) (cは定数、e(x)はxの1次未満の項からなる式、例えばlog(N)とか)
と表せる関係があるなら、もちろんO(k*N^2)はO(N^3)です。


CC BY-SA 3.0
2015-02-21T19:41:45.163
6889
2015-02-21T19:41:45.163
5258
6888
answer