对于像 C++ 这样的现实世界语言，时间复杂度是否有任何一致的定义？
Is there any consistent definition of time complexity for real world languages like C++?
C++ 试图在许多库函数的规范中使用时间复杂度的概念，但渐近复杂度是基于当输入的大小和数字的值趋于无穷大时的渐近行为的数学构造。
显然，在任何给定的 C++ 实现中，标量的大小都是有限的。
C++ 中复杂性的正式形式化是什么，与 C++ 操作的有限和有界性质兼容？
备注：不言而喻，对于基于类型参数的容器或算法（如在 STL 中），复杂性只能用用户提供的操作数来表示（比如对排序的东西进行比较） ，而不是基本的 C++ 语言操作。这不是这里的问题。
编辑：
标准报价：
4.6 Program execution [intro.execution]
1 The semantic descriptions in this International Standard define a
parameterized nondeterministic abstract machine. This International
Standard places no requirement on the structure of conforming
implementations. In particular, they need not copy or emulate the
structure of the abstract machine. Rather, conforming implementations
are required to emulate (only) the observable behavior of the abstract
machine as explained below.
2 Certain aspects and operations of the abstract machine are described
in this International Standard as implementation-defined (for example,
sizeof(int)). These constitute the parameters of the abstract machine. [...]
C++ 语言是根据基于标量类型的抽象机来定义的，例如整数类型，具有有限的、已定义的位数并且只有这么多可能的值。 （指点同上。）
没有 "abstract" C++ 整数可以是无界的并且可以 "tend to infinity".
这意味着在抽象机中，任何数组、任何容器、任何数据结构都是有界的（即使与可用计算机及其微小内存相比可能很大（与 f.ex 相比）。一个 64 位数字） .
计算复杂度和渐近复杂度是两个不同的术语。引用自 Wikipedia:
Computational complexity, or simply complexity of an algorithm is the amount of resources required for running it.
对于时间复杂度，资源量转化为操作量：
Time complexity is commonly estimated by counting the number of elementary operations performed by the algorithm, supposing that each elementary operation takes a fixed amount of time to perform.
在我的理解中，这是C++使用的概念，即以操作次数来衡量复杂度。例如，如果函数执行的操作数不依赖于任何参数，则它是常量。
相反，渐近复杂度是不同的：
One generally focuses on the behavior of the complexity for large n, that is on its asymptotic behavior when n tends to the infinity. Therefore, the complexity is generally expressed by using big O notation.
渐近复杂度对于算法的理论分析很有用。
asymptotic complexity is a mathematical construct based on asymptotic behavior when the size of inputs and the values of numbers tend to infinity.
正确。同样，算法是抽象实体，可以在给定的计算框架（例如图灵机）内针对这些指标进行分析。
C++ tries to use the concept of time complexity in the specification of many library functions
这些复杂性规范对您可以使用的算法施加了限制。如果 std::upper_bound 具有对数复杂度，则不能使用线性搜索作为基础算法，因为它只有线性复杂度。
Obviously the size of scalars in any given C++ implementation is finite.
显然，任何计算资源都是有限的。您的 RAM 和 CPU 只有有限多个状态。但这并不意味着一切都是常数时间（或者说halting problem is solved）。
标准来管理实现可以使用的算法是完全合理和可行的（std::map在大多数情况下被实现为红黑树是其接口函数的复杂性要求的直接结果）。对实际程序 "physical time" 实际性能的影响既不明显也不直接，但这不在范围内。
让我用一个简单的过程来指出你的论点中的差异：
C++ 标准指定了某些操作的复杂度（例如 .empty() 或 .push_back(...)）。
实施者必须 select 满足该复杂性标准的（抽象的、数学的）算法。
实施者然后编写在某些特定硬件上实施该算法的代码。
人们编写和 运行 其他使用此操作的 C++ 程序。
你的论点是，确定结果代码的复杂性是没有意义的，因为你不能在有限的硬件上形成渐近线。这是正确的，但这是一个稻草人：这不是标准所做或打算做的。该标准指定了（抽象的，数学的）算法的复杂性（第1点和第2点），最终导致（现实世界，有限的）某些有益的effects/properties 实现（第 3 点）以造福于使用操作（第 4 点）的人。
标准中未明确指定这些效果和属性（即使它们是那些特定标准规定的原因）。这就是技术标准的工作原理：您描述的是必须如何完成工作，而不是为什么这是有益的或如何最好地使用它。
Obviously the size of scalars in any given C++ implementation is finite.
当然，你这个说法是对的！另一种说法是 "C++ runs on hardware and hardware is finite"。同样，绝对正确。
然而，关键点在于：C++ 并未针对任何特定硬件进行形式化。
相反，它是针对 抽象机 .
形式化的
例如，sizeof(int) <= 4 适用于我个人编程过的所有硬件。但是，关于sizeof(int)，标准中根本没有上限。
What does the C++ standard state the size of int, long type to be?
因此，在特定硬件上 某些函数 void f(int) 的输入确实受到 2^31 - 1 的限制。因此，从理论上讲，无论它做什么，这都是一个 O(1) 算法，因为它的操作数永远不会超过某个限制（这是 O(1) 的定义）。但是，在抽象机上字面上没有这样的限制，所以这个论点不成立。
所以，总而言之，我认为你的问题的答案是 C++ 并不像你想象的那么受限。 C++ 既不是有限的也不是有界的。硬件是。 C++ 抽象机不是。因此，陈述标准算法的形式复杂性（由数学和理论 CS 定义）是有意义的。
争论每个算法都是 O(1)，只是因为在实践中总是存在硬件限制，可以通过纯理论思维来证明，但这毫无意义。尽管严格来说，大 O 仅在理论上有意义（我们可以走向无穷大），但它通常在实践中也很有意义，即使我们不能走向无穷大而只能走向 2^32 - 1 .
更新：
关于您的编辑：您似乎混淆了两件事：
- 没有 特定的 机器（无论是抽象的还是真实的）的
int 类型可以 "tend to infinity"。这就是你所说的，这是真的！所以，在这个意义上总有一个上限。
- C++ 标准是为任何 未来可能发明的机器编写的。如果有人用
sizeof(int) == 1000000 创建硬件，这符合标准。所以，在这个意义上没有上限。
我希望您理解 1. 和 2. 之间的区别，以及为什么它们都是有效的陈述并且彼此不矛盾。每台机器都是有限的，但硬件厂商的可能性是无限的。
因此，如果标准规定了算法的复杂性，那么就第2点而言，它确实（必须）这样做。否则会限制硬件的增长。而且这种增长没有限制，因此使用复杂性的数学定义是有意义的，它也假设没有限制。
What is the official formalization of complexity in C++, compatible with the finite and bounded nature of C++ operations?
有none.
C++ 试图在许多库函数的规范中使用时间复杂度的概念，但渐近复杂度是基于当输入的大小和数字的值趋于无穷大时的渐近行为的数学构造。
显然，在任何给定的 C++ 实现中，标量的大小都是有限的。
C++ 中复杂性的正式形式化是什么，与 C++ 操作的有限和有界性质兼容？
备注：不言而喻，对于基于类型参数的容器或算法（如在 STL 中），复杂性只能用用户提供的操作数来表示（比如对排序的东西进行比较） ，而不是基本的 C++ 语言操作。这不是这里的问题。
编辑：
标准报价：
4.6 Program execution [intro.execution]
1 The semantic descriptions in this International Standard define a parameterized nondeterministic abstract machine. This International Standard places no requirement on the structure of conforming implementations. In particular, they need not copy or emulate the structure of the abstract machine. Rather, conforming implementations are required to emulate (only) the observable behavior of the abstract machine as explained below.
2 Certain aspects and operations of the abstract machine are described in this International Standard as implementation-defined (for example,
sizeof(int)). These constitute the parameters of the abstract machine. [...]
C++ 语言是根据基于标量类型的抽象机来定义的，例如整数类型，具有有限的、已定义的位数并且只有这么多可能的值。 （指点同上。）
没有 "abstract" C++ 整数可以是无界的并且可以 "tend to infinity".
这意味着在抽象机中，任何数组、任何容器、任何数据结构都是有界的（即使与可用计算机及其微小内存相比可能很大（与 f.ex 相比）。一个 64 位数字） .
计算复杂度和渐近复杂度是两个不同的术语。引用自 Wikipedia:
Computational complexity, or simply complexity of an algorithm is the amount of resources required for running it.
对于时间复杂度，资源量转化为操作量：
Time complexity is commonly estimated by counting the number of elementary operations performed by the algorithm, supposing that each elementary operation takes a fixed amount of time to perform.
在我的理解中，这是C++使用的概念，即以操作次数来衡量复杂度。例如，如果函数执行的操作数不依赖于任何参数，则它是常量。
相反，渐近复杂度是不同的：
One generally focuses on the behavior of the complexity for large n, that is on its asymptotic behavior when n tends to the infinity. Therefore, the complexity is generally expressed by using big O notation.
渐近复杂度对于算法的理论分析很有用。
asymptotic complexity is a mathematical construct based on asymptotic behavior when the size of inputs and the values of numbers tend to infinity.
正确。同样，算法是抽象实体，可以在给定的计算框架（例如图灵机）内针对这些指标进行分析。
C++ tries to use the concept of time complexity in the specification of many library functions
这些复杂性规范对您可以使用的算法施加了限制。如果 std::upper_bound 具有对数复杂度，则不能使用线性搜索作为基础算法，因为它只有线性复杂度。
Obviously the size of scalars in any given C++ implementation is finite.
显然，任何计算资源都是有限的。您的 RAM 和 CPU 只有有限多个状态。但这并不意味着一切都是常数时间（或者说halting problem is solved）。
标准来管理实现可以使用的算法是完全合理和可行的（std::map在大多数情况下被实现为红黑树是其接口函数的复杂性要求的直接结果）。对实际程序 "physical time" 实际性能的影响既不明显也不直接，但这不在范围内。
让我用一个简单的过程来指出你的论点中的差异：
C++ 标准指定了某些操作的复杂度（例如
.empty()或.push_back(...)）。实施者必须 select 满足该复杂性标准的（抽象的、数学的）算法。
实施者然后编写在某些特定硬件上实施该算法的代码。
人们编写和 运行 其他使用此操作的 C++ 程序。
你的论点是，确定结果代码的复杂性是没有意义的，因为你不能在有限的硬件上形成渐近线。这是正确的，但这是一个稻草人：这不是标准所做或打算做的。该标准指定了（抽象的，数学的）算法的复杂性（第1点和第2点），最终导致（现实世界，有限的）某些有益的effects/properties 实现（第 3 点）以造福于使用操作（第 4 点）的人。
标准中未明确指定这些效果和属性（即使它们是那些特定标准规定的原因）。这就是技术标准的工作原理：您描述的是必须如何完成工作，而不是为什么这是有益的或如何最好地使用它。
Obviously the size of scalars in any given C++ implementation is finite.
当然，你这个说法是对的！另一种说法是 "C++ runs on hardware and hardware is finite"。同样，绝对正确。
然而，关键点在于：C++ 并未针对任何特定硬件进行形式化。 相反，它是针对 抽象机 .
形式化的例如，sizeof(int) <= 4 适用于我个人编程过的所有硬件。但是，关于sizeof(int)，标准中根本没有上限。
What does the C++ standard state the size of int, long type to be?
因此，在特定硬件上 某些函数 void f(int) 的输入确实受到 2^31 - 1 的限制。因此，从理论上讲，无论它做什么，这都是一个 O(1) 算法，因为它的操作数永远不会超过某个限制（这是 O(1) 的定义）。但是，在抽象机上字面上没有这样的限制，所以这个论点不成立。
所以，总而言之，我认为你的问题的答案是 C++ 并不像你想象的那么受限。 C++ 既不是有限的也不是有界的。硬件是。 C++ 抽象机不是。因此，陈述标准算法的形式复杂性（由数学和理论 CS 定义）是有意义的。
争论每个算法都是 O(1)，只是因为在实践中总是存在硬件限制，可以通过纯理论思维来证明，但这毫无意义。尽管严格来说，大 O 仅在理论上有意义（我们可以走向无穷大），但它通常在实践中也很有意义，即使我们不能走向无穷大而只能走向 2^32 - 1 .
更新：
关于您的编辑：您似乎混淆了两件事：
- 没有 特定的 机器（无论是抽象的还是真实的）的
int类型可以 "tend to infinity"。这就是你所说的，这是真的！所以，在这个意义上总有一个上限。 - C++ 标准是为任何 未来可能发明的机器编写的。如果有人用
sizeof(int) == 1000000创建硬件，这符合标准。所以，在这个意义上没有上限。
我希望您理解 1. 和 2. 之间的区别，以及为什么它们都是有效的陈述并且彼此不矛盾。每台机器都是有限的，但硬件厂商的可能性是无限的。
因此，如果标准规定了算法的复杂性，那么就第2点而言，它确实（必须）这样做。否则会限制硬件的增长。而且这种增长没有限制，因此使用复杂性的数学定义是有意义的，它也假设没有限制。
What is the official formalization of complexity in C++, compatible with the finite and bounded nature of C++ operations?
有none.