Kevin5307的博客

博客

UNR #8 D2T2 的一个估计没有什么用的线性做法

2024-07-14 22:40:45 By Kevin090228

先咕一下,闲下来写。

是我场上写的做法,只不过场上我以为它的复杂度是 O(nlogn) 状物。

中间复杂度分析的部分有大量我的扯淡,请在看中间的分析之前先跳到最后查看正确的复杂度分析。


来写一下。

由于我不会 SMAWK,所以只能随机二分,自然询问次数为 O(nlogn)

考察瓶颈所在的位置:二分提供 O(logn),双指针提供 O(n)。由于二分显然不可能被继续优化,考察如何减少双指针的次数。我的想法是设置步长 s,每一次指针移动的时候,相比于每次移动 1 个位置,我们可以每次移动 s 个位置。

这可能会带来误差,考察误差的影响。形象的思考带步长的双指针的过程。普通双指针实际上是找到了一个分割线/轮廓线,使得左上角是 mid 的数,右下角是 >mid 的数。带步长的双指针找到的轮廓线是对这个轮廓线的一个粗略近似,但是它相比原轮廓线的误差不会超过步长 s

那么我们二分再往两边递归的时候,如果想往左上递归,就将轮廓线往右下平移 s 个位置,想往右下递归,就将轮廓线往左上平移 s 个位置。这样所有当前可能成为第 k 大的位置就仍然会被包含在待确定的区域中。


分析一下这个东西的询问次数。

我场上认为这个东西仍然是 O(nlogn) 的,没有什么实质优化,所以一直在尝试调整步长 s 并对拍。现在可以仔细分析一下询问次数了。下面的分析过程不太严谨,但是感性理解足够了。

f(x) 表示当前待确定区域的左上到右下的斜向宽度(这里默认左下到右上方向的宽度为 n,显然不可能超过这个值)为 x 的时候需要的询问次数。设步长为 s,有:

f(x)=minsf(x2+s)+O(ns)

由于是随机二分,所以实际应该是一个概率分布,但是我正在感性理解,于是当成 x/2 计算了。取 s=logx,进行 logx 轮,由于 s 远小于 x,暂时忽略这个 f(x/2+s) 中的 s。那么有粗略的递推式:

f(x)=f(logx)+O(n)

然后大概就能得出 f(n)=O(nlogn) 了。

虽然忽略 s 这个事情看上去就不严谨,但是感性理解大概能得到一个这样的结果。然后这里不一定取到了下界,所以可能还会更优。


没有分析复杂度的常数,因为这东西本来就复杂度不优。并且我分析不明白,就这样。


感觉分析其实可能是错的,如果每一步都取 s=logx,且忽略 s 的话,只能得出:

f(x)=f(x2)+O(nlogx)

然后这个解出来是 f(x)=xloglogx

请懂的人教我一下。@monstersqwq 教我一下谢谢。


其实是线性的,取 s=x/2,感谢咋克。


仔细分析各种乱七八糟的东西,最后可以得到 15.5n 的复杂度上界。哈哈,没有任何意义。

评论

[0]
  • 2024-07-15 11:59:59
  • Reply

发表评论

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