luosiyuan的博客

博客

关于 $m$ 元组问题

2019-11-07 20:59:29 By luosiyuan

$m$ 元组问题，即询问序列中有多少个长度为 $m$ 的上升子序列的问题。

问：令 $n$ 为序列长度，有没有复杂度小于 $O(nm\log n)$ 的算法？

评论

ouuan

虽然不是很清楚，但应该是小于 $\Theta(nm\log n)$ 吧（

2019-11-08 15:12:03
回复

发表评论

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