algorithm - コンピューターでの指数関数的ランタイムの影響は何ですか?

Question

指数関数的なランタイムを持つアルゴリズムを含むプログラムを作成し、そのプログラムを何年も終了しない十分に大きなデータセットで実行したとしましょう。

コンピューターはどうなりますか？ロックアップしますか？終了するか、電源が切れるまで、100% の容量で動作しますか? ハードウェアは、完了する前に故障しますか?

まだ推測していない場合は、時間の複雑さについて宿題をしています。これは宿題の質問ではありません。それは私が持っていたちょうどランダムな考えです。

Answer 1

コンピューターはどうなりますか？

完了するまで[または予期しないエラーが発生するまで]アルゴリズムを実行します

それはロックされますか？

アルゴリズムの実装方法によって異なりますが、通常は「プログラム」がフリーズする可能性がありますが、特にマシンがマルチコアの場合、コンピューターは引き続き動作します[おそらく低速]。

終了するか、電源が切れるまで、100％の容量で動作しますか？

アルゴリズムがシリアルに実装されており、マシンがマルチコアである場合、100％の容量で実行されません。マルチスレッドの場合、おそらくそうなるでしょう。

終了する前にハードウェアに障害が発生しますか？

2^nopsを必要とするアルゴリズムの場合、およびn=1000[最新の現在のマシンの場合]-おそらく[実行される前に地球はここにありません]。しかし、それを保証するものではありません。

重要：指数関数的な問題の問題は、マシンへの影響ではなく、マシンの問題でもありません。問題は、時間がかかることです。どのぐらいの間？さて、O(n!)アルゴリズム[ナイーブTSP実装]の場合、のn == 20場合、実行時間は〜decadeです。n問題のサイズを少し変更するだけで、1つ増えるだけで、実行時間は最大200年になります。追加の追加により、約4000年になります... [ここでも、最新の現在のマシンを想定してc、O(n!) c >= 1

Answer 2

場合によります。

しかし、ハードウェアが故障することのない理論上のコンピューターを想像すると、非常に長時間実行されるアルゴリズムを確実に設計できます。のように、宇宙の熱死までの長い時間。

通常のオペレーティング システムには、非常に長時間の実行後に問題を引き起こすバグが存在する可能性がありますが、長時間の実行が原因でコンピュータがロックする特別な理由はありません。

Answer 3

「時間の複雑さ」は、結果を得るために必要な時間の尺度にすぎません。そのため、コンピュータは何らかの方法で停止されなくなるまで実行を続けます - Ctrl^C またはブラックアウトによって。