10
|
R.. GitHub STOP HELPING ICE · 技术社区 · 14 年前 |
![]() |
1
10
原因是,如果选择3个块,我们可能会失去使用O(n)时间算法的保证。 对于5个块,时间复杂度为 T(n)=T(n/5)+T(7n/10)+O(n) 对于3个街区,结果是 T(n)=T(n/3)+T(2n/3)+O(n) 看看这个: http://www.cs.berkeley.edu/~luca/w4231/fall99/slides/l3.pdf |
![]() |
2
6
我认为这与保证“良好”的分手有关。划分为5个元素块可确保最坏情况下的拆分为70-30。标准的论点是这样的:
这给了
自从
因此,选择3个元素块可以:
在这种情况下,
|
![]() |
3
4
你可以用3号块!是的,我和你一样惊讶。2014年(你在2010年问过)有一篇论文展示了如何做到这一点。
这个想法是这样的:而不是
所以不是:
上述文章是 Select with Groups of 3 or 4 Takes Linear Time Select with groups of 3 or 4 (2015年,作者主页)。 |
![]() |
feasega · 聚合物模拟-2个节点之间的最短路线,适用于所有节点 6 月前 |
![]() |
Alisa Petrova · 在有向图中更改一对顶点以创建循环 6 月前 |
![]() |
b39b332d · 使用C++标准库实现高效间隔存储 10 月前 |
![]() |
Paul C · 在维基百科上,将二叉搜索树转换为排序链表的算法是否存在错误? 10 月前 |
![]() |
ABGR · 二叉树的直径——当最长路径不通过根时的失败案例 10 月前 |
![]() |
EpicAshman · 数独棋盘程序中同一列和同一行出现两次的数字 11 月前 |