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

Question

我多次遇到这种情况,往往很难估计迭代次数,因此最坏情况下的时间复杂度也很接近.这是问题所在:

给你一个数字N.你继续加上数字N反向,直到得到回文.例如327.

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

您可以有以下假设:

1. 解决方案始终存在
2. 得到的回文最大值永远不会超过2 ^ 32(4位int足够)

这是我的代码:

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数是算法不终止的数字.196是最着名的一个.没有证明算法永远不会终止196或其他Lychrel数字,但显然没有人能找到解决方案,因此假设Lychrel数字存在,如果我们从这些数字开始,算法不会终止.