确定迭代次数难以估计时的时间复杂度

Question

我遇到过这种情况很多次，通常很难估计迭代次数，因此很难估计最坏情况下的时间复杂度。这是问题所在：

给你一个数字N，你不断地把数字N和它的倒数相加，直到得到回文。例如给出了327。

327 + 723 = 1050
1050 + 0501 = 1551
You stop

您可以有以下假设：

解决方案总是存在的
结果回文的最大值永远不会超过 2^32（足够 4 位整数）

这是我的代码：

unsigned long rev(unsigned long k)  //log k 
{
    unsigned long res = 0;
    while(k)
    {
        res = res * 10 + k%10;
        k = k/10;
    }
    return res;
}

int main()
{
    int t,iter;
    unsigned long n,res;

    cin >> t;
    while(t--)
    {
        cin >> n;
        iter = 0;

        while(1) //how many times this loop runs?
        {
            iter++;
            res = n + rev(n);
            if(res == rev(res)) //is a palindrome
                break;
            else
                n = res;
        }
        cout << iter << " " << res << endl;
    }

    return 0;
}

这种情况下的时间复杂度是多少？

这取决于内部 while 循环在最坏情况下运行的次数。最坏的情况发生在数字从 10 开始跳到 2^32 之前的最大回文。但是要跳多少次又很难估计。

也许在这种情况下我们可以应用某些数学来估计迭代，但是如果在达到回文之前通过执行随机代数 (+,-,*) 来随机化情况怎么办。我们如何在那些随机情况下引用时间复杂度？

Answer 1

你无法估计时间复杂度，因为（还）不能证明算法总是终止。

所谓的Lychrel numbers就是算法不终止的数字。 196是最著名的。尚未证明该算法永远不会因 196 或其他 Lychrel 数而终止，但显然还没有人找到解决方案，因此假设 Lychrel 数存在并且如果我们从这些数字开始算法不会终止。

确定迭代次数难以估计时的时间复杂度

Determine the time complexity when number of iterations are difficult to estimate

algorithm

computer-science

c++11