1

前几天我被要求写一个基本方法，当给两个朋友时，如果他们有联系（我的意思是他们是朋友的朋友的朋友）返回 true，如果他们不相关则返回 false（没有他们任一好友列表中的一个已连接）。

在和这个人一起工作之后，这是我们得出的基本算法：

def is_linked(friend_a, friend_b, visited = {}):

  is_found = False
  friends = friend_a.get_friends()

  # You can assume this method is O(1)
  if friends.contains(friend_b):
    return True

  visited[friend_a] = 1
  for friend in friends:

    # Prevents infinite recursion
    # Assume O(1)
    if friend in visited:
      next

    is_found = is_linked(friend, friend_b, visited)
    if is_found:
      last

  del visited[friend_a]
  return is_found

该算法的最坏情况时间复杂度是多少？ 我们每个人都提出了自己的答案，由于我们无法达成协议，我希望在这里独立验证。

4

2 回答 2

2

我要把我的答案扔在那里。我认为 Wikipedia 上的广度优先搜索文章涵盖了该文章，该文章表明它确实取决于边E和节点的数量，N并且具有不同的最佳和最坏情况值。您带有关键区域的代码已注释

def is_linked(friend_a, friend_b, visited = {}): # At worst, will call this N-1 times

    friends = friend_a.get_friends()

    # You can assume this method is O(1)
    if friends.contains(friend_b):
        return True

    visited[friend_a] = 1
    for friend in friends:

        # Prevents infinite recursion
        # Assume O(1)
        if friend in visited:
            next # At worst, this will happen N-2 times

        return is_linked(friend, friend_b, visited)

    del visited[friend_a]
    return False

绝对最坏的情况？O((N-1)(N-2))这是真的O(N^2)。如果您可以说您的图是稀疏连接的，那么您可以做得很好，O(N)因为这种if friend in visited: next情况很少发生。

于 2013-04-30T19:52:51.820 回答
1

如果两者if friend in visited都是friends.containsO(1)，那么函数作为一个整体必须是 O(n)；如果单个调用is_linked（假设没有递归）在恒定时间内完成（如果它所做的一切都在恒定时间内完成，则必须如此），那么递归调用的完成时间与发生的递归次数成线性关系，即必须检查才能找到链接的朋友数量。我没有能力对此进行数学证明，但请考虑：

a[friends] = [c, d, e]
b[friends] = [e, f, g]
[...]
e[friends] = [a, b]

在这种情况下，调用is_linked(a, b)将导致总共四个调用：

is_linked(a, b) # 原调用 is_linked(c, b, {a: 1}) is_linked(d, b, {a: 1, c: 1}) is_linked(e, b, {a: 1, c: 1, d: 1}) # 真

相似地：

a[friends] = [b, c]
b[friends] = [c, d]
c[friends] = [d, e]
d[friends] = [e]

调用 tois_linked(a, e)也会导致四个调用：

is_linked(a, e) # original call
is_linked(b, e, {a: 1})
is_linked(c, e, {a: 1, b: 1})
is_linked(d, e, {a: 1, b: 1, c: 1}) # True

同时：

a[friends] = [b, c, d, e, f, g]
[...]
g[friends] = []

结果有is_linked(a, g)六个电话，&c。这一切的重点是证明，如果不是证明的话，花在上面的时间is_linked与它必须检查的项目数量成线性关系。

我对 Python 的字典键查找 ( if friend in visited) 的实现不是很熟悉；一个简单的实现，作为一个跨键数组的线性搜索，将具有 O(n) 复杂度，导致我最初假设的 O(n^2) 复杂度is_linked。但是，据此，他们将其归结为“O(1) 的平均复杂度”。如果这是真的，那么is_linked确实是 O(n); 如果我怀疑可能是这种情况，实际上它更接近 O(log n)，那么is_linked应该是 O(n log n)，这仍然不是那么糟糕。

更新：dlp 指出其中有一个数组遍历（for friend in friends）is_linked，以及一个键查找。那次迭代总是 O(n)，这is_linked至少必然是 O(n^2)。（可以是 O(n^2 log n) 吗？家里有计算机科学家吗？我的意思是，我不是一个……）

于 2013-04-30T19:17:08.583 回答