이 초보 그래프 검색의 최악의 시간 복잡도는 얼마입니까?

Question

나는 다른 친구에게 두 친구가 주어 졌을 때 친구가 친구라는 것을 의미하는 링크가 있으면 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 

이 알고리즘의 최악의 경우 시간 복잡도는 무엇입니까 :

이 사람이 작업을 한 후, 여기에 우리가 함께 제공되는 기본 알고리즘은? 우리는 각각 우리 자신의 대답을 생각해 냈습니다. 우리가 합의에 이르지 못했기 때문에 여기서 독립적으로 검증하기를 희망합니다.

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)입니다. 그래프가 희박하게 연결되었다고 말할 수 있다면 if friend in visited: next이 거의 발생하지 않기 때문에 O(N)만큼 좋은 결과를 얻을 수 있습니다.

Answer 2

if friend in visited과 friends.contains이 둘 다 O (1) 인 경우 함수는 전체적으로 O (n)이어야합니다. is_linked에 대한 단일 호출 (일정한 시간 내에 완료되는 모든 것이 완료되어야하는 것처럼 반복 시간이 일정해야 함)에 대한 단일 호출이 발생하면 재귀 호출이 완료되는 시간은 발생하는 반복 횟수에 따라 선형 적으로 조정됩니다 (즉, 링크를 찾기 위해 검사해야하는 친구의 수. is_linked

(A, B) # 원본 : 네 통화의 총 발생합니다 is_linked(a, b)를 호출,이 경우

a[friends] = [c, d, e] 
b[friends] = [e, f, g] 
[...] 
e[friends] = [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] 

is_linked(a, e)를 호출 515,

또한 네 호출 결과 : 한편

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에 소비 된 시간이 검사해야하는 항목의 수와 선형으로 비례 함을 입증하는 것입니다.

파이썬의 사전 키 조회 (if friend in visited) 구현에 익숙하지 않습니다. 키 배열을 통한 선형 검색으로 복잡성 O (n)을 갖게되어 원래는 is_linked으로 가정 된 O (n^2) 복잡성을 초래하게됩니다. 그러나 this에 따르면 그들은 "평균 O (1)의 복잡성"에 이르렀습니다. 그것이 사실이라면 is_linked은 실제로 O (n)입니다. 만약 내가 용의자로서, 실제로는 O (log n)에 가깝다면, is_linked은 O (n log n)이어야하고, 여전히 그렇게 나쁘지는 않습니다.

업데이트 : DLP는 is_linked의 배열 탐색 (for friend in friends)뿐만 아니라 키 조회가 있다고 지적한다. 그 반복은 언제나 O (n)이 될 것이므로 적어도 is_linked은 반드시 O (n^2)가 될 것입니다. (어떤 것이 O (n^2 log n) 일 수 있습니까? 어떤 컴퓨터 과학자가 집에 있습니까? 내 말은, 나는 하나가 아닙니다 ...)