本文介绍了如何确定递归代码的Big-O?的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述

我有以下代码,它是此问题的答案: https://leetcode.com/problems/add-digits/

I have the following code, which is an answer to this question: https://leetcode.com/problems/add-digits/

class Solution {
public:
    int addDigits(int num) {
        if (!num/10)
            return num;

        long d = 1;
        int retVal = 0;

        while(num / d){
            d *= 10;
        }
        for(d; d >= 1; d/=10){
            retVal += num / d;
            num %= d;
        }
        if (retVal > 9)
            retVal = addDigits(retVal);

        return retVal;
    }
};

不过,作为后续工作,我正在尝试确定BigO的增长情况.我第一次计算它的尝试是O(n^n)(我想是因为每次深度的增长每次都直接取决于n),这很令人沮丧.我错了吗?我希望我错了.

As a follow-up to this though, I'm trying to determine what the BigO growth is. My first attempt at calculating it came out to be O(n^n) (I assumed since the growth of each depth is directly depended on n every time), which is just depressing. Am I wrong? I hope I'm wrong.

推荐答案

nnum以10为底的数字.我会说

Let n be the number of digits in base 10 of num.I'd say that

T(n)= n + T(n')和n'< = n

T(n)=n+T(n') with n' <=n

哪个给了我们

但是我们可以做得更好吗?请注意,用2位数字表示的最大数字是99,它以这种方式减小99-> 18-> 9.

But can we do better?Note than the maximum number representable with 2 digits is 99 which reduce in this way 99->18->9.

请注意,我们总是可以将10位数字折叠成2个9999999999->90.对于n>10,我们可以分解n/10段中的数字,每个段最多10个数字,然后将这些段减少为每个2位数字的总和. 2位数字的n/10数字总和将总是小于(或等于)(n/10)*2数字.因此

Note that we can always collapse 10 digits into 2 9999999999->90. For n>10 we can decompose than number in n/10segments of up to 10 digits each and reduce those segments in numbers of 2 digits each to be summed. The sum of n/10 numbers of 2 digits will always have less (or equal) than (n/10)*2 digits. Therefore

n小于10的其他基本情况应该更容易些.这给出了

Other base cases with n<10 should be easier. This gives

T(n)= n + T(n/5)表示n> = 10

T(n)=n+T(n/5) for n>=10

求解递推方程给出

这篇关于如何确定递归代码的Big-O?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!

08-20 02:50
查看更多