OIer_Automation的博客

博客

复杂度分析求助

2025-03-30 15:12:59 By OIer_Automation

有一个长度为 $n$ 的序列 $a$，现在有一个针对序列 $a$ 的算法。我们设集合 $S_r=\{\text{mex}(l,r)|1\le l\le r\}$，其中 $\text{mex}$ 是区间中最小的没有出现过的自然数，那么这个算法的复杂度为 $\sum_{1\le r\le n}|S_r|$，询问这个算法复杂度的级别，或者换句话说，我们可以将这个算法卡到什么程度？

A2_Chaos

感觉可以到立方级别，比如说我1放中间，2放1左边，3放1右边，4放2左边，以此类推。瞪了一下感觉是立方的。

2025-03-30 17:00:47
回复

liu_cheng_ao

序列中间1/3放 $0,1,\dots,n/3$，那么至少有 $n^2/9$ 个区间答案不小于 $n/3$，所以肯定是 $O(n^3)$ 的。不过，如果想要进一步的精确的最大值而不是渐进的最大值倒是比较困难。

2025-03-31 15:37:46
回复

发表评论

可以用@mike来提到mike这个用户，mike会被高亮显示。如果你真的想打“@”这个字符，请用“@@”。