중독에 취약 중독에 취약

1. 개요 MST(Minimum Spanning Tree), MSF(Minimum Spanning Forst)를 얻기 위해 사용하는 탑욕법 기반의 알고리즘이다. 처음으로 제시된 것은 1926년에 Otakar Borůvka에 의해 고안된 알고리즘으로, 체코에 있는 Moravia의 전력망 건설을 효율적으로 하기 위한 방식으로 제안되었다. (꽤나 신기한 이유에 의해 고안된 알고리즘이라 생각된다. 사실 네트워크 연결이나... 전력망 연결이나... 거의 비슷한 느낌으로 연결하니까 그럴 법도 하다 생각된다.) 2. 과정 입력은 서로 연결된, 가중치가 존재하는 무향 그래프를 입력으로 받는다. 입력으로 받은 그래프의 정점들을 하나씩 forest T에 넣어 초기화한다. T 가 하나보다 많은 요소를 갖고 있을 경우(min..

1. 특징 순수하게 포인터에 기반한 자료구조이다. 배열은 사용되지 않으며 key는 수치적 가정에 기반하지 않는다. 자료구조의 heap order 속성을 지키기 위해 key는 결국 증가한다. 특정 키의 값을 인위적으로 올리는 방식을 통해 자료구조의 엔트로피를 낮춘다. 비교 기반 모델에서 로그 복잡도보다 나은 성능을 보인다. e값이 어떤 값인지에 상관없이 Soft heap은 비교 기반 모델에서 최적의 성능을 가진다. insert를 제외한 연산들의 armortized complexity는 $O(1)$이며 insert의 경우 에러율이 $\epsilon$일 때, $O(log 1/\epsilon)$이다. 에러율이 $\epsilon(0 next = tail, t..