如何计算此算法的时间复杂度

GullDe 发表于 Dev

古尔德

我编写了一个函数，该函数获取给定的数字并将其添加到相反的位置，直到该数字是回文。我正在尝试计算代码的时间复杂度，但我根本不知道该怎么做甚至不知道如何开始。有人可以告诉我该怎么做吗？另外，这是最有效的方法还是将整数转换为字符串更好？

void getPali(int num) {        
    int n = 0;
    int nNum;
    while(true) {
        nNum = num;
        int rNum = 0;            
        while (nNum > 0) {
            int rem = nNum % 10;                
            nNum = nNum / 10;                 
            rNum = rNum * 10 + rem;                
        }
        if(rNum == num) break;
        num += rNum;              
        n++;
    }
}

帕帕姆斯

好吧，作为输入值num的函数。此代码块：

while (nNum > 0) {
    int rem = nNum % 10;                
    nNum = nNum / 10;                 
    rNum = rNum * 10 + rem;                
}

将必须执行log（n）次。这是因为每次通过此循环将nNum减少10倍。因此，对于2 ^ 10的数字，将需要10次循环迭代才能完成。另外，由于在每个循环的开始将nNum重置为n，因此每次循环将花费相同的时间。

然后循环的下一部分是

if(rNum == num) break;
num += rNum;              
n++;

这本质上是循环条件，但是它是以奇怪的方式编写的。较大的循环将执行到rNum = num。所以问题是rNum增加多快。答案是，rNum每次经过大循环时都会增加10倍，因此要达到num，将再次花费lg（n）时间。

因此，组合时间复杂度为log（n）^ 2。因为外循环执行log（n）次，内循环执行log（n）次。因此时间复杂度为log（n）^ 2（或log ^ 2（n））

本文收集自互联网，转载请注明来源。

如有侵权，请联系[email protected] 删除。

编辑于2021-02-19

我来说两句

0条评论

登录后参与评论

来自分类Dev

Related 相关文章

文章