这个问题已经被问过几次了，但是我仍然很难找到这个问题的答案，因为它比其他问题中提供的简单示例更加复杂。
我正在尝试为以下项找到大的O表示法：
float foo(int start, int end, int s)
{
if (start == end) {
return start*start;
} else {
int iSegment = (end - start + 1) / s;
int iCurrResult = 0;
for (int i=0; i<=s; i++)
iCurrResult += foo (start + i*iSegment, start + (i+1) * iSegment - 1, s);
return iCurrResult*iCurrResult;
}
}
每次调用该函数时，它都会s+1以一定范围的大小n/s（n即元素数）递归地调用自身。
这为您提供了复杂度函数：
T（n）=（s + 1）T（n / s）+1
根据Wolphram Alpha的说法，此功能位于O((s+1)^(logn/logs)) = O((s+1)^log(n-s))
请注意，这是在中Omega(n)，因为n=s^log_s(n)=s^log(n)/log(s)，很容易看出该函数严格（且渐近地）大于s^(logn/logs)
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句