c++ - 关于 C/C++ 标准中的时间/空间复杂度

Question

最近看了抽象机和as-if规则(What exactly is the "as-if" rule?)，以及标准库对时间复杂度的要求(比如这个:Is list::size() really O(n)?)。

1. 标准库的时间/空间复杂度要求是抽象机还是具体机？

如果这些是在抽象机方面，看起来一个实现实际上可以生成复杂度较低的代码，即使它看起来不实用。

1. 标准是否提到了非标准库代码的时间/空间复杂性？

例如我可能会编写自定义排序代码并期望 O(n log n) 时间，但如果实现只是将其视为抽象机器中的代码，则允许在汇编和机器代码中生成较慢的排序，例如将其更改为 O( n^2) 排序，尽管在实际情况下不太可能这样做。

或者我可能遗漏了抽象机和真实具体机之间的转换需求。你能帮我澄清一下吗？ :)

还以为主要看C++标准的东西呢，其实也想了解一下C标准的情况。所以这个问题标记了两者。

Answer 1

1. Are the time/space complexity requirements on standard library in terms of abstract machine or in terms of real concrete machine?

复杂性要求是在抽象机方面:

[intro.abstract] The semantic descriptions in this document define a parameterized nondeterministic abstract machine...

---

2. Did the standards mention anything about time/space complexity for non-standard-library code?

没有。标准中唯一的复杂性要求是针对标准容器和算法的。

if an implementation just treats this as code in abstract machine, it is allowed to generate a slower sorting in assembly and machine code, like changing it to O(n^2) sort

这还不是它能做的最糟糕的事情。一个实现可以让 CPU 在每条指令之间休眠一年。只要您有足够的耐心，该程序就会具有与抽象机相同的可观察行为，因此它是符合规范的。