我知道当你将问题集的大小分为指定的一部分时，你在处理O(log(n))。然而，当有多个递归调用执行此操作时，我感到困惑。例如，在这个函数中，我们将计算一个指数的值。
public static long pow(long x, int n)
{
if(n==1)
return x;
if(isEven(n))
return pow(x,n/2) * pow(x,n/2);
else
return pow(x*x, n/2) * x
}
分析后，我得出运行时间为O(N)。我的判断正确吗？感谢您的时间。
是的，至少在最坏情况分析下你说得对。
请注意，对于某个自然数 k，当 n = 2^k 时，除了到达停止条件外，条件始终为真，并且递归函数将运行两次。
当此条件建立时，仅需分析：
T(n) = T(n/2) + T(n/2) + X
其中X是某个常数，（如果忽略其他递归调用，则每次递归调用都需要完成相同的工作量）。
根据主定理情况1，得出：
f(n) = X
a = 2, b = 2, c = 0 (since X is in O(n^0)=O(1))
由于 c=0 < 1 = log_2(2)，因此满足情况1的条件，我们可以得出函数 T(n) 在 Theta(n^log_2(2)) = Theta(n) 中。
平均情况分析：
对于平均情况，使用均匀分布的数字 n，在该数字的二进制表示中，一半位于上方（1），另一半位于下方（0）。
由于除以2基本上是算术右移，而且条件 isEven(n) 仅在最低有效位为0时为真，这意味着平均复杂度函数为：
T(n) = 0.5 T(n/2) + 0.5 * 2 T(n/2) + X = 0.5 * 3 * T(n/2) + X
= 1.5 * T(n/2) + X
So
T(n) = 3/2 T(n/2) + X
情况1仍然适用（假设常数X不变）：
a = 3/2，b=2，c = 0
则平均情况时间复杂度为Theta(n^log_1.5(2))~=Theta(n^0.58)
快速说明：
这假定所有算术操作确实是O(1)的。如果不是这种情况（数字很大），则应该将它们的复杂度放在定义T(n)中的常数位置，并重新分析。假设每个此类操作都是次线性的（与表示其的位数无关），则结果仍为Theta(n)，因为主定理的情况1仍适用。（对于平均情况，“优于”~O(n^0.58)的任何函数都不会改变所示的结果。
Varun，你的部分正确。让我们看看这两种情况：
如果n是偶数，则你只是将任务分成了两半，没有进行重大优化，因为pow(x, n/2)被计算了两次。
如果n是奇数，则你有一种特殊的分解情况。x将被替换为xx，这使得xx成为新的基础，这样就可以避免重新计算x*x。
在第一种情况下，我们有轻微的优化，因为重复较小的乘积比做整个乘积更容易，如下所示：
(3 * 3 * 3 * 3) * (3 * 3 * 3 * 3)比(3 * 3 * 3 * 3 * 3 * 3 * 3 * 3)更容易计算，因此第一种情况通过使用乘法是一个可结合操作的事实稍微改进了计算。在第一种情况下执行的乘法数量并没有减少，但计算的方式更好。
然而，在第二种情况下，你有显著的优化。假设n = (2^p) - 1。在这种情况下，我们将问题简化为一个问题，其中n = ((2^p - 1) - 1) / 2 = ((2^p) - 2) / 2 = (2^(p-1)) - 1。因此，如果p是自然数且n = (2^p) - 1，则将其减半。因此，在最好的情况下，算法对数为n = (2^p) - 1，在最坏的情况下，算法是线性的n = 2^p。
我们通常分析最坏时间复杂度，即当isEven(n)为真时发生的情况。在这种情况下，我们有
T(n) = 2T(n/2) + O(1)
其中T(n)表示pow(x, n)的时间复杂度。
应用主定理，情况1，得到T(n)的大O符号形式。即:
T(n) = O(n)
a=pow(x,n/2); return a*a;- karakfa