本题的答案是不是有问题

Question

本题的答案是不是有问题，除了最后一次递归执行的语句是if(n==1)return1；其余递归执行的语句是2*Func(n/2)+n;
另外本题是不是没有考虑到整数除二会四舍五入，似乎默认了n是偶数

Answer 1

引自免费微信小程序：皆我百晓生

确实，该题目的解析存在不严谨之处，并且没有明确指出整数除法对结果的影响。

首先，分析递归函数Func(int n)的时间复杂度。该函数的递归关系式可以表示为 T(n) = T(n/2) + O(1)，这是因为除了递归调用外，还有一次常数时间的操作（即执行 return 2*Func(n/2)+n; 部分）。根据主定理（Master Theorem），该递归的时间复杂度实际上为 O(logn)。

但是，在分析中提到的“单层循环执行次数”是一种类比，并非严格意义上的循环。在递归过程中，每次调用时都会处理一次基本操作（这里是加法和乘法），然后继续处理规模减半的问题。由于每次都将问题规模减半，并在每次递归调用结束时进行一次附加操作，故总共执行大约 log_2n 次这样的操作，故总时间复杂度确实是 O(logn)。

然而，对于题目中提到的整数除二是否会四舍五入这一点，实际编程语言中整数除以2通常会向下取整（例如在C/C++、Java等语言中），这意味着即使n不是偶数，递归也会正常进行，不会因为奇数除以2导致问题规模跳跃式变化。因此，这里默认n是任意正整数，并不影响最终的时间复杂度分析结论。

综上所述，答案选择C（O(logn)）是正确的，但解析中的表达方式不够准确，没有充分描述每次递归调用的具体操作。尽管如此，它得出的时间复杂度结论是正确的。