我们能用什么来证明它的复杂性

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，但我想对它进行精确的空间和时间复杂性分析

有人能帮我找出确切的解决方案吗？对我来说，找出递归方法的确切时空复杂性是非常棘手的

Answer 1

首先观察长度有Θ(5^n/2(个有效数n.考虑到的复发

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

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

由于空间使用是有界的，因此空间使用将渐近相同上按时间，下按输出的总大小，它们是相同的θ。