0

みんな、宿題について最後の質問があります..問題は次のように尋ねます。

Reorder the following efficiencies from smallest to largest:
2^n
n!
n^5
10,000
nlog(n)

繰り返します..これに直接答えないでください。

私の質問:

1.) 最小から最大へとはどういう意味ですか? 最も効率的でないものから最も効率的なものへ?

2.) 10,000 が一定であることを考えると、これが最も効率的で、nlog(n)、n!、効率的な n^5、最後に 2^n と続くと思います。これは正しいでしょうか？

4

6 に答える 6

3

n!、n^5、2^n の場合、n+1 でどのように増加するかを考えます。つまり、(n+1)! を比較します。n! に、(n+1)^5 から n^5 に、2^(n+1) から 2^n に。

最初の質問については、あなたが最も理にかなっていると思うように解釈し、教授があなたの意味を理解できるように、それがあなたがそれらをどのように順序付けているかを明示的に述べてください（ほとんどの人にとって最も効率的ではない、またはその逆）.

于 2013-01-23T17:34:52.137 に答える
2

f(n) = O(g(n))これは、一定で十分に大きい|f(n)|場合、常に以下であることを意味します。これは、無限大になるまで関数値を比較していることを意味します。c * |g(n)|cnn

たとえば、100 * nは小さい場合よりもn²小さいnですが、それn = 100以降n²は常に以上である100 nため、「大きい」と見なされます。

それは逆には機能しません-定数をどれだけ大きく選択しても、すべてのに対してc常にいくつかあるn0ようになりますn > n0 n² > c * 100 * n。たとえば、を選択した場合c = 1,000,000 n²でも、それ以降はそれ以上c * 100 * nですn = 100,000,000。

于 2013-01-23T17:34:32.693 に答える
1

可能であれば、それらをプロットしてみてください。グラフがどのように見えるかを確認し、n の代わりに x を使用してそれらを比較します。

于 2013-01-23T19:25:54.643 に答える
0
  1. 私は逆に行きます-最も効率的なものから最も効率的でないものへと並べ替えますが、ジョニーがコメントしたように-教授に尋ねてください:)
  2. 最初の 2 つは正しいです。
于 2013-01-23T17:29:47.410 に答える
0

最小から最大 とはどういう意味ですか? 最も効率的でないものから最も効率的なものへ?

おそらく、最も効率が良いものから最も効率が悪いものまで、O(1) -> O(n) -> O(n 2 ) の順です。

10,000 が一定であることを考えると、これが最も効率的で、nlog(n)、n!、効率的な n^5、最後に 2^n と続くと思います。これは正しいでしょうか？

ここでヒントだけ。これらのそれぞれに n のいくつかの値を代入し、どれが最も速く成長するかを確認します。10 の最初の 7 乗または 8 乗など、かなり広い範囲の値を使用するようにしてください。

于 2013-01-23T17:30:08.607 に答える
0

この宿題は、大きな入力に置き換えて比較するだけです。あなたが学ぶために..ビッグオー、オメガ表記、シータΘがあります。

Big O は、この宿題のために取得する必要があるものです。これは、関数が決して超えない上限であるためです。..大きな値です。

オメガΩは下限であり、関数が小さな値に対して決して下回らないものです。たとえば、1,000,000。

シータ Θ はその中間です。

しかし、実生活では、私はいつも大きなO表記にしか直面していませんでした。

let n = 1000    
2^n =~ 1e30  
n!  =~ too BIG!  
n^5 =~ 1e15  
10,000 =~ 10000  
nlog(n) 3000

ある程度の感覚で、今すぐ正しい順序を見つけることができます。

于 2013-01-23T18:18:35.190 に答える