O(|V|) 시간에 솔루션을 묻는이 질문의 많은 변형이 있습니다.adjecency list 표현이 주어지면 보편적 싱크를 찾는 시간 복잡도는 무엇입니까
그래프에 범용 싱크대가 있고 인접 목록에 그래프가있는 경우 계산하고 싶다면 최악의 경우는 무엇입니까? 이것은 다른 모든 알고리즘이 인접성 목록에 더 좋을 것 같기 때문에 중요합니다. 따라서 범용 싱크가 너무 자주 필요하지 않은 작업을 찾으면 필자는 매트릭스가 아닌 목록을 확실히 진행할 것입니다.
제 생각에 시간 복잡도는 그래프의 크기가 O(|V| + |E|)입니다. 그래프의 범용 싱크 (sink)를 찾는 알고리즘은 다음과 같다. 이웃리스트를 가정 할 때, 그래프의 인덱스 1에서 시작하십시오. 색인 1 (인접 라우터 목록의 길이가 |V| - 1) 인 지 확인한 다음 목록을 탐색하여 자체 루프가 있는지 확인하십시오. list에 자체 루프가없는 경우 and 다른 모든 정점은 목록의 일부이므로 목록 색인을 저장하십시오. 그런 다음이 목록이 목록에 포함되어 있는지 확인하기 위해 다른 목록을 검토해야합니다. 그럴 경우 저장된 정점을 범용 싱크가 될 수 없습니다. 다음 색인에서 검색을 계속하십시오. 리스트가 바깥 쪽리스트이더라도,리스트가있는 버텍스를 length = 0으로 검색하고, 다른 모든리스트를 검색하여이 버텍스가 각각의리스트에 존재하는지 확인해야합니다.
위의 설명에서 결론 지을 수 있듯이 어떤 형태의 인접성 목록이 고려 되더라도 최악의 경우 범용 싱크를 찾는 것은 모든 꼭지점과 가장자리를 한번 통과해야하므로 복잡성은 그래프의 크기입니다 즉, O (| V | + | E |)
최근에 조교수로 대학에 합류 한 내 친구는 O(|V|*|V|)이어야한다고 말했습니다. 나는 그가 봄에 코스를 가르치기 전에 그의 노트를 검토하고 있지만 교정하기 전에 나는 100 퍼센트 확신하고 싶다.