algorithm - コンパイラと言語の選択は時間計算量に影響しますか？

Question

人々がコンピュータサイエンス戦略を使用して数学の問題を解決することに伴う時間計算量について話すとき、コンパイラ、コンピュータ、または言語の選択は、単一の方程式が生成する可能性のある時間に影響を与えますか？x86マシンのアセンブリでアルゴリズムを実行すると、x64マシンのJavaで同じ数式を作成するよりも速い結果が得られますか？

編集：この質問は元の質問から分岐しています。コンパイラと言語の選択が重要でない場合、アルゴリズム自体が時間計算量の唯一の決定要因ですか？

Answer 1

漸近解析の要点は、さまざまなコンパイラ、アーキテクチャ、実装などによって導入されたニュアンスを考慮する必要がないようにすることです。時間分析で使用された仮定に従う方法でアルゴリズムが実装されている限り、他の要因安全に無視できます。

ただし、主に重要なアルゴリズムについて話しています。たとえば、次のコードがあるとします。

for(int i=0; i<N; i++){}

標準的な分析では、このコード スニペットのランタイムはO(N). それでも、優れたコンパイラは、これが単なる nop であることを認識して最適化し、O(1). ただし、コンパイラは (まだ) 自明ではないものに対して漸近的に重要な最適化を行うほど賢くはありません。

特定の分析の仮定が成り立たない例は、ランダム アクセス メモリがない場合です。したがって、プログラミング プラットフォームがこれらすべての前提条件を満たしていることを確認する必要があります。それ以外の場合は、別の分析を実行する必要があります。

Answer 2

一般的な操作 (+、-、​​/、*、…) の組み込みを備えていないbrainfuckなどのエキゾチックな言語を使用する場合を除き、時間の複雑さは言語に依存しません。

ただし、 tail-rec関数を使用する場合、スペースの複雑さはコンパイラに依存します。