ps:피보나치_힙
피보나치 힙
- 피보나치 힙을 처음 접하는 것은 보통 Dijkstra's algorithm이나 Prim's algorithm을 배울 때이다. 시간복잡도를 놀랍게 단축해 줄 수 있다고 전해진다.
- 일반적인 바이너리 힙과 달리, 삽입과 decrese-key 연산을 O(logn)이 아닌 O(1)에 처리할 수 있다고 한다
- 그러나 일반 수업이나 강좌에서 피보나치 힙을 구현시키는 경우는 아직 들어본 적이 없고, Dijkstra's algorithm이나 Prim's algorithm을 구현시킬 때도 바이너리 힙을 사용하게 한다.
- 이론적으로 빅오 복잡도는 바이너리 힙에 비해서 빠른게 맞지만, 앞에 붙는 상수가 너무 크기 때문에, 실질적으로 구현하게 되는 n의 범위에서는 바이너리 힙을 사용한 구현보다 느린것 같다.
- 시간날때 한번 실제로 테스트 해볼까..
- 파이썬으로된 구현은 이런 것들이 있는듯 하니, 써보는 데에 어려움은 없을 듯
ps/피보나치_힙.txt · 마지막으로 수정됨: 2020/12/11 14:57 저자 teferi
토론