递归时间复杂度定义混淆
递归算法的时间复杂度被称为
Given a recursion algorithm, its time complexity O(T) is typically
the product of the number of recursion invocations (denoted as R)
and the time complexity of calculation (denoted as O(s))
that incurs along with each recursion
O(T) = R * O(s)查看递归函数：
void algo(n){
if (n == 0) return; // base case just to not have stack overflow
for(i = 0; i < n; i++);// to do O(n) work
algo(n/2);
}根据上面的定义，我可以说，时间复杂度是，R是logn时间，O(s)是n，所以结果应该是n，在这里，与数学归纳法一样，证明了o(n)中的结果。
请不要证明归纳方法。我的问题是，为什么给出的定义不适用于我的方法。
回答 2
Stack Overflow用户
发布于 2019-06-19 19:01:49
问得好！这涉及到在递归调用链中计算工作量的两种不同方法。
您描述的用于计算递归调用中完成的工作量的最初策略--将每个调用完成的工作量乘以调用的次数--有一个隐含的假设。也就是说，这假定每个递归调用的工作量是相同的。如果确实如此，那么您就可以确定作为呼叫数量和每个呼叫工作的乘积完成的总工作量。
但是，如果每次调用的工作量因调用参数的不同而有所不同，则此策略通常不起作用。毕竟，如果没有一个表示完成了多少工作的值，我们就不能把调用所做的“工作量”乘以调用的次数！
确定递归调用链完成的工作量的一个更一般的策略是将每个递归调用完成的工作量相加。在上面描述的函数中，第一个调用所做的工作是n，第二个调用是n/2，因为它所做的工作量是线性的。第三个调用是n/4工作，第四个工作是n/8工作，这意味着所做的全部工作都是以
N+ n/2 + n/4 + n/8 + n/16 + = n(1 + 1/2 + 1/4 + 1/8 + 1/16 +.) ≤2n，
这就是更紧的O(n)界的来源。
值得注意的是，“将所有呼叫所做的所有工作相加”的想法完全等同于“将每个呼叫所做的工作量乘以呼叫的数量”，在特定情况下，每个呼叫所做的工作量是相同的。你明白为什么吗？
或者，如果您可以获得递归调用链完成的工作量的保守上限，则可以将调用的数量乘以任意一个调用所做的最大工作量。这将永远不会低估总数，但它不会总是给你正确的界限。这就是您所列出的例子中的情况--每个调用最多执行n个工作，并且有O(log )调用，所以总工作量确实是O(n log )。这并不是一个紧密的限制。
简短的说明--我不认为将完成的总工作量乘以调用数的策略称为递归调用链所做工作量的“定义”是不合适的。如前所述，与其说这是一个正式的定义，不如说是一种“确定所做工作的策略”。如果有的话，我认为正确的形式定义将是“每个递归调用完成的工作量之和”，因为这更准确地说明了将花费多少时间。
希望这能有所帮助！
Stack Overflow用户
发布于 2019-06-19 18:23:31
我认为你们试图找到关于主定理的信息，这是用来证明递归算法的时间复杂性的。
而且，通常不能仅仅通过查看算法运行时来确定算法运行时，尤其是递归算法运行时。这就是为什么你的快速分析和归纳证明不同的原因。
https://stackoverflow.com/questions/56651231
复制相似问题
腾讯云开发者
