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

Question

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

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

Answer 1

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

不过，我主要讨论的是不平凡的算法。例如，我可能有代码：

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

标准分析会说这段代码的运行时间为

O(N)

。然而，一个好的编译器会意识到这只是一个 nop 并将其优化掉，留下一个

O(1)

。然而，编译器还不够智能，无法对任何不平凡的事情进行任何渐近显着的优化。

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

Answer 2

除非您使用一些外来语言，例如brainfuck，它不具有常见操作的内置功能（+，-，/，*，...），时间复杂度不依赖于语言。

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