프림알고리즘과 nearest 의 역할에 대해서...
갤투
2023.04.01
질문 제목 : 프림알고리즘과 nearest 의 역할에 대해서 궁금한게 있어요질문 내용 : 프림알고리즘(최소 신장 트리 구할 때 쓰는 알고리즘)에서 nearest라는 배열이 있더라고요 이 알고리즘을 수행하고 나면 어떤 vertex와 vertex가 연결이 되었는지 파악할 수 있게 nearest 배열이 완성이되던데요
e.g) nearest[1]=2 =vertex 1과vertex 2를 이어야지최소신장트리를 구성할 수 있다. 라는 뜻;
그런데 제가 학교에서 강의를 들어보니까 교수님께서 이 nearest 배열을 쓰지 않으면 o(n^3) 이 된다고 하셨어요
nearest를 쓰면 o(n^2) 이 된다고 하시구요...
그런데 제가 아무리 코드를 분석해 봐도 nearest 라는 배열은 시간복잡도에는 영향을 미치지 않고 그저 vertex와 vertex의 연결만을 나타내는 단순한 데이터 저장의 역할만하던데 말이죠;;
제가 잘못 알고 있는 건가요?....
그렇다면 간단하게라도 왜 nearest배열이 시간복잡도를 줄이는데 필요한지 알려주셨음 좋겠어요!
읽어주셔서 감사합니다
