对于C++这样的现实世界语言,是否有时间一致性定义?

C++中的复杂性形式正式化,与C++操作的有限性和有限性兼容?

没有。

很明显鳞片的大小 是有限的。

当然,你的说法是对的!另一种说法是“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++标准是为 任何 将来可能发明的机器。如果有人用 sizeof(int) == 1000000 从这个意义上说 没有上限。

我希望你能理解1之间的区别。和2。为什么它们都是有效的陈述而不互相矛盾。每台机器都是有限的,但硬件供应商的可能性是无限的。

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

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

在许多图书馆功能的规范中,C++试图使用时间复杂性的概念。

这些复杂性规范对您可以使用的算法施加限制。如果 std::upper_bound 具有对数复杂度,不能使用线性搜索作为基础算法,因为它仅具有线性复杂度。

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

halting problem is solved ).

算法 实现可以使用( std::map 在大多数情况下,作为红黑树实现是其接口函数的复杂性要求的直接结果。对真实程序的实际“物理时间”性能的影响既不明显也不直接,但这不在范围之内。

让我用一个简单的过程来指出你论点中的分歧:

1. C++标准指定了某些操作的复杂性(例如)。 .empty() 或 .push_back(...) ).

3. 然后,实现者编写实现该算法的代码 在某些特定硬件上 .

你的论点是,确定所产生的代码的复杂性是没有意义的,因为你不能在有限的硬件上形成渐近线。这是正确的,但它是一个救命稻草:这不是什么标准做或打算做。该标准规定了(抽象的、数学的)复杂性。 算法 (第1点和第2点),最终导致(现实世界,有限)的某些有益效果/特性 实施 (第3点)为了使用操作的人的利益(第4点)。

这些影响和特性在标准中没有明确规定(即使它们是这些特定标准规定的原因)。这就是技术标准的工作原理:你描述的是必须如何做的事情,而不是为什么这是有益的或如何最好地使用它。

和 是两个不同的术语。引用自 Wikipedia :

,或者简单地说,算法的复杂性是 .

为了 ,资源量转换为 作业量 :

通常是通过计算 ,假设每个基本操作都需要固定的执行时间。

在我的理解中,这是C++使用的概念,也就是说,复杂性是用 操作次数

相反地, 有点不同:

人们通常关注 n个 ,在它的 渐近行为 n个 . 因此,复杂性一般用大的来表示。 O型

渐近复杂性对于算法的理论分析是有用的。