我们能证明它的复杂性吗？

Question

在一次在线评估中，我遇到了一个编码挑战，我为此编写了一个递归代码。问题是 -

Given an integer n, return all the reversible numbers that are of length n.
A reversible number is a number that looks the same when rotated 180 degrees (looked at upside down).

 

Example:
Input: n = 2
Output: ["11","69","88","96"]

我写了某种递归方法，它通过了。

    vector<string> recursion(int n, int m) {
        if (n == 0) {
            vector<string> res = {""};
            return res;
        }
        
        if (n == 1) {
            vector<string> res = {"0", "1", "8"};
            return res;
        }
        
        vector<string> ans = recursion(n - 2, m);
        vector<string> res;
        
        for (auto subAns: ans) {
            // We can only append 0's if it is not first digit.
            if (n != m) {
                res.push_back('0' + subAns + '0');
            }
            
            res.push_back('1' + subAns + '1');
            res.push_back('6' + subAns + '9');
            res.push_back('8' + subAns + '8');
            res.push_back('9' + subAns + '6');
        }
        
        return res;
    }
    
    vector<string> getAllNumbers(int n) {
        return recursion(n, n);
        
    }

我认为因为我们正在调用 5 递归，它类似于 5^N 但我想对其进行精确的 space 和时间复杂度分析。

谁能帮我找出确切的解决方案，我很难找出递归方法的确切 space 时间复杂度

Answer 1

先观察长度有Θ(5^n/2)个有效数名词鉴于复发

C(−2) = 0
C(−1) = 0
C(0) = 1
C(1) = 3
∀n ≥ 2, C(n) = 5 N(n−2),

有C(n) − C(n−2) 个数。如果 n = 2k 其中 k 是一个整数，那么 C(n) = 5^k。如果 n = 2k + 1，则 C(n) = 3 (5^k).

运行时间为Θ(5^n/2n)。我们可以写一个递归

T(0) = O(1)
T(1) = O(1)
∀n ≥ 2, T(n) = T(n−2) + Θ(5^n/2 n),

其中后一项计算构造 Θ(5^n/2) 的成本每个长度为 n 的数字。这不是一个非常有趣的重复；我们最终得到一个总和，其项的下降速度比几何下降得更快，所以它是最大项的 Θ。

Space 用法将渐近相同，因为 space 用法是有界的上面是时间，下面是输出的总大小，它们是同样的 Θ.

我们能证明它的复杂性吗？

What could we the complexity proof of it?

algorithm

recursion

data-structures