78

これはデータ構造の私の最初のコースであり、すべての講義/ TA講義について、私たちは話しO(log(n))ます。これはおそらくばかげた質問ですが、誰かが私にそれが何を意味するのかを正確に説明してくれれば幸いです！？

4

6 に答える 6

105

これは、問題の物（通常は実行時間）が、入力サイズの対数と一致する方法でスケーリングされることを意味します。

Big-O表記は、正確な方程式を意味するのではなく、境界を意味します。たとえば、次の関数の出力はすべてO（n）です。

f(x) = 3x
g(x) = 0.5x
m(x) = x + 5

xを増やすと、それらの出力はすべて線形に増加するためです。との間に6：1の比率がある場合、f(n)との間にg(n)約6：1の比率もあります。f(10*n)g(10*n)

良いかどうかについてO(n)は、次O(log n)のことを考慮してください。if n = 1000、then log n = 3（log-base-10の場合）。アルゴリズムを実行するのに、1000秒と3秒のどちらを使用しますか？

于 2012-04-29T04:01:45.820 に答える
38

簡単に言えば、O（log n）はO（n）よりも優れています

さて、O（log n）とは正確には何ですか？

一般に、ビッグO表記を参照する場合、log nは2を底とする対数を指します（同様に、lnは2を底とする対数を表します）。この2を底とする対数は、指数関数の逆関数です。指数関数は非常に急速に成長し、その逆関数は正反対のことを行う、つまり非常にゆっくりと成長することを直感的に推測できます。

例えば

x = O（log n）

nを次のように表すことができます。

n = 2 x

と

2 10 = 1024→lg（1024）= 10

2 20 = 1,048,576→lg（1048576）= 20

2 30 = 1,073,741,824→lg（1073741824）= 30

nの大きな増分は、log（n）のごくわずかな増加につながるだけです。

一方、O（n）の複雑さについては、線形関係が得られます。

log 2 nの因数は、いつでもnの因数を引き継ぐ必要があります。

これをさらに固めるために、私はトーマス・コルメンによってロック解除されたアルゴリズムの例に出くわしました

2台のコンピューターを考えてみましょう：AとB

両方のコンピューターには、配列で値を検索するタスクがあります。配列に検索対象の要素が1,000万個あると仮定します。

コンピューターA-このコンピューターは1秒あたり10億の命令を実行でき、O（n）の複雑さのアルゴリズムを使用して上記のタスクを実行することが期待されています。このコンピューターがタスクを完了するのにかかる時間は、次のように概算できます。

n /（命令p秒）→10 7/10 ^ 9 =0.01秒

コンピューターB-このコンピューターははるかに低速で、1秒あたり1,000万命令しか実行できません。コンピューターBは、O（log n）の複雑さのアルゴリズムを使用して上記のタスクを実行することが期待されています。このコンピューターがタスクを完了するのにかかる時間は、次のように概算できます。

log（n）/（命令p秒）→log（10 7）/ 10 7 = 0.000002325349

この図を使用すると、コンピューターAはコンピューターBよりもはるかに優れていますが、Bが使用するアルゴリズムにより、タスクをはるかに迅速に完了することがわかります。

O（log（n））がO（n）よりもはるかに速い理由は今や非常に明確になるはずです。

于 2019-02-11T10:58:06.630 に答える
21

サイズの入力の場合n、のアルゴリズムはO(n)に比例したステップを実行しますがn、の別のアルゴリズムはO(log(n))大まかにステップを実行しますlog(n)。

明らかlog(n)に小さいnので、複雑さのアルゴリズムO(log(n))が優れています。それははるかに高速になるので。

于 2012-04-29T04:08:56.867 に答える
7

O（logn）は、アルゴリズムの最大実行時間が入力サイズの対数に比例することを意味します。O（n）は、アルゴリズムの最大実行時間が入力サイズに比例することを意味します。

基本的に、O（何か）はアルゴリズムの命令数（アトミック命令）の上限です。したがって、O（logn）はO（n）よりもタイトであり、アルゴリズム分析の観点からも優れています。しかし、O（logn）であるすべてのアルゴリズムもO（n）ですが、逆方向ではありません...

于 2012-04-29T04:08:55.723 に答える
5

http://en.wikipedia.org/wiki/Big_oh

O（log n）の方が優れています。

于 2012-04-29T04:04:28.587 に答える
3

正式な定義：

g（x）= O（f（x））<=> x0と定数Cがあり、すべてのx> x0に対して、| g（x）| <= C | f（x）|。

したがって、問題PのアルゴリズムAがその複雑さO（f（n））であることがわかった場合、アルゴリズムが実行するステップ数は、通常nが入力サイズ。（nは何でもかまいません）

詳細については、http：//en.wikipedia.org/wiki/Big_O_notationをご覧ください。

于 2012-07-05T15:13:24.887 に答える