1

Big-O記法について読みました。私はいくつかのアイデアを理解しましたが、2つのアルゴリズムを比較すると、彼が言う既存の2つのアルゴリズムに続くものを理解できませんでした。

 First f2(n) = 2n + 20 steps. 
second f3(n) = n + 1 steps.
he write f2 = O(f3):

    f2(n)/f3(n)
    =((2n + 20)/(n + 1))<= 20;
   he say Certainly f3 is better than f2?, of course f3 = O(f2), this time with c = 1.

要素が少ないので、f3はf2よりも優れていると思います。私の質問

1) 定数 c= 1 なぜ彼はそれを選ぶのか? 2) なぜ f3 = O(f2) で、なぜ f2 = O(f3) なのか?

4

2 に答える 2

1

これらは両方とも線形関数であるため、両方ともであり、互いにO(n)両方です。は、漸近的に よりも 20 倍高速です。これらすべてのことは同時に真実です。Of3f2

于 2013-02-13T22:34:06.223 に答える
0

Patrick87の回答は、Big-O表記の漸近的性質についてもう少し説明しています。これについてもう少し分析してみましょう。もう少し詳しく調べf2てみましょう。f3

まず、f2(n)：私たちはそれを知っていf2(n) = O(2n + 20)ます。20は定数なので、無視してかまいません。だから、f2(n) = O(2n + 20) = O(2n)。繰り返しますが、2は定数なので、無視することもできますf2(n) = O(2n + 20) = O(2n) = O(n)。

この分析が意味することは、n増加するにつれて、ある関数はである関数と2n + 20同じくらい速く成長し、それはである関数と2n同じくらい速く成長するということですn。あなたがそれについて考えるならば、これは理にかなっています：これらの関数はすべて平行線です。それらの成長率は同じです。

今f3(n)：私たちはそれを知っていf3(n) = O(n + 1)ます。1は定数なので、無視してかまいません。だから、f3(n) = O(n)。

そしてそれが理由f3でありf2、両方O(n)です。これは、これらの関数が特定の値に対してまったく同じ時間nを要すること、またはクロック時間f2と同じくらい速いことを意味するものではありません。f3これは、両方の機能の複雑さ（つまり、作業にかかる時間）が増加するのと同じ割合でn増加することを意味します。

于 2013-02-13T22:45:09.847 に答える