时间戳

首页 > 解决方案 > 联合查找解决方案的时间复杂度

algorithm - 联合查找解决方案的时间复杂度

问题描述

以下问题的解决方案的大约时间复杂度是多少？如果我们假设由于路径压缩，每次调用 self.find() 大致摊销到 ~O(1)

问题陈述：

给定一个帐户列表，每个元素 accounts[i] 是一个字符串列表，其中第一个元素 accounts[i][0] 是名称，其余元素是表示帐户电子邮件的电子邮件。

现在，我们想合并这些帐户。如果两个帐户有一些共同的电子邮件，则两个帐户肯定属于同一个人。请注意，即使两个帐户具有相同的名称，它们也可能属于不同的人，因为人们可能具有相同的名称。一个人最初可以拥有任意数量的帐户，但他们的所有帐户肯定都具有相同的名称。

合并账户后，按以下格式返回账户：每个账户的第一个元素是名称，其余元素是排序后的电子邮件。帐户本身可以按任何顺序退回。

示例：输入：accounts = [["John", "johnsmith@example.com", "john00@example.com"], ["John", "johnnybravo@example.com"], ["John", "johnsmith @example.com", "john_newyork@example.com"], ["Mary", "mary@example.com"]]

输出：[["John", 'john00@example.com', 'john_newyork@example.com', 'johnsmith@example.com'], ["John", "johnnybravo@example.com"], ["Mary ", "mary@example.com"]]

解释：第一个和第三个 John 是同一个人，因为他们有共同的电子邮件“johnsmith@example.com”。第二个 John 和 Mary 是不同的人，因为他们的电子邮件地址都没有被其他帐户使用。我们可以按任何顺序返回这些列表，例如答案 [['Mary', 'mary@example.com'], ['John', 'johnnybravo@example.com'], ['John', 'john00@ example.com', 'john_newyork@example.com', 'johnsmith@example.com']] 仍然会被接受。

class Solution:
    def accountsMerge(self, accounts):
        """
        :type accounts: List[List[str]]
        :rtype: List[List[str]]
        """
        owners={}
        parents={}
        merged=collections.defaultdict(set)
        results=[]

        for acc in accounts:
            for i in range(1,len(acc)):
                owners[acc[i]] = acc[0]
                parents[acc[i]] = acc[i]

        for acc in accounts:
            p = self.find(acc[1],parents) #Find parent of the first email in the list.
            for i in range(2,len(acc)):
            #Perform union find on the rest of the emails across all accounts (regardless of account name, as no common email can exist between different names.)
            #Any common emails between any 2 lists will make those 2 lists belong to the same set.
                currP = self.find(acc[i],parents)
                if p!=currP:
                    parents[currP] = p

        for acc in accounts:
            p = self.find(acc[1],parents)
            for i in range(1,len(acc)):
                merged[p].add(acc[i])        

        for name,emails in merged.items():         
            res = [owners[name]] + sorted(emails)
            results.append(res)

        return results


    def find(self,node,parents):
        if node!=parents[node]:
            parents[node] = self.find(parents[node],parents)
        return parents[node]

标签： algorithmtime-complexityunion-find

解决方案

逐部分检查代码：

for acc in accounts:
    for i in range(1,len(acc)):
        owners[acc[i]] = acc[0]
        parents[acc[i]] = acc[i]

这是 O(N)，其中 N 是输入文本的大小，因为算法只访问输入的每个部分一次。请注意，每个文本元素可能具有任意大小，但要注意这一点，因为 N 是输入文本的大小。

然后：

for acc in accounts:
    p = self.find(acc[1],parents) #Find parent of the first email in the list.
    for i in range(2,len(acc)):
        currP = self.find(acc[i],parents)
        if p!=currP:
            parents[currP] = p

这也是 O(N)，因为：

  1. self.find(acc[i], parents)由于路径压缩，被认为是摊销 O(1)。
  2. 和以前一样 - 每个输入元素都被访问一次。

下一个：

for acc in accounts:
     p = self.find(acc[1],parents)
      for i in range(1,len(acc)):
            merged[p].add(acc[i])

循环本身取决于 N - 输入文本的大小。该add()方法对集合进行操作，在 python 中被认为是 O(1)。总而言之，这个块也需要 O(N)。

最后：

for name,emails in merged.items():         
    res = [owners[name]] + sorted(emails)
    results.append(res)

令人惊讶的是，这里存在瓶颈（至少在 O 表示法方面）。中的元素数量emails是 O(N)，因为很可能系统有一个大用户拥有大部分电子邮件。这意味着sorted(emails)可以采取 O(N log N)。

排序后创建 res 的代码部分：

 res = [owners[name]] + <the sort result>

这仅在排序数据的大小上是线性的，小于排序的 O(N log N)。

尽管处于循环中，但排序的成本加起来总体上不会超过 O(N log N)，因为 O(N log N) 的成本假设有一个大用户。不能超过少数几个大用户。

例如，假设系统中有 K 个相等的用户。这使得每个用户的排序成本为 O(N/K log(N/K))。整个系统的总计为 O(N log (N/K))。如果 K 是常数，则变为 O(N log N)。如果 K 是 N 的函数，则 O(N log(N/K)) 小于 O(N log N)。这不是一个严格的证明，但足以了解为什么它是 O(N log N) 而不是更糟的基本概念。

结论：算法以 O(N log N) 复杂度运行，其中 N 是输入文本的大小。

注意：复杂度计算有一个主要假设，即在 Python 中，通过长度为 L 的字符串键访问映射或集合是 O(L) 操作。这通常是正确的，具有完美的散列函数，而 Python 没有。

推荐阅读