python - 这个基本图搜索的最坏情况时间复杂度是多少？

Question

有一天，我被要求编写一个基本方法，当给定两个 friend 时，如果他们有联系，则返回 true(我的意思是他们是 friend 的 friend 的 friend )，如果他们是 friend ，则返回 false不相关(他们的 friend 列表中没有人有联系)。

与此人合作后，我们得出了以下基本算法:

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

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

Answer 1

我要把我的答案公布出来。我认为 Breadth-first search 涵盖了维基百科上的文章表明它实际上取决于边 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) 一样好的结果，因为 iffriend invisited: next 很少会发生。