代码之家  ›  专栏  ›  技术社区  ›  user1008636

联合求解的时间复杂度

  •  0
  • user1008636  · 技术社区  · 6 年前

    以下问题的解决方案的时间复杂度是多少?如果我们假设由于路径压缩自我发现()大致分摊到O(1)

    其中第一个元素accounts[i][0]是一个名称,其余元素accounts[i][0]是一个名称

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

    格式:每个帐户的第一个元素是名称,其余元素是 元素是按顺序排列的电子邮件。账户本身可以 以任何顺序归还。

    "john00@example.com“],[“约翰”,”johnnybravo@example.com“],[“约翰”, "johnsmith@example.com", "john\u newyork@example.com“],[“玛丽”, "mary@example.com"]]

    输出:[“John”,'john00@example.com', 'john\u newyork@example.com', "mary@example.com"]]

    说明:第一个约翰和第三个约翰是同一个人 “有共同的电子邮件”johnsmith@example.com". 第二个约翰和玛丽 其他账户。例如,我们可以按任何顺序返回这些列表 'john\u 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]
    
    1 回复  |  直到 6 年前
        1
  •  0
  •   Michael Veksler    6 年前

    逐部分检查代码:

    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)):
            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])        
    

    add() 方法对一个集合进行操作,在python中,这个集合被认为是O(1)。总之,这个块也需要O(N)。


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

    令人惊讶的是,瓶颈就在这里(至少就O表示法而言)。中的元素数 emails sorted(emails) 可以取O(N log N)。

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

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

    尽管在一个循环中,排序的成本加起来并不超过O(N logn),因为O(N logn)的成本假设有一个大用户。最多只能有几个大用户。

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


    :算法以O(N logn)复杂度运行,其中N是输入文本的大小。

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

    推荐文章