如何确定递归代码的Big-O？
我有以下代码，这是对这个问题的回答：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），这很令人沮丧。我错了吗？我希望我错了。
共有3个答案
看起来它是值的O（1）
我对大O符号还不够精通，无法给出如何将其结合起来的答案。
很可能第一部分在意义上是可选择的，这样整体时间复杂度就变成了O（n）。
设n为num的基数10的位数。我会这么说
T（1）=O（1）
T（n）=n T（n’）带n'
这给了我们
O（n*n）
但是我们能做得更好吗？注：用2位数字表示的最大数字为99，以这种方式减少-
请注意，我们总是可以将10位数字折叠为299999999-
T（n）=n对于n，T（n/5）
具有n的其他基本情况
T（n）=O（1）表示n
T（n）=n对于n，T（n/5）
求解递推方程给出了
O（n）表示n
在这种情况下，它是线性的，因为在方法体中递归调用addDigits方法，没有任何循环等等
更多细节：确定递归函数的复杂度（大O表示法）
更新：从递归函数调用一次的角度来看，它是线性的。然而，在这种情况下，这并不完全正确，因为执行的数量几乎不取决于输入参数。
-
问题内容： 我使用firefox版本> 3.5（3.5。 ，3.6。 ，4。*），我尝试正确地指定和属性，但是它不起作用。我的applet主类位于中，运行时加载的一些必需类位于中。如果仅指定，则将加载该applet，但缺少来自的类。如果指定和，则无法加载该applet。看起来像applet尝试从文件夹加载主类，并且不查找文件。 主类位于http://myurl.com/archive/myjar.
-
我试图想出一个程序，从用户那里获取任何数字，并生成斐波那契码的第n个数字。当我完成工作时，它会显示下一个，而不是我需要的。例如，我正在寻找第11个#和它的生产233而不是144。这是我的代码：
-
我对这个代码有一些问题 问题1：终止情况究竟如何运作？s.length如何等于0？ 问题2：为什么代码需要具有“firstChar”才能反转字符串？为什么当逆转字符串接受0的子字符串而不必添加第一个字符时，代码不起作用？
-
我需要解码一个递归编码为count后跟substring的字符串 给定一个编码字符串，任务是对其进行解码。字符串的编码模式如下所示。 示例： 输入：str[]=“1[b]”输出：b 输入：str[]="2[ab]输出：abab 输入：str[]=“2[a2[b]”输出：ABB 输入：str[]="3[b2[ca]]"输出：bcacabcacabcaca 下面是我试图实现的代码。我只知道它可以用两个
-
我需要编写伪代码来检查有效的二叉树是否是搜索二叉树。 我创建了一个数组来保存树的顺序值。如果顺序值是降序的，这意味着它确实是BST。然而，我对INOVERAR方法中的递归有一些问题。 我需要更新数组的索引，以便按照值在树上的顺序将其提交给数组。 我不确定在递归过程中索引是否真的得到了正确更新。。到底是不是？如果你发现问题，能帮我解决吗？谢谢 伪代码 第一功能 IsBST（节点） 大小← 树化（节点