2 ^（n + a）がO（2 ^ n）であることをどのように証明できますか？私が考えることができる唯一のことは、2 ^ nのnは任意の値であり、したがってn + aも同様に任意であるため、n + a=nです。または、2 ^（n + a）= 2 ^ n * 2^a。2 ^ nは明らかにO（2 ^ n）であり、aは2 ^ aに任意の値として存在するため、2 ^ a = 2 ^ n = O（2 ^ n）です。これを証明するためのより明確で正式な方法はありますか？
質問する
130 次
3 に答える
3
big-O の正式な定義では、すべての n > n0 に対して 2^(n+a) <= M*2^n となるような M と n0 が存在する必要があります。
M = 2^a および n0 = 0 を選択すると、2^(n+a) = 2^a * 2^n = M*2^n、つまり <= M*2^n であることがわかります。すべての n > n0 に対して。したがって、2^(n+a) は O(2^n) です。
于 2012-11-16T19:29:15.063 に答える
1
ここでbig-O表記の定義を参照してください。M定義のように定数を見つけることができるかどうかを考えてください。
于 2012-11-16T19:28:29.950 に答える
0
一般に、 が であることを証明するにf(n)は、すべての に対して となるようなO(g(n))正の整数を見つけなければなりません。Nn >= Nf(n) <= g(n)
于 2012-11-16T19:29:02.800 に答える