algorithm
-
B+ Tree (B+ 트리)algorithm 2013. 6. 28. 17:41
개념 모든 레코드들이 트리의 최하위 레벨에 정렬되어 있고 트리 내부 블록에는 키들만 저장됨. 파일시스템 같은 블록기반 스토리지에서 저장데이터의 효율적인 검색에 유용함. 알고리즘 검색 Function: search (k) return tree_search (k, root); Function: tree_search (k, node) if node is a leaf then return node; switch k do case k < k_0 return tree_search(k, p_0); case k_i ≤ k < k_{i+1} return tree_search(k, p_i); case k_d ≤ k return tree_search(k, p_d); 삽입 1. 새 레코드를 삽입하기위한 검색을 수행 2. 노드..
-
Merge sort (병합정렬, 합병정렬, 머지소트)algorithm 2013. 6. 26. 18:31
알고리즘 1. 정렬되지 않은 리스트들을 원소가 1개인 하위리스트들로 나눔. 2. 분할된 하위리스트들을 합병하면서 새로운 하위리스트들을 만들고, 최종적으로 1개의 리스트로 합병함. 시간복잡도 최악 : O(n log n) 최선 : O(n log n) 평균 : O(n log n) 소스 import java.util.ArrayList; import java.util.List; public class MergeSort { /** * @param args */ public static void main(String[] args) { int nData = 16; //정렬할 데이터 개수 설정. double TargetDataList[] = new double[nData]; //데이터 생성 for(int i = 0; i..
-
Insertion Sort (삽입정렬)algorithm 2013. 6. 26. 15:30
알고리즘 입력된 리스트의 모든 원소를 앞부분부터 순서대로 비교하면서 적절한 위치에 삽입함. 시간복잡도 최악의 경우 : O(n^2) 번 비교와 위치변경 최선의 경우 : O(n) 비교와, O(1)번 위치변경 평균 : O(n^2) 비교 및 위치변경. 소스 public class InsertionSort { /** * @param args */ public static void main(String[] args) { int nData = 100000; //정렬할 데이터 개수 설정. double TargetDataList[] = new double[nData]; //데이터 생성 for(int i = 0; i < nData; i++) { TargetDataList[i] = Math.random(); System.o..
-
Quick Sort (퀵정렬, 퀵소트)algorithm 2013. 6. 5. 10:34
참조 1. http://ko.wikipedia.org/wiki/%ED%80%B5_%EC%A0%95%EB%A0%AC 2. http://en.wikipedia.org/wiki/Quicksort 3. http://codereview.stackexchange.com/questions/4022/java-implementation-of-quick-sort 시간복잡도 가장 나쁜 경우 : O(n^2) 가장 좋은 경우 : O(n log n) 평균 성능 : O(n log n) 장점 대부분의 경우에 빠르게 정렬이 가능. 단점 운이 없을때는 O(n^2) 만큼의 정렬 시간이 걸림. 알고리즘 1. 리스트에서 피봇(pivot)으로 사용할 원소를 선택 2. 리스트를 재정렬함. 이때 피봇보다 작은 값은 피봇 이전에 오게하고 피봇보다 ..
-
정렬 : Bubble Sort (버블정렬, 거품정렬)algorithm 2013. 5. 22. 10:47
참조 : http://en.wikipedia.org/wiki/Bubble_sort 시간 복잡도 가장 나쁜 경우 : O(n^2) 가장 좋은 경우 : O(n) 평균 성능 : O(n^2) 장점 구현이 단순함. 소스 public class BubbleSort { public static void main(String[] args) { int nData = 10;//정렬할 데이터 개수 설정. double TargetDataList[] = new double[nData]; //데이터 생성 for(int i = 0; i < nData; i++) { TargetDataList[i] = Math.random(); System.out.print(TargetDataList[i]+" ");//데이터 출력 } System.ou..
-
시간복잡도(Time Complexity) 정리algorithm 2013. 4. 18. 11:36
Time Complexity알고리즘의 시간복잡도(Time Complexity)란 함수가 입력된 값을 처리하는데 걸리는 시간을 측정한 값을 의미함.일반적으로 Big O 기호를 사용하여 표혐함.이때, 시간 복잡도의 입력값 크기는 점근적(asymptotically)으로 증가해서 결국 무한대까지갈 수 있음.시간 복잡도의 측정방법은 알고리즘이 수행하는 기본적인 연산이 몇 개 인지를 세어서 확인함. 표기기호Big O(O) : 상한(upper bound)을 의미함.Big Omega(Ω) : 하한(lower bound)을 의미함.Big Theta(Θ) : Big O 와 Big Omega가 같을 때를 의미함. 일반적인 시간복잡도 정리표명칭복잡도 수준실행시간(T(n))실행시간 예예제 알고리즘constant time(상수시..
-
알고리즘(algorithm) 개념 정리algorithm 2012. 12. 9. 10:30
알고리즘의 정의함수를 계산하기위해 잘 정의된 절차들의 유한한 목록으로 표현되는 효과적인 방법.계산을 위한 단계적 절차들. 알고리즘의 5가지 중요한 특징. 1) 유한성(finiteness)알고리즘은 단계들을 반드시 유한한 횟수로 거친 후에 종료해야 함.2) 명확성(definiteness)알고리즘의 각 단계는 반드시 명확하게 정의되어야 함.3) 입력(input)알고리즘은 0 또는 그 이상의 입력들을 가짐.4) 출력(output)알고리즘은 하나나 그 이상의 출력들을 가짐.5) 효과성(effectiveness)효과적이라는 말은, 이론적으로 알고리즘의 모든 연산들이 사람이 종이와 연필을 이용해서 유한한 시간 안에 정확하게 수행할 수 있을 정도로 충분히 단순해야 한다는 의미임. 참조 The Art of Comput..