递归回文问题的时间复杂度，C++
递归回文问题的时间复杂度，C++
提问于 2019-09-21 03:33:56
我只是想知道如何在这里找到我的递归函数的时间复杂度。我知道我的程序的大部分时间都是固定的O(1)，但是我如何计算递归函数的时间复杂度呢？
int pal(int n, int temp)
{
// Using division of 10 trick
if(n == 0)
return temp;
// Build the number backwards.
temp = (temp * 10) + (n % 10);
// Then advance through the number.
return pal(n / 10, temp);
}
int main()
{
int n = 5678;
int temp = pal(n, 0);
if(temp == n)
cout << "Yes it is a palindrome";
else
cout << "No its not a palindrome";
]回答 1
Stack Overflow用户
发布于 2019-09-21 04:04:23
它是O(log(n))，其中n是数字。
但它也是O(s)，这里的s是输入大小(在计算理论中，将输入大小用作字符串是非常标准的)
在任何现有的C++平台上编译，你也可以争辩说它是O(k)，因为int的大小是有限的。
因此，这取决于您使用的约定。或者你的教授在课堂上展示的任何东西。:-)
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/58034235
复制相关文章
相似问题
腾讯云开发者
