无限循环计算时间T(n)和Big-O [英] Computing Time T(n) and Big-O with an infinite loop

问题描述

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

I'm confused on how to create a function T(n) to measure computing time for a nested infinite loop. Here is the code:

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的值.由于循环是无限的，而且我们根本无法表达其计算时间，因此我们也可能对此过度考虑.任何帮助将不胜感激.

So the inner loop will go on forever, and I am stuck trying create the function to represent its computing time. I have written that its computing time is T(n) = [Summation i=0 until (n-2)] (2^j). 2^j represents the value of x with the current value of j from the inner loop. After discussing this with my peers, we definitely agree that the computing time is certainly not dependent on the value of n. We also could be completely over-thinking this as the loop is infinite and there is simply no way to express its computing time. Any help is greatly appreciated.

推荐答案

仅针对算法定义算法复杂度，而算法必须(最常被接受)定义终止.该过程不会终止(如Marcelo所言，在实践中除外"；即作为真实机器上的程序，而理论上是具有无限磁带且在世界范围内的理论图灵机上的理论上)，因此该算法不是算法.因此它没有算法时间复杂度".

Algorithm complexity is only defined for algorithms, which by (the most often accepted) definition must terminate. This process doesn't terminate (except "in practice" as Marcelo notes; i.e. as a program on a real machine vs. in theory on a theoretical Turing machine with an infinite tape and all the time in the world) so is not an algorithm. So it has no "algorithmic time complexity".

尝试确定非算法的算法复杂度是徒劳的，如果尝试将其运行时间表示为多项式，则这是徒劳的.

Trying to determine the algorithmic complexity for a non-algorithm is a futile exercise, as is trying to express its running time as a polynomial if it's an infinite process.

这篇关于无限循环计算时间T(n)和Big-O的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！