あなたは（n lg n）がO（n^2）だと言うことができますか？

O(n lg n)とO(n^2)の場合、nが十分に高い場合は、(n lg n)が小さくなることがわかります。あなたは（n lg n）がO（n^2）だと言うことができますか？

O(n^2)は(n lg n)の正しい評価になりますか？

O(n lg n)とO(n^2)に大きな違いは、私はO(n^2)が(n lg n)の『最悪の場合』のタイトルの質問（もともとだった答える

2016-09-20 Jules Mena

「O」を使うときに人々が異なることを意味するので、質問は実際にはうまく形成されません。正式な大きなthethaを意味します。また、大きなO表記の意味での「等しい」という意味を定義することは、あまり一般的ではありません。どの定義を使用するかを定義する必要があります。ここでは、良い読書です：http://stackoverflow.com/questions/471199/what-is-the-difference-between-%CE%98n-and-on – luk32

[私の質問に誰かが答えるときに私はどうすればよいですか？] – xenteros

に最良の答えになることはよく分からないがあります：あなたはでしたそのnlgnはO（N^2）に等しいと言う）：？nlgnとして

いいえ、あなたはできませんが機能とO(n^2)ががを設定されています。身体からあなたの質問に答える

は：

まあ、はい、nlognはO(n^2)です...しかしO(n^n)で試験でそれぞれの質問に答えることをしようとしないでください。彼らが求めるものではありません。 Big-O記法は、最良の答えを与えるためには使用されません。それはちょっとした情報を与える単なる方法です。 ウィキペディアによれば

：

ランダウの記号は、引数が特定の値または無限大に向かう傾向がある機能の制限動作について説明した数学的表記です。それは、Paul Bachmann、Edmund Landau、および他者によって発明された表記法のファミリーのメンバーであり、まとめてBachmann-Landau表記または漸近表記と呼ばれています。

出典

2016-09-20 12:52:02 xenteros

素晴らしいです、説明をありがとうございます。私は今から "is"を使用します。 –

私はウィキからもう1つの文章について言及したいと思います。*「非公式に、特にコンピュータサイエンスでBig O表記は、Big ThetaΘを使用する場合、漸近的な緊密な境界を記述するために、表記法は事実上適切なものであるかもしれません。[要出典] "* – luk32

xentrosの回答が良いです。あなたの質問に答えるもう一つの方法は、Big-Oh漸近線が要求されたとき、通常、あなたが見つけることができる上限を厳密に与えることが求められるということです。

したがって、ng n = 0（n^2）（=記号は表記の乱用ですが、一般的な悪用です）。 ng n = O（n lg n）と言うのは正しいものであり、より制限的な上限であるという意味ではより良いでしょう。

同様に、下限を見つけたときの優先度は、見つけられるほどの下限です。本当に幸せなケースは、上限が十分に低く、下限が十分に高く、Theta境界を見つけることができるときです。

出典

2016-09-20 12:59:37 Patrick87

@Vatineこれはどのようにして質問に答えませんか？私は "ng n = O（n^2）である"という質問を読んだ。答えは「はい、でもそれはO（ng n）であり、それはより良い答えです」。 – Patrick87

正直なところ、なぜ私はそれを選んだのか分かりません。私はそれを見ていて、それを見たときに答えのように見えてはならないにちがいありませんでしたが、今はそうです。あなたの答えを少しはっきりさせることができるかどうかを見てみましょう。 – Vatine

あなたは（n lg n）がO（n^2）だと言うことができますか？

答えて

関連する問題