如何确定递归代码的Big-O? [英] How do determine Big-O of recursive code?

问题描述

我有以下代码，它是此问题的答案: 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.

推荐答案

让n为num以10为底的数字. 我会说

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

T(1)= O(1)

T(1)=O(1)

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

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

哪个给了我们

O(n * n)

O(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

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

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

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

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

T(n)= O(1)表示n <10

T(n)=O(1) for n<10

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

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

求解递推方程给出

n等于10的O(n)

O(n) for n>=10

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