n が非常に大きく、k が非常に小さい場合、O(kn) は線形複雑度であると言えますか?
k が n/2 に近いが、n/2 を超えない場合はどうなるでしょうか? それでも線形複雑性と見なしますか? または二次複雑さ O(n^2)?
O(kn) を 2 次複雑度と見なすために、k の大きさに制限はありますか?
4757 次
2 に答える
15
が定数の場合k、任意の O(kn) 関数は O(n)、つまり線形です。
kが O(n)の関数である場合n、任意の O(kn) 関数は O(n^2) です。n/2 は O(n) です。さらに、(n^2)/2はO(n) ではないため、 が次にk近い場合はO(n) ではありません。n/2kn
kが O(n) でない場合は、 knO(n^2) ではありません。
于 2012-10-31T15:30:55.270 に答える
0
k と n が独立変数であると仮定すると、O(kn) が線形であると言うのは適切なステートメントです。
于 2012-10-31T15:31:16.560 に答える