如何确定递归代码的Big

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

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

I have the following code, which is an answer to this question: leetcode/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