algorithm - 不同编程语言中的实现可能会影响时间复杂度是什么意思？

Question

我一直认为使用 Big O 的时间复杂度对于任何编程语言的某些代码逻辑都是相同的，但我一直在阅读 C++ 中的引用传递或值传递或其他语言的其他特性有时可能会有不同时间复杂度的影响。这就是说不同编程语言的实现可能会影响时间复杂度的意思吗？怎么可能看到这样的差异。

标签： algorithmtime-complexitybig-o

Answer 1

无论如何，您可以用任何（现实的）编程语言编写相同的算法并获得相同的时间复杂度。

但是用不同语言编写事物的“正常”、“通常”或“显而易见”的方式可能会产生具有不同复杂性的实现。

通过引用传递与值传递通常不在该类别中，因为在允许您选择的语言和不允许您选择在这些情况下通过引用传递的语言中，两者都是自然的。

一些例子可能是：

• 用一种语言对列表进行切片可能会在 O(N) 中生成副本，而在另一种语言中它可能会返回对子列表 O(1) 的引用
• 一种语言的映射或集合可能在哈希表中实现（预期为 O(1)/op），而在另一种语言中可能是 BST (O(log N)/op)
• 不同的语言对重复的字符串或列表连接有不同的优化。

在所有这些情况下，您可以通过实现自己的数据结构或以特定方式做事来获得最佳复杂性，但这不是程序员通常会做的事情。