編譯器和語言的選擇是否影響時間複雜性？

Question

當人們談論使用計算機科學策略解決數學問題所涉及的時間複雜性時，編譯器，計算機或語言的選擇是否會影響單個方程可能產生的時間？會在x86機器上運行彙編算法產生比在x64機器上使用java創建相同公式更快的結果？

編輯：這個問題從原來的分支出來，如果選擇編譯器和語言無所謂，那麼算法本身就是其時間複雜度的單一決定因素？

Answer 1

漸近分析的重點在於，我們不必考慮由各種編譯器，體系結構，實現等引入的細微差別。只要該算法按照時間使用的假設來實現分析，其他因素可以安全地忽略。

雖然我主要談論的是非平凡的算法。例如，可能我的代碼：

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

標準分析會說，這個代碼片段有O(N)運行時。然而，一個好的編譯器會意識到這僅僅是一個nop並優化它，給你一個O(1)。然而，編譯器還不夠聰明（還沒有）對任何非平凡的東西進行任何漸近顯着的優化。

某些分析假設不成立的例子是當您沒有隨機存取存儲器時。所以你必須確定你的編程平臺滿足所有這些假設。否則，必須執行不同的分析。

Answer 2

除非您使用某些外來語言，例如brainfuck，它不具有用於常見操作（+， - ，/，*，...）的內置插件，但時間複雜度不取決於語言。

但是，如果使用tail-rec函數，空間複雜度取決於編譯器。