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

Question

C++ 试图在许多库函数的规范中使用时间复杂度的概念，但渐近复杂度是基于当输入的大小和数字的值趋于无穷大时的渐近行为的数学构造。

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

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

备注：不用说，对于基于类型参数的容器或算法（如在 STL 中），复杂性只能用用户提供的操作数来表示（比如对排序的东西的比较），而不是基本的 C++ 语言操作。这不是这里的问题。

编辑：

标准报价：

4.6程序执行 [intro.execution]

1 本国际标准中的语义描述定义了一个参数化的非确定性抽象机。本国际标准对一致性实现的结构没有要求。特别是，它们不需要复制或模仿抽象机器的结构。相反，需要符合要求的实现来模拟（仅）抽象机的可观察行为，如下所述。

2 抽象机的某些方面和操作在本国际标准中描述为实现定义（例如， sizeof(int))。这些构成抽象机的参数。[...]

C++ 语言是根据基于标量类型的抽象机器定义的，例如整数类型，具有有限的、定义的位数和只有这么多可能的值。（Dito 为指针。）

没有“抽象”C++ 整数将是无界的并且可能“趋于无穷大”。

这意味着在抽象机器中，任何数组、任何容器、任何数据结构都是有界的（即使与可用计算机及其微不足道的内存相比可能很大（与 f.ex. 64 位数字相比）。

标签： c++time-complexitylanguage-lawyercomplexity-theory

Answer 1

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

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

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

例如，sizeof(int) <= 4对于我个人编写过的所有硬件来说都是如此。但是，标准中根本没有关于 的上限sizeof(int)。 C++ 标准规定 int、long 类型的大小是多少？

因此，在特定硬件上，某些功能的输入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，这符合标准。所以，从这个意义上说，没有上限。

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

因此，如果标准规定了算法的复杂性，那么就第 2 点而言，它确实（必须）这样做。否则它将限制硬件的增长。而且这种增长没有限制，因此使用复杂性的数学定义是有意义的，它也假设没有限制。