关于本题暴力算法时间复杂度

首先这里暴力算法指的是：

CPP

//输入并排序
//求前缀和并保存至数组s
for(k=3;k<=n;k++) for(i=k;i<=n;i++) if(a[i]<s[i-1]-s[i-k]) {
    cout<<k<<' ';break;
}

或者类似的东西。

可以证明除排序部分之外剩下的复杂度是

O(n+\log ^2(\max a))

。

对于每个“循环次数大于一”的

k

，都有

a_1+a_2+\cdots+a_{k-1} \le a_k

。所以把这些

a_k

排成一个序列，就会发现序列中每一项都大于等于前面所有项的和。故由归纳法易证序列的第

i(i \ge 2)

项至少是

2^{i-2}

。从而这样的

k

最多有

O(\log(\max a))

个。

然后看这些

k

对应的循环次数。

对于每个

k

，假设 break 语句在

i=\text{i}(k)+1

时执行。如果一直没有执行，则令

\text{i}(k)=n

。

这样就会得到：

a_1+\cdots+a_{k-1} \le a_k,a_2+\cdots+a_k \le a_{k+1}

，以此类推直到

a_{\text{i}(k)}

。

因为所有

a

都是正的，所以在左边去掉若干项，不等式仍然成立。

所以当

\text{i}(k)<2k

时，可以发现：

a_k \le a_{k+1},a_k+a_{k+1} \le a_{k+2}

，以此类推直到

a_k+a_{k+1}+\cdots+a_{\text{i}(k)-1} \le a_{\text{i}(k)}

。

所以这个序列：

a_k,a_{k+1},a_{k+2},\cdots,a_{\text{i}(k)}

它也满足“每一项都大于等于前面所有项的和”，所以同样有第

i(i \ge 2)

项不小于

2^{i-2}

。从而

a_{\text{i}(k)}

是

2^{\text{i}(k)-k}

量级，

\text{i}(k)-k=O(\log(\max a))

。

如果

\text{i}(k) \ge 2k

，刚才的结论仍然对于

2k-1

适用，即

a_{2k-1} \ge 2^{k-2}

。于是从

a_{2k-1}

开始再构造若干类似刚才的序列，直到

a_{\text{i}(k)}

。就会发现它依然是

2^{\text{i}(k)-k}

量级。

所以还是有

\text{i}(k)-k=O(\log(\max a))

。

综上，每个

k

对应的循环次数最多是

O(\log(\max a))

。

这样最开始的结论就证出来了。（因为不算太严谨，而且有点啰嗦，所以就发在讨论区了）

关于本题暴力算法时间复杂度

讨论操作

回复

相关推荐

关于本题暴力算法时间复杂度