c++ - 对于像 C++ 这样的现实世界语言，时间复杂度有一致的定义吗？

Question

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++ 语言是根据基于标量类型的抽象机器来定义的，例如具有有限的、定义的位数和只有这么多可能值的整数类型。 (Dito 为指针。)

不存在“抽象”C++，其中整数是无界的并且可以“趋于无穷大”。

这意味着在抽象机器中，任何数组、任何容器、任何数据结构都是有界的(即使与可用的计算机及其微小的内存相比可能很大(例如与 64 位数字相比)。

Answer 1

Obviously the size of scalars in any given C++ implementation is finite.

当然，你的这个说法是正确的!另一种说法是“C++ 在硬件上运行，而硬件是有限的”。再说一次，绝对正确。

但是，关键点是: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 .

更新:

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

1. 没有特定机器(无论是抽象的还是真实的)具有 int可以“趋于无穷大”的类型。这就是你所说的，而且是真的!因此，从这个意义上来说总是有一个上限。
2. C++ 标准是为任何 future 可能发明的机器编写的。如果有人使用 sizeof(int) == 1000000 创建硬件，这符合标准。因此，在这个意义上没有上限。

我希望您理解 1. 和 2. 之间的区别，以及为什么它们都是有效的陈述并且不会相互矛盾。每台机器都是有限的，但硬件厂商的可能性是无限的。

所以，如果标准规定了算法的复杂性，那么它就(必须)按照第2点这样做。否则就会限制硬件的增长。而且这种增长没有限制，因此使用复杂性的数学定义是有意义的，该定义也假设没有限制。