알고리즘
-
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..
-
정렬 : 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..
-
알고리즘(algorithm) 개념 정리algorithm 2012. 12. 9. 10:30
알고리즘의 정의함수를 계산하기위해 잘 정의된 절차들의 유한한 목록으로 표현되는 효과적인 방법.계산을 위한 단계적 절차들. 알고리즘의 5가지 중요한 특징. 1) 유한성(finiteness)알고리즘은 단계들을 반드시 유한한 횟수로 거친 후에 종료해야 함.2) 명확성(definiteness)알고리즘의 각 단계는 반드시 명확하게 정의되어야 함.3) 입력(input)알고리즘은 0 또는 그 이상의 입력들을 가짐.4) 출력(output)알고리즘은 하나나 그 이상의 출력들을 가짐.5) 효과성(effectiveness)효과적이라는 말은, 이론적으로 알고리즘의 모든 연산들이 사람이 종이와 연필을 이용해서 유한한 시간 안에 정확하게 수행할 수 있을 정도로 충분히 단순해야 한다는 의미임. 참조 The Art of Comput..