big-o - 使用无限循环计算时间 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

算法复杂性仅针对算法定义，根据(最常接受的)定义必须终止。这个过程不会终止(除了 Marcelo 指出的“在实践中”；即作为真实机器上的程序与理论上在具有无限磁带和世界上所有时间的理论图灵机上的理论)所以不是算法.所以它没有“算法时间复杂度”。

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