O（1）とΘ（1）の違いは何ですか？

私は両方の定義を知っていますが、O（1）や他の時代のΘ（1）が教科書で書かれていることが時々あります。O（1）とΘ（1）の違いは何ですか？

ありがとうございました。

2013-09-07 BarakA

Big-O表記は漸近的な上限を表しますが、Big-Theta表記はさらに漸近的な下限を表します。多くの場合、上界は人々が興味を持っているものなので、たとえシータ（何か）も真実であっても、O（何か）を書いています。たとえば、ソートされていないリストでxと等しいものの数を数えたければ、線形時間で実行でき、O（n）であると言うかもしれません。なぜなら、あなたにとって重要なのは、それ以上の時間はかかりません。しかし、リスト内のすべての要素を調べなければならないので、それはオメガ（n）であり、従ってシータ（n）であることも真実であろう - それは非線形時間では実行できない。

出典

2013-09-07 20:28:18

定数について話すとき、それらの間に違いがありますか？また、O 1ではなく、Theta 1の要件が存在するケースがありますか？ – BarakA

下限が暗示されているので、一定の時間について話すときに区別がありません。しかし、ここで興味深い議論を参照してください：http://stackoverflow.com/questions/905551/are-there-any-o1-n-algorithms –

ありがとうお友達 – BarakA

O（1）とΘ（1）は、実数の関数について話している場合、必ずしも同じではありません。例えば、関数f（n）= 1/nを考える。 f（n）= Θ（g（n））の定義の1つで、が Θ（1）でないため、この関数はO（1）））は、| f（n）/ g（n）| nが無限大になると、0 < Lを満たす有限値Lが得られる。f（n）= 1/nとg（n）= 1を差し引くと、| 1/n | nが無限になると0になるので、f（n）≠Θ（1）となります。

希望すると便利です。

出典

2013-09-15 23:05:59 templatetypedef

O（1）とΘ（1）の違いは何ですか？

答えて

関連する問題