math - スカラーはbig-O表記で重要ですか?

Question

スカラーは big-O 表記に含まれていますか、それともスカラーが考慮されていないため、O(2n) は実際には O(n) と同じですか? もしそうなら、これはなぜですか？

Answer 1

Big-O 表記は、その定義により、定数係数 (スカラー) を無視します。

f(n) = O(g(n))ただし、任意の自然数 n > n ₀に対して |f(n)|となるような自然数 n ₀と実数 c が存在する場合。≤ |cg(n)|

ここで、f(n) = O(k × g(n)) とします。これは、任意の n > n ₀に対して |f(n)|となる自然数 n ₀と実数 cが存在することを意味します。≤ |c × k × g(n)|。

これを使用して、f(n) = O(g(n)) を示します。これを行うには、自然数として n ₀を選択し、実数として c × k を選択します。次に、任意の n > n _{0 に対して}、|f(n)| が得られます。≤ |(c × k) × g(n)| なので、f(n) = O(g(n))。

お役に立てれば！