时间戳

首页 > 解决方案 > 递归回文问题的时间复杂度，C++

c++ - 递归回文问题的时间复杂度，C++

问题描述

我只是想知道如何在这里找到递归函数的时间复杂度。我知道我的程序的大部分时间都是常数时间 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";
]

标签： c++recursionbig-o

解决方案

它是O(log(n))，其中 n 是数字。

但它也是O(s)，shere s 是输入大小（计算理论中使用输入大小作为字符串的相当标准）

在任何现有的 C++ 平台上编译，您也可以说这是O(k)因为int' 具有有限的大小。

因此，这取决于您使用的约定。或者你的教授在课堂上展示的任何东西。:-)

推荐阅读