이 알고리즘의 시간 복잡도를 어떻게 예측 하시겠습니까?

Question

N = 정점 수 M = 방향성 그래프 G의 가장자리 수 . 인접리스트의 형태로 에지를 저장하고있다. 명확성을 위해, Oi는 정점 i의 아웃도 (outdegree)이고, Ii는 정점 i의 인디 (in-degree)라고 가정합시다. .

for each vertex i 
    for each vertex j in i's adj.list 
    //do some work 
    for each vertex k in j's adj.list 
     //do some work 

(가) "어떤 일을"본질적으로 (O (1)) 나는 N 시간을 실행하는 일반적인 표현을 유도 할 수없는 일정한 시간에 이루어집니다, 다음과 같이

알고리즘입니다 M. 다른 사람이 어떻게하는지 설명 할 수 있습니까? 여담으로

는 : 그냥 "나는 당신의 숙제를하지 않습니다"의견을 방지하기 위해, 나는의 텍스트 질문을 실천하고있어 (이 하나의 22.1-5) CLRS.I가 추정하는 방법에 대한 자세한 내용은이 뭐하는 거지에서 그래프 알고리즘의 시간 복잡성.

Answer 1

알고리즘에 언급 된 각 인접 목록이 나가는 가장자리 목록이라고 가정합니다. 대신 들어오고 나가는 모서리를 모두 참조하면 총 작업량에 O() 수준에 영향을 미치지 않고 4의 상수 요소가 곱해집니다.

for 문을 F1, F2, F3으로 말하면 F1 반복을 N 번합니다. F2는 번을 반복합니다. 여기서 Oi은 질문에서 언급 한 나가는 가장자리의 각도입니다. F2 패스 당 최대 N 회까지 F3 루프가 발생하며 최악의 경우에는 그보다 작은 하한이 없습니다. 이는 알고리즘 (즉, F1과 F2에서 O (M), F3에서 O (N))에 대해 O (M · N) 시간을 유도합니다.