英文:
How to find recursive relation of this recursive function?
问题
以下是您提供的内容的翻译：
这里我有一个像这样的函数，我想找出其递归关系，然后计算该递归关系的时间复杂度。
public static void f(int n) {
if (n == 1) {
// "做某事"
} else {
for (int i = 1; i < n; i++) {
f(i - 1);
// "做某事"
}
}
}
实际上，我为此尝试了很多次，对于这个函数，我得到了**T(n) = n * f(n-1)**作为关系，但我不确定。您能帮我找到正确的关系并解决它吗？
英文:
Here I got a function like this and I want to find the recursive relation of that and after that calculate time complexity of that recursive relation.
public static void f(int n) {
if (n == 1) {
//" Do sth "
} else {
for (int i = 1; i < n; i++) {
f(i - 1);
//" Do sth "
}
}
}
actually I tried a lot for that and I got T(n) = n * f( n-1) for this function as the relation but I am not sure about that . could you help me find the correct relation and solve it ?
答案1
得分: 0
假设 T(1) = "做某事" 是常数工作，即不依赖于输入规模 n，您可以将递归时间函数写成：
T(n) = T(1) + T(2) + ... + T(n-1)
= { T(1) } + { T(1) } + { T(1) + T(2) } + { T(1) + T(2) + T(3) } + { T(1) + T(2) + T(3) + T(4) } +....
[令 T(1) = x]
= x + x + {x + x} + {x + x + (x + x)} + {x + x + (x + x) + x + x + (x + x)} +....
= x + x + 2x + 4x + 8x + ...
~ x.2^(n-2)
~ O(2^n)
这里是一个演示求和系数序列的 Python 程序：
t = [0 for i in range(10)]
for i in range(1, 10):
if i == 1:
t[i] = 1
else:
val = 0
for j in range(1, i):
val += t[j]
t[i] = val
print(t[1:])
输出：[1, 1, 2, 4, 8, 16, 32, 64, 128]
您可以看到，对于每个 n，当 n ≥ 2 时，都成立 2^(n-2)，复杂度为 O(2^n)。
英文:
Assuming T(1) = "Do sth" is constant work i.e. it doesn't depend on the input size n, you could write the recursive time function as :
T(n) = T(1) + T(2) + ... + T(n-1)
= { T(1) } + { T(1) } + { T(1) + T(2) } + { T(1) + T(2) + T(3) } + { T(1) + T(2) + T(3) + T(4) } +....
[let T(1) = x]
= x + x + {x + x} + {x + x + (x + x)} + {x + x + (x + x) + x + x + (x + x)} +....
= x + x + 2x + 4x + 8x + ...
~ x.2^(n-2)
~ O(2^n)
Here is a python program to demonstrate the sequence of coefficients for the summation:
t = [0 for i in range(10)]
for i in range(1,10):
if i == 1:
t[i] = 1
else:
val = 0
for j in range(1,i):
val += t[j]
t[i] = val
print(t[1:])
prints : [1, 1, 2, 4, 8, 16, 32, 64, 128]
You can see that 2<sup>(n-2)</sup> for n >= 2 holds good at each 'n' and complexity is O(2<sup>n</sup>)
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论