使用无限循环计算时间 T(n) 和 Big-O

Question

我对如何创建函数 T(n) 来测量嵌套无限循环的计算时间感到困惑。这是代码：

x=1;
for(int i = 0;i<n-1;i++){
     for(int j = 1; j<=x; j++){
        cout << j << endl;
        x*=2;
     }
}

因此内部循环将永远持续下去，并且我一直在尝试创建函数来表示其计算时间。我写过它的计算时间是T(n) = [Summation i=0 until (n-2)] (2^j)。 2^j 表示 x 的值与内循环中 j 的当前值。在与我的同行讨论之后，我们绝对同意计算时间肯定不依赖于 n 的值。我们也可能完全过度思考这一点，因为循环是无限的，并且根本没有办法表达其计算时间。非常感谢任何帮助。

Answer 1

算法复杂度仅针对算法进行定义，按照（最常接受的）定义，算法必须终止。这个过程不会终止（除了马塞洛指出的“实践中”；即作为真实机器上的程序与理论上具有无限磁带和世界上所有时间的理论图灵机上的程序），因此不是算法。所以它没有“算法时间复杂度”。

尝试确定非算法的算法复杂性是徒劳的，如果它是一个无限过程，则尝试将其运行时间表示为多项式也是徒劳的。

Answer 2

真正的无限循环的 Big-O 复杂度是未定义的。原因如下：

大 O 表示法的定义是这样的：

f(N) = O(g(N)) 当且仅当对于某个常数，f(n) <= |M g(n)| M，并且对于所有n >= n0

但是，前提条件是 f(n) 和 g(n)是实值函数。

在无限循环的情况下，完成循环所花费的时间的假设值是无限的。因此函数 f(n) 不会将 N 映射到实数。因此，f(N) 不是实值函数，我们无法以具有数学意义的方式应用标准 Big O 定义。

（Big O Notation 上的维基百科页面更正式地说明了定义，但结果是相同。）

---

我们还认为，根据通用定义，不能在有限数量的步骤中完成的算法严格来说不是算法。 （例如，请参阅维基百科算法描述。）因为无限循环不会不完整......永远......它不是一种算法，并且不能具有算法复杂性。

（但是，我不喜欢这个解释，因为它依赖于“算法”一词的特定定义。这个问题实际上并未使用该术语。）

Answer 3

好吧，在现实世界中，由于显而易见的原因，你不会得到答案，但在数学中......为什么不呢。

我将写下该函数的时间方程：

T(n) = n-1 * T(X) 

T(X) 是内部循环的时间。我将花费它：X1 = x 的初始值（在本例中为1）

T(X) = T(X1 * 2) + 1 = T(X1 * 4) + 2 = ... = T(X1 * 2^j) + j

此循环的结束条件是当j >= X1 * 2^j + 1，所以我们要求解：

j >= X1 * 2^j -> j = 2^j -> j <= log2(j).

上面的方程在这个自然数集合范围内无解，但在整数集合中很容易用 -1 求解code> （实际上任何小于0）。

因此，T(n) 的时间复杂度将为 (n-1) * (-1) = 1 - n。

我不知道这有什么用，但我希望它能帮到你。