各种编程语言中算法的运行时

Question

算法的 运行 时间在不同的编程语言中有何不同？例如，假设算法的 运行 时间表示为 Θ(n²) ，如果它是 运行 在 [=18 中，它会有任何不同吗=]、Java、C等?

编辑：我的问题已经得到解答，但如果你们有空的话，我仍然希望补充意见。我的教授让我们在这个季度做我们自己的编程项目，这是我想出的一个主意，我只是想确保有足够的东西供我讨论。我正在重新考虑这个问题，所以如果有人想就此提出想法或 modify/build，我将不胜感激。

Answer 1

算法的时间复杂度与其实现的具体方式密切相关。例如，Dijkstra 算法将 运行 如果您使用 Fibonacci 堆，时间 O(m + n log n)，如果您使用二进制堆，则需要时间 O(m log n)，并且需要时间 O(n²) 如果你使用基于数组的优先级队列。

我提到这个是因为如果你说一个特定的算法 运行s 在时间 Θ(n²) 中，你是说算法，当实现以特定的方式使用特定的数据结构，将在时间 Θ(n²) 中 运行。如果你能忠实地用你选择的编程语言实现适当的数据结构和其他基本操作，那么运行时间就是Θ(n²)。常数因子可能会根据特定语言和 Θ(n²) 算法被翻译成语言的特定方式而有很大差异，但没有根本原因 C 中的算法运行 应该比 Java 中的相同算法渐进地更快，前提是它也可以在 Java.

中表示

也就是说，某些编程语言可能不支持或至少无法有效支持某些操作。纯函数 Haskell 代码，忽略了各种 monadic 技巧，不支持变量赋值和变异，因此许多在命令式模型中 运行 非常快速的算法在 Haskell 中无法有效工作。对纯函数算法和数据结构进行了大量研究，结果 (IIRC) 表明任何命令式算法都可以转换为具有 O(log n) 减速的函数算法。在某些情况下，根本没有减速（例如，在纯函数二项式堆或 red/black 树中）。如果您查看 Haskell 然后允许状态使用 monadic 技巧，那么据我所知，没有减速，因为底层实现可以将代码直接优化为命令式等价物。

再举一个例子，单线程编程语言可能无法实现并行算法，所以即使并行算法 运行s 在时间 Θ(f(n)) 内，最好的你也许可以用一种没有线程的语言来做 ω(f(n))。不支持位操作（如果存在的话）的语言可能无法利用某些位技巧来减少某些类型算法的 O(log n) 因素。

在实践中，您有时会发现在使用不同编程语言实现算法时速度变慢，因为这些编程语言实现某些结构的方式存在细微差别。例如，如果您不习惯使用 C++，很容易在不经意间让许多对象按值而不是指针或引用传递，由于复制对象的成本而增加了额外的成本。如果您还不知道 std::map 实现通常是一些平衡的 BST，由于查找成本，您可能最终会引入一个额外的 O(log n) 因子。也就是说，这与其说是关于特定的语言，不如说是关于该语言中的特定实现。

希望对您有所帮助！