问题描述
我有以下代码,它是此问题的答案: 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(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/10
segments 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?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!