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

Question

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

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

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

备注：毋庸置疑，对于基于类型参数的容器或算法（如STL），复杂度只能用用户提供的操作数（例如对已排序内容的比较）来表示，而不能用基本的C ++语言操作。这不是这里的问题。

编辑：

标准报价：

4.6 程序执行 [介绍执行]

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

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

C ++语言是在抽象机器的基础上定义的，它基于标量类型（例如整数类型），具有有限的，已定义的位数，并且只有这么多可能的值。（指针的Dito。）

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

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

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点而言是这样做的。否则，它将限制硬件的增长。而且这种增长是没有极限的，因此使用数学上的复杂性定义是合理的，它也假设没有极限。