问对于像C++这样的现实世界的语言，是否有一致的时间复杂性定义？

EN

什么是官方形式的复杂性在C++，兼容的有限和有界性质的C++操作？

根本就没有。

显然，中标量的大小--任何给定的C++实现--都是有限的。

当然，这句话你是对的！另一种说法是"C++运行在硬件和硬件上是有限的“。再一次，绝对正确。

然而，关键是：C++不是针对任何特定的硬件进行形式化的，而是针对抽象机器进行形式化的。

作为一个例子，sizeof(int) <= 4对我个人曾经为之编写的所有硬件都是正确的。然而，在关于sizeof(int)的标准中根本没有上限。C++标准说明int的大小，长类型是什么？

因此，在特定的硬件上，对某些函数void f(int)的输入确实受到2^31 - 1的限制。所以，从理论上说，不管它做什么，这都是一个O(1)算法，因为它的运算数永远不能超过一定的极限(这是O(1)的定义)。但是，上的抽象机器实际上没有这样的限制，所以这个论点不能成立。

因此，总之，我认为您的问题的答案是，C++没有您想象的那么有限。C++既不是有限的也不是有界的。硬件就是。C++抽象机器不是。因此，描述标准算法的形式复杂性(由数学和理论CS定义)是有意义的。

认为每一种算法都是O(1)，因为在实践中总是有硬件限制，可以用纯理论的思想来证明，但这是毫无意义的。尽管严格地说，大O只在理论上是有意义的(在那里我们可以走向无穷大)，但在实践中它通常也是相当有意义的，即使我们不能走向无穷大，而只能是2^32 - 1。

更新：

关于你的编辑:你似乎混淆了两件事：

1. 没有特定的机器(不管是抽象的还是真实的)具有可能“趋向无穷大”的int类型。这是你说的，这是真的！所以，在这个意义上，总是有一个上界。
2. C++标准是为编写的，任何机器将来都可能被发明出来。如果有人用sizeof(int) == 1000000创建硬件，这是符合标准的。所以，，在这个意义上，没有上界。

我希望你能理解第一条和第二条之间的区别，以及为什么两者都是有效的陈述，而不是相互矛盾的。每台机器都是有限的，但是硬件供应商的可能性是无限的。

因此，如果标准指定了算法的复杂性，它就会(必须)在第2点上这样做，否则就会限制硬件的增长。这种增长没有限制，因此使用复杂性的数学定义是有意义的，它也假定没有极限。

渐近复杂性是一种基于渐近行为的数学构造，当输入的大小和数值趋于无穷大时。

对，是这样。类似地，算法是抽象实体，可以在给定的计算框架(如图灵机)中分析这些度量。

C++试图在许多库函数的规范中使用时间复杂度的概念。

这些复杂性规范对您可以使用的算法施加了限制。如果std::upper_bound具有对数复杂度，则不能使用线性搜索作为底层算法，因为这只具有线性复杂度。

显然，在任何给定的C++实现中，标量的大小是有限的。

显然，任何计算资源都是有限的。您的RAM和CPU只有有限多个状态。但这并不意味着一切都是恒定的时间(或止步问题解决了)。

规范一个实现可以使用哪些算法是完全合理和可行的(在大多数情况下，std::map作为一个红黑树实现是其接口函数复杂性要求的直接后果)。对真实世界程序的实际“物理时间”性能的影响既不明显也不直接，但这不在范围之内。

让我用一个简单的过程来指出你论点中的不一致之处：

1. C++标准指定了某些操作(例如.empty()或.push_back(...))的复杂性。
2. 实现者必须选择符合这一复杂性标准的(抽象的、数学的)算法。
3. 然后，实现者编写代码，在特定的硬件上实现该算法。
4. 人们编写并运行其他使用此操作的C++程序。

您的论点是，确定结果代码的复杂性是没有意义的，因为您不能在有限的硬件上形成渐近线。这是正确的，但它是一个稻草人:这不是标准所做或打算做的。该标准指定了(抽象的、数学的)算法(点1和2)的复杂性，这最终导致(现实世界，有限的)实现(点3)的某些有益的效果/属性，以造福于使用操作的人(第4点)。

这些效果和属性在标准中没有明确规定(尽管它们是这些具体标准规定的原因)。这就是技术标准是如何工作的:您描述的是如何做事情，而不是为什么这是有益的，也不是如何最好地使用它。