問題タブ [little-o]

f(n) と g(n) という 2 つの関数があるとします。f(n) が小さいか o(g(n)) かどうかを確認したい場合は、次のようにします。

上記が 0 になった場合、f(n) は o(g(n)) ということになりますか? そして、制限付きの大きなシータと小さなオメガをどのように確認できますか?

試験の復習のために次の 3 つの質問があります。

1. f(n) = 2n - 32つの異なる関数g(n)を与える場合h(n)（そうg(n)ではないh(n)）そのようなものf(n) = O(g(n))とf(n) = O(h(n))
2. g'(n)関数とで同じことをもう一度行いますh'(n)が、今回は関数は と の形式である必要があります g'(n) = Ɵ(f(n))。f(n) = o(h'(n))
3. 関数f(n) = O(g(n))とは可能f(n) = Ω(g(n))ですか？

O(n)関数が他の関数よりも小さいか等しい場合、その関数は別の関数であることを知っています。だから私は 1.g(n) = 2n²-3とh(n) = 2n²-10.

Ɵ(n)また、関数が基本的に他の関数と等しい場合（定数は無視できます）、関数が別の関数であることも知っています。また、関数よりも小さい場合は、2. と を持つことができるとo(n)思います。g'(n) = 2n-15h'(n) = 2n

3. へ: 関数が と の両方である可能性があるのは、関数が指定された関数と同じであることを許可するため、 と の両方O(n)であるという規則に等しく、それを満たす関数を持つことができるからです。Ω(n)O(n)Ω(n)g(n)f(n)OΩ

これが正しいかどうか誰か教えてください。

私の同僚が私に質問をしてきました: セットo(1)(小さな o 記法) は空ですか?

私の質問は:o(1)空集合ですか? o(1)そうでない場合、時間の複雑さを持つプログラムはありますか?

リマインダー、 Cormenによる little-o の定義:

任意の正の定数に対して、すべてに対して という定数が存在する場合、その関数は存在するとf(n)言われます。o(g(n))c>0n0 > 00 <=f(n) < cg(n)n>= n0

直観的に、if it is in ですf(n)が、この境界は厳密ではありません。o(g(n))O(g(n))

Big-O と little-o の違いは理解できますが、特定の状況 (およびその逆) で Big-O よりも little-o を選択するのはいつ、なぜなのか疑問に思います。