从多种参数的算法中查找封闭表格

function What(n,a,total) 
    if n=0 
     return total 
    elseif n is even and n>0 
     return What(n/2, a+1, total) 
    elseif n is odd 
     return What((n-1)/2, a+1, total + 2^n) 
    endif 
end What

我不知道如何找到此算法的封闭形式。这不是一个家庭作业问题，只是为我即将到来的决赛学习以前的考试。根据给定的标记/空间，它应该是一个小/简单的解决方案。从多种参数的算法中查找封闭表格

假设总开始于0，

我可以看到，该算法返回图2，如果n为2的幂;如果n是偶数，则返回2 ^（n/2）+2;如果n是奇数，则2^n + 2。对于第一个elseif我得到了T（n/2）+ 1时间，对于第二个elseif我得到了T（（n-1）/ 2）+ 2^n + 1（？）时间。总体而言，我不知道如何去寻找这里的封闭表格/使用重复的替代。

来源

2016-08-01 user284064

您是否试图为算法的*返回值*或其*时间复杂度*找到一个封闭的表单？目前尚不清楚。 – user2357112

@ user2357112我给出了运行时间的答案。我不认为我有一个封闭的形式的数学:-) –

欣赏What()函数的复杂性似乎只取决于传递给它的第一项。通过检查，这是相当清楚地看到，运行时间为O(lg_2 N + 2)，整数N> 0。为了证明这一点，只考虑要求对2的前几个整数倍的功能数量：

num | # function calls 
2 |   3 = lg_2(2) + 2 
4 |   4 = lg_2(4) + 2 
8 |   5 = lg_2(8) + 2 
16 |   6 = lg_2(16) + 2

具体，每次调用What(n)将调用What(floor(n/2))，这意味着n在递归的每个线性步骤中被分成两半。

来源

2016-08-01 23:54:54

从多种参数的算法中查找封闭表格

回答

相关问题