2

アルゴリズムの時間複雑度の表現方法を決定する方法は?

またはで時間の複雑さを表現することを選択する必要がありますO(n)かtheta(n)? 関数はまたはf(n)として表現できるためです。Big-Oh(g(n))theta (g(n))

theta よりも big-oh を選択するのはいつですか?

4

1 に答える 1

5

下限も指定する場合は、Big Theta 表記を使用します。f(n) = O(g(n))はfによって上に境界があると言いますがg、上と下の両方に によって境界があると言います。f(n) = Theta(g(n))fg

つまり、定数などがありk1ますk2。k1 * |g(n)| <= |f(n)| <= k2 * |g(n)|

于 2011-03-19T23:46:37.030 に答える