big-o - 正の定数を持つBig-O

Question

このBig-O/計算の複雑さの問題では、aとbが1より大きい正の定数であり、nが可変パラメーターであると仮定します。

^{a n + 1} = O（a ⁿ）、a ^bn = O（a ⁿ）＆a ^{n + b} = O（a ⁿ） と仮定しました

まず、これを想定するのが正しいかどうかを知る必要があります。

もしそうなら、f（n）= O（f（n））であることをどのように証明しますか。

Answer 1

big-Oの定義を思い出してください。

f（n）∈O（g（n））は、正の定数cとkがあり、すべてのn≥kに対して0≤f（n）≤cg（n）であることを意味します。cとkの値は、関数fに対して固定する必要があり、nに依存してはなりません。

g = f、c = 1、k = 0とすると、f（n）∈O（f（n））の簡単なデモンストレーションがあります。

同様に、^{n + 1} =a⋅anから、f（n）= a ^{n + 1}、g（n）= a ⁿ、c = a、k = 0とし、ここでもO（a ^{n + 1}）= O（a ⁿ）は自明です。^{O（a n + b}）= O（a ⁿ ）の証明は同じです。
O（a ^bn ）はa、b> 1のO（a ⁿ ）と等しくありません。big -o表記の指数関数的成長を参照してください。