バブルは1 000 000の整数の配列でどのくらい時間がかかりますか？

バブルソートには計算複雑性O（n^2）があります。例えばCPU 3.5 GHzの場合、これらの計算は正しいですか？ 1 000 000 * 1 000 000 = 10^12 3.5 GHz〜マイク1本あたり6 000 000（これが真でない場合は、私に修正してください）バブルは1 000 000の整数の配列でどのくらい時間がかかりますか？

（10^12/6 * 10^6 ）/ 60 =〜2777時間これは本当ですか？

出典

2017-11-16 xodos

そうかもしれないし、そうでないかもしれない。それは、あなたが600万人のどこから得られたか、入力データの仕方、誰がMikeなのかなどによって決まります。 –

これは、使用されるプログラミング言語、システム全体の読み込み、短い、長い、または長いlong intなどにも依存します。 – roelofs

'mはC++、4バイトint、データはrand（）からのもので、プロセッサが何回計算を行うのか不思議です。私は別のトピックでこの値を見つけました。 – xodos

あなたはBigO表記を誤解していると思います。

理論情報学では、BigOを使用して上限と下限を表現するので、値をプラグインして時間を見つけるだけではありません。あなたはBigO表記法O（10N）= O（N）でわかりません。

例えば、quicksortの複雑さを見ると、〜1.39NlogNであり、BigOではO（NlogN）です。

BigOまたはティルダの表記は、ミリ秒とは関係ありません。しかし、時間を知る唯一の方法は比率テストを使うことです。

BigOは比較回数を表します。

出典

2017-11-16 12:13:03

バブルは1 000 000の整数の配列でどのくらい時間がかかりますか？

答えて

関連する問題