컴퓨터하는 kimmessi

다익스트라 알고리즘 (Dijkstra's algorithm) 특정 노드에서 출발해 다른 모든 노드로 가는 최단 경로를 구해주는 알고리즘 다익스트라 알고리즘은 음의 간선이 있는 그래프에서는 사용이 불가능하지만 현실 세계에서는 음의 간선이 존재하지 않으므로 현실 세계에서 쓰기에 적합하다. 다익스트라는 그리디로 분류된다. 매상황 가장 비용이 적은 노드를 선택해 임의의 과정을 반복해준다. 동작 과정 1. 출발 노드를 설정해준다. 2. 최단거리 테이블을 초기화한다. 3. 방문하지 않은 노드 중 최단거리가 가장 짧은 노드를 선택한다. 4. 해당 노드에서 다른 노드로 가는 최단 거리 테이블을 갱신해준다. 5. 3번과 4번을 반복한다. 알고리즘 사례 위와 같은 그래프가 있다고 하자 출발점은 0이다. 이제부터 0번 노드..

마스터 정리 (Master Theorem) 재현식으로 표현된 알고리즘의 동작시간을 점근적으로 계산해 간단하게 계산하는 방법 $T(n) = a T( \frac{n}{b} ) + f(n) $이고 $ a>b>1, n$이 음수가 아닌 정수일 때, $$\begin{cases}T(n) \in \Theta (n^{\log _b a}) & \mathrm{if}\,\, f(n) \in O(n^{\log_b a- \epsilon }) \\ T(n) \in \Theta(n^{\log_b a} \log n) & \mathrm{if} \,\, f(n) \in O(n^{\lg _b a}) \\ T(n) \in \Theta(f(n)) & \mathrm{if} \;f(n) \in \Omega(n^{\log_b {a+\epsilon}..