如果基本情况是 O(n)，则递推式是多少？
我们必须创建一个算法并找到并解决它的递归问题。找到重复性让我难住了。
foo(A, C)
if (C.Length = 0)
Sum(A)
else
t = C.Pop()
A.Push(t)
foo(A,C)
foo(A,C)
最初 A 是空的，C.Length = n。我无法给出真正的算法，因为这是不允许的。
我的导师告诉我，我可以尝试使用 2 个变量。这就是我想到的：
T(n, i) = { n if i = 0
2*T(n, i-1) + C if i != 0
我无法解决它，所以我也尝试仅用一个变量来解决递归：
T(n) = { n0 if n = 0
2*T(n-1) + C if n != 0
其中 n0 是 n 的初始值。
如何从基本情况复杂度为 O(n) 的算法中形成递归？
We have to create an algorithm and find and solve its recurrence. Finding the recurrence has me stumped..
foo(A, C)
if (C.Length = 0)
Sum(A)
else
t = C.Pop()
A.Push(t)
foo(A,C)
foo(A,C)
Initially A is empty and C.Length = n. I can't give the real algorithm because that's not allowed.
My instructor told me that I might try to use 2 variables. This is what I came up with:
T(n, i) = { n if i = 0
2*T(n, i-1) + C if i != 0
I couldn't solve it, so I also tried to solve a recurrence with just one variable:
T(n) = { n0 if n = 0
2*T(n-1) + C if n != 0
Where n0 is the initial value of n.
How do you form a recurrence from an algorithm where the complexity of the base case is O(n)?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
如果 C 的大小为 n，则令 f(n) 为复杂度。设 N 为 C 的原始大小
。则 f(0) = N 且 f(n) = 2 * f(n - 1) + c。
其解为 f(n) = N * 2^n + (2^n - 1) * c，因此 f(N) = O(N * 2^N)。
Let f(n) be the complexity if C is of size n. Let N be the original size of C.
Then f(0) = N and f(n) = 2 * f(n - 1) + c.
This has the solution f(n) = N * 2^n + (2^n - 1) * c, and so f(N) = O(N * 2^N).