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)$ 。

说实话我感觉有点怪怪的，但是答案是这个。有待研究。