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

Question

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

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

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

你可以有以下假设:

1. 解决方案永远存在
2. 结果回文的最大值永远不会超过 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 数存在并且如果我们从这些数字开始算法不会终止。