홍시홍의 프로그래밍

정렬의 하한은 결정트리로 증명할 수 있다. 3개의 자료를 정렬 할 때 나올 수 있는 경우는 3!으로 총 6가지이다. 이 말은 총 6가지 중 하나는 참인 경우가 존재한다는 것이다. 6가지 중 하나의 도착하는 시간은 결정 트리의 높이에 따른다 결정트리는 이진 트리로 이루어져 있으므로 총 n!의 리프트리를 가지고 있다 이 결정트리의 높이는 height = log n! n!는 stirling's formula(스털링 근사)정의에 의해 nlogn으로 정의될 수 있다 그러므로 H=nlogn이 될 수있고 비교정렬에서 최소의 시간 복잡도는 O(nlogn)이 된다. https://ict-nroo.tistory.com/57

특징 큐를 사용하여서 그래프안에서 연결된 최단 거리를 찾는 알고리즘이다. 너비가 넓어지는 형태로 탐색이 진행된다. 시간복잡도 인접 리스트로 구현 되었을 경우, O(V+E) 인접 행렬인 경우, O(V^2) 구현 방법 큐를 이용해 조건에 만족하는 정점을 큐에 넣어서 탐색을 진행한다. FIFO 형태로 앞 서 들어온 것을 먼저 탐색한다.

특징 다익스트라 알고리즘은 정점에서 정점까지의 최소 거리를 구하는 알고리즘이다 특징으로는 음의 간선을 포함하는 경우에는 계속 업데이트 되므로 최소 거리를 구할 수 없다. 이 경우는 다익스트라 알고리즘이 아닌, 벨만 포드 알고리즘으로 거리를 구한다. 사용하는 곳 인공위성, GPS, 네비게이션등 최단 거리를 구하고자 하는 곳에 사용된다. 시간 복잡도 다익스트라 알고리즘은 인접 행렬로 구현할 경우 O(N^2) 리스트인 경우 O(N*onN)이 된다 힙을 사용해야되기 때문이다. 구현방법 다익스트라는 1. 모든 정점까지의 거리를 무한대로 설정 2. 시작점 거리 0으로 초기화 3. Q에 삽입 4. 현재 정점과 연결 되있으며, 거리가 업데이트되는 경우 Q에 삽입 5. Q가 빌때까지 반복

1. 시간 복잡도 O(n^2) 바깥루프에서 n-1번 안쪽 루프에서 n-i번 2. 구현방법 0->n번째까지 i번재 로 작은 값을 찾아 앞에서 부터 채워준다. 3. 특징 비교 정렬이다 O(n^2)시간 복잡도를 가져 느리다 https://ko.wikipedia.org/wiki/%EC%84%A0%ED%83%9D_%EC%A0%95%EB%A0%AC