Home

0

Quick sort algorithm

퀵 정렬 알고리즘퀵 정렬은 피벗을 기준으로 좌/우에 자신보다 큰/작은 값을 몰고, 문제를 조금씩 나눠가며 정렬을 하게 된다. 최악의 경우(항상 피벗이 모든 값 중 가장 작은 경우) O(n^2)를 가지는 상황이 나올 수 있지만, 확률적으로 그럴 일은 적기에 평균적으로 O(NlogN)의 시간복잡도를 가진다. 구현123456789101112131415161718

0

Dijkstra Algorithm

다익스트라 알고리즘Dijkstra algorithm(이하 다익스트라 알고리즘)은 음의 가중치가 없는 그래프에서 한 노드에서 다른 모든 노드까지의 가장 짧은 거리를 구하는 알고리즘 중 하나이다. 선형구조로 구현된 다익스트라 알고리즘은 O(N^2)의 시간복잡도를 가지지만 힙을 이용해 구현하게 되면 O(NlogN)의 시간복잡도를 가지게 된다. 최단 거리를 구하는