最近我读到了关于抽象机器和 as-if 规则的东西（“as-if”规则到底是什么？），以及标准库对时间复杂度的要求（比如这个：Is list::size() 真的O（n）？）。
如果这些是在抽象机器方面，那么看起来一个实现实际上可以在复杂性方面生成效率较低的代码，即使它似乎不切实际。
例如，我可能编写自定义排序代码并期望 O(n log n) 时间，但如果实现只是将其视为抽象机器中的代码，则允许在汇编和机器代码中生成较慢的排序，例如将其更改为 O (n^2) 排序，即使在实际情况下不太可能这样做。
或者我可能错过了抽象机器和真实具体机器之间的转换要求。你能帮我澄清一下吗？:)
虽然我主要是看C++标准的东西，但我也想知道C标准的情况。所以这个问题同时标记了两者。
- 标准库的时间/空间复杂度要求是抽象机器还是真实的具体机器？
复杂性要求是抽象机器方面的：
[intro.abstract] 本文档中的语义描述定义了一个参数化的非确定性抽象机......
- 标准是否提到了非标准库代码的时间/空间复杂性？
不可以。标准中唯一的复杂性要求是针对标准容器和算法的。
如果实现只是将其视为抽象机器中的代码，则允许在汇编和机器代码中生成较慢的排序，例如将其更改为 O(n^2) 排序
这还不是它所能做的最糟糕的事情。一个实现可以让 CPU 在每条指令之间休眠一年。只要您有足够的耐心，该程序将具有与抽象机器相同的可观察行为，因此它会符合要求。
C++ 标准中的许多复杂性要求都与特定操作的特定计数有关。这些确实限制了实现。
最多
last - first应用谓词。
这比“ O(N) ”更具体，N = std::distance(first, last)因为它指定了一个常数因子 1。
还有其他的有 Big-O 界限，定义了哪些操作被计算在内
O(N·log(N))，其中
N = std::distance(first, last)比较。
这不限制包括比较的速度有多慢，也没有发生多少交换。如果您的计算模型具有快速比较和缓慢交换，那么您不会得到非常有用的分析。
正如您在评论中被告知的那样，这些标准对时间或空间复杂性没有任何要求。并解决您的其他隐含问题，是的，编译器可以更改您的 O(n log n) 代码以在 O(n²) 时间内运行。或者如果它愿意，在 O(n!) 中。
基本的解释是标准定义了正确的程序，一个程序是正确的，不管它需要多长时间执行或使用多少内存。这些细节留给实现。
特定的实现可以编译你的代码以达到正确的行为。例如，在您编写的每一行代码之间添加 5 秒延迟的实现是完全允许的——程序仍然是正确的。只要可观察到的行为相同，编译器也可以找出更好的方法来执行您编写的内容并重写整个程序。
但是，实现合规的事实并不意味着它是完美的。添加 5 秒延迟不会影响实现的合规性，但没有人愿意使用该实现。编译器不做这些事情，因为它们最终是工具，因此，它们的编写者希望它们对使用它们的人有用，并且故意让你的代码变得更糟是没有用的。
TL;DR：糟糕的性能（时间复杂度、内存复杂度等）不会影响合规性，但它会让你寻找新的编译器。