Higurashi 最近的时间轴更新
Higurashi

Higurashi

V2EX 第 484673 号会员,加入于 2020-04-18 18:36:54 +08:00
今日活跃度排名 1232
根据 Higurashi 的设置,主题列表被隐藏
二手交易 相关的信息,包括已关闭的交易,不会被隐藏
Higurashi 最近回复了
176 天前
回复了 levelworm 创建的主题 V2EX 不知道 V2EX 能不能修改一下回复评论这个功能
大多数加楼层的回复应该都是用了一个浏览器插件:v2ex-plus 。
205 天前
回复了 Higurashi 创建的主题 问与答 并查集算法的最坏情况
@sengxian #3 虽然没有细看,也没有看懂,但知道这是在作均摊分析,似乎并没有直接分析“最坏”情形。但是在 https://oi-wiki.org/ds/dsu/ 的引用中,有一篇论文( https://www.researchgate.net/publication/220430653_Worst-case_Analysis_of_Set_Union_Algorithms/link/0a85e53cd28bfdf5eb000000/download )对此进行了分析,这篇论文中应该有想要的答案。显然对这个问题的解释并不是一两句话所能够说清楚的,有一种直观的理解方法当然最好,没有的话问题就到此为止。谢谢。
206 天前
回复了 Higurashi 创建的主题 问与答 并查集算法的最坏情况
@sengxian #1 感谢回复。是的,更常见的似乎的确是按高度合并,但按大小合并也是一种可行(而且效率同样较高)的方法。我知道在该情况下深度不变,但这一点如何真正说明连续合并两棵树大小相等时是最坏的?能给些更详细些的提示吗?
206 天前
回复了 hing 创建的主题 分享发现 语雀免费领取 1-4 年会员(必领 1 年)
FQYVG7
@YouRTBUG #3 嗯,再次感谢!
@YouRTBUG #1 感谢回复。因为我理解“处理 N 个触点和 M 条连接”的意思是:开始输入 N 个触点,互不相连(有 N 个分量),然后算法依照输入将触点逐个相连,连接到最后只剩 M 个分量。所以我说“最后剩下 M 条连接”。现在看来它实际的意思应该是:输入 N 个触点,且 N 个触点组成 M 个分量。将 M 个分量连起来需要调用 M 次 union ,加权 quick-union 的 union 函数最多访问数组 lgN 次,所以最多总共最多访问数组 MlgN 次,quick-find 的 union 函数至少访问 (N+3) 次数组,所以总共至少访问数组 M(N+3) 次。和书本上的说明接近,只是不知道为什么 MlgN 前面有一个常数 c ?另外 M(N+3) 次的总次数与 MN 还是有差别。
@ikesnowy #4 嗯,是。所以看来增长的数量级可用来给时间成本的增长快慢分类,比如两种不同的对数增长都属于对数级别、两种不同的线型级别也同属于线性级别(即使两者之间有比较明显的快慢区分)。也正因为如此,增长数量级相对于近似来说更“粗糙”,作者也在答疑中回复道:
“我们希望讨论的是给定成本模型下所有语句执行的准确频率,因为它们能够提供更多关于算法性能的信息,而且从我们所讨论的算法中获取这些频率是可能的。例如,我们可以说‘ThreeSum 访问数组的次数为~ N^3/2’,以及‘在最坏情况下 cnt++执行的次数为~ N^3/6’,它们虽然有些冗长但给出的信息比‘ThreeSum 的运行时间为 O ( N^3 )’要多得多。”
@Higurashi #2 我想我知道了。当数据量很大时,log10N 和 log2N 之间的差别其实并不“显著”(可以到 https://www.geogebra.org/graphing?lang=zh_CN 看看),也正因如此,只有一个“对数级别”而不存在所谓“log10N 级别”或是“log2N 级别”。
关于   ·   帮助文档   ·   API   ·   FAQ   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   846 人在线   最高记录 5497   ·     Select Language
创意工作者们的社区
World is powered by solitude
VERSION: 3.9.8.5 · 19ms · UTC 21:31 · PVG 05:31 · LAX 14:31 · JFK 17:31
Developed with CodeLauncher
♥ Do have faith in what you're doing.