0

アルゴリズムの学習を始めたばかりです。したがって、演習では、ステートメントが常に/場合によってはtrueまたはfalseであるかどうかを確認します。エム、私の論理はここでどこで失敗しますか？

f(n) != O(g(n)) and g(n) != O(f(n))

O表記は、定数が0 <= f(n) <= cg(n)どこにあるかです。cしたがって、ここで等しくないということは、次のことを意味します。

f(n) > cg(n) and g(n) > cf(n)

の場合f(n) = g(n) = 1、そして言いましょうc = 1/2：

1 > (1/2)*1 and 1 > (1/2)*1

したがって、この場合は真実です。しかし、この本は、この特定のケースではそれが誤りであると述べています。私はどの部分を誤解していますか？

4

1 に答える 1

2

Big-Oは、それ自体が一定で0 <= f(n) <= c g(n)はありません。nの「十分に大きい」値に対して関係が成り立つような数cが存在するということです。（これは、Big-Oを漸近表記と呼ぶときに参照する「漸近」であり、他の一般的な表記はBig-ThetaとBig-Omegaです。）

たとえば、n要素を含むデータ構造を操作し、3n^2 + 7n + 18手順を実行するアルゴリズムがあるとします。これを呼び出しますf(n)。この式のBig-Oは、、のすべての「十分に大きい」値に対してO(n^2)定数（この場合は3より大きいもの）が存在するためであると言います。nf(n) <= c n^2

于 2012-06-21T02:56:14.253 に答える