0

1）次の効率を最小から最大に並べ替えます。 2^n, n!, n^5, 10000, nlog2(n)

私の答え->10000<nlog2（n）<n ^ 5 <2 ^ n <n！

正しい ？

2）アルゴの効率。このアルゴリズムのステップの場合、n^3です。1ナノ秒かかります。（10 ^ -9秒）。アルゴにはどれくらい時間がかかりますか。サイズ1000の入力を処理するには？

わからない…（1000）^ 3 * 10 ^ -9？

4

3 に答える 3

2

質問1は大丈夫です。質問2、あなたの答えは彼らが探しているものだと思いますが、n ^ 3がO（n ^ 3）を意味する場合、実際には答えることができません（これが「アルゴリズム効率」の使用でない限り）Iなじみがない）。

Big-Oの複雑さは、アルゴリズムの動作に漸近的な限界を与えます。「大きい」nの場合、O（n ^ 3）は、サイズnの入力でアルゴリズムを実行するのにかかる時間よりも大きいことがわかります。「大きいn」と「漸近境界」の2つの警告に注意してください。すべてのn>mについて、n ^ 3が実行時間を制限するようなmが存在する限り、サイズ1000の入力がサイズ2000の入力の2倍の時間がかかるのを止めることはできません。また、n ^ 3はまだランタイムに制限されているため、すべての入力で1ナノ秒かかるアルゴリズムを停止することはできません。これは非常に悲観的です。

これが、実際の状況では大きなO表記が限られた用途であることが多い理由です。これは、公正な「最悪のケース」の概要を示していますが、特定の使用シナリオについては説明していません。より実用的に役立つ（しかし見過ごされがちな）複雑さのクラスセットについては、「Bigtheta」をグーグルで検索してください。

于 2009-07-27T14:58:11.153 に答える
1

両方の答えは正しいです

于 2009-07-27T14:46:00.347 に答える
1

1）はい、その通りです。

2）それも正しいです。次元分析：（1000 ^ 3ステップ）* 10 ^（-9）秒/ステップ

于 2009-07-27T14:46:19.003 に答える