負の符号は、関数が時間的に複雑であることを示していますか？

時間複雑度n-lognを持つ関数を考えてみましょう。それで、ここで何を示す否定的な印が負の符号は、関数が時間的に複雑であることを示していますか？

その複雑さには-lognが含まれ、それはnより小さくなるか、またはlogn操作としてより多く含まれ、それは> nですか？

2017-04-05 K D

n-log（n）はおそらくn * ln（n）ですが、ひどく書かれています – Gar

この表記に遭遇したときのコンテキストを教えてください。 –

アルゴリズムの時間複雑さは、入力の長さ/サイズの関数としてアルゴリズムを実行するのに要する時間を定量化します。例えば

：未分類リストの

時々、これらの境界は上向きです。そして、そのような場合、人々は切り上げる傾向があります。このアルゴリズムは、nが十分大きな値のnに対して2nを支配するので、O（n2-2n + 1）回の演算を必要とします。

あなたの場合、記述されているアルゴリズムは複雑さO（n-log（n））を持っています。入力値nに対して非負の出力を生成する任意の数学関数を使用できます。 -log（n）を使用しても問題ありません。

2017-04-05 11:35:54

n-lognの場合、負の符号を解釈する方法操作はnより大きい場合もあるし、より小さい場合もある –

これを「log（n）とn（n）の間」ではなく「n minus log（n）」と解釈する。なぜなら、log（n）は通常nよりもずっと小さいからです。「log（n）とnの間」で指定された範囲は、実際のnの値に対して使用するには大きすぎます。 –

もし私が間違っていたら、2つのalgosがn + lognとしてもう1つのn-lognが起こることができれば、より多くの操作と何サインが複雑になるかを正確にしてください。 –

答えて