0

私の教科書では、バイナリ ツリーでノードを見つけるためのビッグ O 表記法は O(log 2 N) であると言っていますがN = 1、log 2 N が 0 になる場合、これは不可能でしょうか? これは切り上げられるだけ1ですか、それとももっとありますか?

4

5 に答える 5

5

NBig-O 表記法は、データの量 (または説明するもの) が無限に向かって増加したときに、アルゴリズムの実行時間 (またはメモリ消費など) がどのようにスケーリングするかを説明することを目的としています。の特定の値が与えられたときに正確なランタイムを提供することを意図したものではありませんN。の値が小さい場合、Nいずれにせよ定数因子が優位になる傾向があります。この場合、導き出そうとしているのは、この特定のアルゴリズムの実行時間が対数的にスケーリングされるということだけです。

于 2013-08-03T01:35:25.033 に答える
4

O 表記は、N が ∞ になるときの制限動作のみを考慮します。正式には、次のような定数 C と別の定数 N がある場合、非負関数 f はクラス O(g(n)) に属します。

n ≥ N ⇒ f(n) ≤ C g(n).

n の定数係数と小さな値はまったく問題になりません。

于 2013-08-03T01:35:53.307 に答える
1

Oまず、ノードのバイナリ ツリーでNノードを見つけることが重要であるというステートメントO(log N)は誤りです。このステートメントは、二分探索木には当てはまりますが、一般的な二分木には当てはまりません。

N = 1 の場合、log N は 0 になりますが、これは不可能ですか? これは1に切り上げられるだけですか、それとももっとありますか?

関係ない。それfが大きいO(log n)ということは、定数があるというCことNです。

n >= N implies f(n) <= C * g(n)

つまり、最終的に fは によって制限されC * gます。したがって、 を含む有限数の値を満たすことが不可能であるかどうかは問題ではありませんn = 0。つまり、すべての動作ではなく、漸近的Oな動作を説明することです。

于 2013-08-03T01:38:15.803 に答える
1

Big O は漸近的な複雑さです。実際の実行時間は log 2 N + C のようなものなのでN = 1、実行時間はC

于 2013-08-03T01:34:54.163 に答える