计算具有无限循环的时间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)= [求和i = 0直到(n-2)](2 ^ j).2 ^ j表示x的值,其内部循环的当前值为j.在与同行讨论这个问题之后,我们肯定同意计算时间肯定不依赖于n的值.我们也可能完全过度思考,因为循环是无限的,根本没有办法表达它的计算时间.任何帮助是极大的赞赏.

Answer 1

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

试图确定非算法的算法复杂度是徒劳的,如果它是一个无限的过程,试图将其运行时间表示为多项式.