note[6]
例:求以下错误的二分代码的平均时间复杂度。 来源
\(1 \le s \le n \le 10^4\) 。
#include<bits/stdc++.h>
using namespace std;
int l=1,r=10000,mid;
int main()
{
int n; cin>>n; r=n;
int s,cnt=0; cin>>s;
while(l<=r)
{
++cnt;
mid=(l+r)/2;
if(mid==s) break;
else if(mid>s) r=mid-1;
else ++l; // here is wrong
}
printf("%d\n",cnt);
return 0;
}
解:
首先不难发现最坏有 \(T(n) = O(n)\)
考虑正常的分析。 \[ \begin{aligned} T(n) &= \frac{1}{2}T\left(n/2\right) + \frac{2}{n}\sum_{i=1}^{\frac{n}{2}}\left[T(i) + \frac{n}{2}-i\right] \\ &= \frac{1}{2}T\left(n/2\right) + \frac{2}{n}\sum_{i=1}^{\frac{n}{2}}T(i) + \frac{2}{n}\sum_{i=1}^{\frac{n}{2}}\left(\frac{n}{2}-i\right) \end{aligned} \] 可以发现最右边的那个东西有个 \(\frac{n^2}{n} = n\) 的大小
所以已经有个 \(O(n)\) 了,因此平均复杂度为 \(O(n)\) 。
说实话我感觉有点怪怪的,但是答案是这个。有待研究。