递推公式

Question

首先，是它的硬件 - 真的尽力了，但不知道的东西，所以生病很高兴，如果你能帮助我:)

我有这样的代码：

我需要给这个编码一个recusive公式。 我做的是 - 第一次递归调用是T（n/2）。 第二 - 这是问题！真的很混淆，加上'p'...是那个 T（n/2）呢？ 三 - 对THETA运行（N） 和外面递归调用是T（N）...

你能帮我到最后的公式？

感谢

Answer 1

如果我正确地阅读它，您希望重现运行时复杂性。

对于n > 1，你有复发参数floor(n/2)与参数n-floor(n/2)，之后你输出n项目。因此你有

T(n) = T(cost of first recursive call) + T(second rec. call) + extra work 

你现在应该带入一个适用于主定理的形式。

Answer 2

这可能是一个有趣的问题或者您误解了问题。你有什么是一个递归公式。你需要将这个公式从C++切换到更传统的数学符号吗？需要找到一个非递归算法？在你回答这个问题时，T是什么？术语公式在这里并不适用，因为没有任何东西被计算出来。这是一个永不修改给定数组的无效函数。发生的所有事情都是按照某种顺序将数组中的某些元素放到屏幕上的。

我会从追踪示例开始，了解发生了什么。 比方说A = {1,2,3,4}然后“FUNC（A，0,4）”是：

tracing func(A,0,4) : 
p = 2 
func(A,0,2) 
func(A,2,2) 
cout << 1 2 3 4 

tracing func(A,0,2) : 
p = 1 //start=0; n=2 
func(A,0,1) 
func(A,1,1) 
cout << 1 2 

tracing func(A,2,2) : 
p = 1 //start=2; n=2 
func(A,2,1) 
func(A,3,1) 
cout << 3 4 

tracing func(A,2,1) : 
p = 0 //start=0; n=1 
func(A,0,0) 
func(A,0,1) 
cout << 1 

tracing func(A,3,1) : 
p = 0 //start=3; n=1 
func(A,3,0) 
func(A,3,1) 
cout << 3 

tracing func(A,2,1) : 
p = 0 //start=0; n=1 
func(A,0,0) 
func(A,0,1) 
cout << 1 

在这一点上，我要停下来，因为这是你的家庭作业的问题。你可以从这里完成它。