个人中心
文章发布
退出
作者热门文章
- iOS/Objective-C 元类和类别
- objective-c - -1001 错误，当 NSURLSession 通过 httpproxy 和/etc/hosts
- java - 使用网络类获取 url 地址
- ios - 推送通知中不播放声音
26
4
这是关于 wikipedia 上不相交集合森林的联合/查找算法的分割:
O(n))
O(log(n))
O(a(n))，有效 O(1))按排名实现联合需要每个节点保留一个 rank 字段用于比较目的。我的问题是，按等级联合是否值得这个额外的空间？如果我跳过 union by rank 而只是进行路径压缩，会发生什么情况？够好了吗？现在的摊销复杂度是多少？
有一条评论暗示在没有路径压缩的情况下按等级合并(分摊 O(log(n) 复杂度)对于大多数实际应用来说已经足够了。这是正确的。我要问的是反过来:如果您跳过按等级合并并只进行路径压缩怎么办？
从某种意义上说，路径压缩是按等级改进并集的额外步骤，这就是为什么可以省略该额外步骤而不会造成灾难性后果的原因。但是按等级联合是路径压缩的必要中间步骤吗？我可以跳过它并直接进行路径压缩吗，否则这会是灾难性的吗？
还有人指出，如果没有按等级联合，重复联合可能会创建类似链表的结构。这意味着在最坏的情况下，单个路径压缩操作可能需要 O(n)。这当然会影响 future 的操作，所以我更感兴趣的是在分摊到许多操作时如何发挥作用。
最佳答案
我用谷歌搜索“without union by rank”，出现的第二个链接是 this one :
...We close this section with an analysis of union–find with path compression but without union by rank...
The union-find datastructure with path compression but without union by rank processes m find and n-1 link operations in time O((m+n) log n)
关于algorithm - 不相交集森林数据结构的没有按等级联合的联合/查找算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/2323351/
26
4
0
我正在通过修改我为处理 slice 而创建的库来玩转泛型。我有一个 Difference接受 slice 并返回仅在其中一个 slice 中找到的唯一元素列表的函数。 我修改了函数以使用泛型，并且我正
Typescript 编译器 在我尝试使用联合或多个类型/接口(interface)时不断抛出错误。 My requirement 我从服务器收到一个对象作为响应，其中一个键 ('errorMessa
我需要在 SQLAlchemy 中执行 2 选择。例如: select1 = Session.query(col1, col2, col3, col4).filter(...) select2 = S
我建立了一个数据库来输入我所有的头痛和偏头痛跟踪数据。我正在提取一些查询，这些查询显示某一年中按月计算的不同头痛严重程度的计数。我有一个查询按月得到所有头痛，另一个在一定严重程度下得到头痛，最后一个在
我有三个表，一个是默认值表。 我需要做的是选择 TableA 和 TableB 的值，并从默认值的选择中回填任何缺失的值。 每个表都有一个键和值列。 数据的一个例子可能是这样的: DefaultTab
我正在尝试构建一个 单个 JSONPath 查询 ，它将测试 是否存在两个或多个路径 。 让我们考虑以下示例文档: { "firstName": "John",
我正在尝试基于对象中的嵌套属性创建联合类型。请参见下面的示例: type Foo = { abilities: { canManage: boolean } } typ
我有以下查询: SELECT result.globalId AS id, result.date, p1.playerName AS player, p2.playerName AS targe
我有两张 table 。第一个每天刷新。(该表有超过 10 列，但其中 2 列是相关的)我想根据 vid (这是一个唯一的 id )和人口进行每日统计。新的视频 ID 每天都会出现和消失。例如: 第一
这个问题已经有答案了: How to know what table a result came from when using UNION in MySQL (1 个回答) 已关闭 6 年前。 让我
我有 2 个表，一个列出人员及其与其属性的关系，另一个表列出属性(名字、姓氏等)。 人员表中的每个人可能不具有属性表中列出的所有属性。我想要的是每个人都为每个属性返回一行，无论他们是否有链接。 举个例
假设我们有 MySQL 服务器 A，我们需要在其中创建位于服务器 B 上的表的“副本”。 我们没有启用联合。重置服务器 A 会造成很多麻烦，我相信，我们不能在不重置的情况下启用联合。我也认为在B服务器
我有一个 Java 类 A。A 的构造函数调用了几个方法 m1、m2。 class A{ public A(){ m1(); m2(); ......
我正在开发一种编程语言，我想为其提供一个Range 数据类型，目前它不是通常的int 对列表。值 (x,y)约束条件是 x < y .我说不像通常那样，因为通常一个范围只是一对，但在我的例子中，它超过
我正在寻找加速一段合并两个 SortedLists 的代码。 C# 4.0 通用 SortedList:http://msdn.microsoft.com/en-us/library/ms132319
如果我有以下包含函数及其参数的联合，我该如何调用它？ type Wrapper = { fn: (a: string) => void arg: string } | { fn: (a:
我正在尝试移植一个内部有一个联合的 C 结构。 Winapi.Winsock2.pas 中的默认结构记录中缺少某些字段。 但这是正确的方法吗？谢谢。 typedef struct _WSACOMPLE
我希望通过“版本”编号的前 8 个字符的子字符串对以下查询的结果进行排序。我理解 SUBSTRING()，所以不要用这个来打扰我。我的问题是尝试实际放置关于 UNION 的 ORDER BY。 更新:
我需要创建一个带有联合的 QueryBuilder，这可能吗？ $qb = $this->em->createQueryBuilder() ->select('table1.numObject
我正在为 Magic the Gathering Cards 创建库存系统，需要使用主要卡片信息更新价格。 我有两个表，卡片和价格 卡片有以下列:ID、姓名、Ed、价格 价格有以下列:姓名、Ed、价格
我是一名优秀的程序员,十分优秀！