algorithm - 编译器和语言的选择会影响时间复杂度吗？

Question

当人们谈到使用计算机科学策略解决数学问题所涉及的时间复杂度时，编译器、计算机或语言的选择是否会影响单个方程可能产生的时间？在 x86 机器上以汇编程序运行算法会比在 x64 机器上在 java 中创建相同的公式产生更快的结果吗？

编辑：这个问题与原始问题有点不同，如果编译器和语言的选择无关紧要，那么算法本身是其时间复杂度的唯一决定因素吗？

Answer 1

渐近分析的重点是让我们不必考虑不同编译器、体系结构、实现等引入的细微差别。只要算法的实现方式遵循时间分析中使用的假设，其他因素可以安全地忽略。

我主要是在谈论非平凡的算法。例如，我可能有以下代码：

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

标准分析会说这段代码的运行时间为O(N). 然而，一个好的编译器会意识到这只是一个 nop 并优化它，给你留下一个O(1). 然而，编译器还不够聪明（还）无法对任何不平凡的事情进行任何渐近显着的优化。

某些分析假设不成立的一个例子是当您没有随机存取存储器时。所以你必须确保你的编程平台满足所有这些假设。否则，将不得不执行不同的分析。

Answer 2

除非您使用一些外来语言，例如没有内置常用操作（+、-、/、*、...）的Brainfuck，否则时间复杂度不取决于语言。

但是，如果您使用tail-rec函数，空间复杂度取决于编译器。