-3

O() の定義のみを使用しますか?

4

2 に答える 2

1

あなたは矛盾によって証明する必要があります。それがであると仮定しn^2 ます O(n*log(n))。c これは、定義上、次のような有限で非可変の実数があることを意味します。

n^2 <= c * n * log(n)

ある有限数よりも大きいnごとにn0。

次に、の時点に到達し、それc >= n /log(n)をとして導出します。これは明らかに不可能です。n -> INFc >= INF

そして、あなたはそうではないと結論しますn^2 O(n*log(n))

于 2013-02-04T09:06:16.303 に答える