자료구조5 검색 알고리즘 package search [ 검색에 사용될 기본 페킷 ]class _Set_Search [ 데이터를 산출하는 클래스 ] /*** * _Set_Search( int Data_su ) // 정수형의 크기만큼 배열을 생성한다. * _Data_Init() // 배열에 랜덤값을 넣는다. * _Data_Sort() // 퀵정렬을 이용 데이터를 정렬한다. * _Set_Key() // 검색할 값을 입력받는다. *_Show_Data() // 배열의 값을 화면에 보여 준다. ***/ import java.util.Scanner;public class _Set_Search extends java.util.Random { public int Data_len ; public int[] nDate ; public int Hei.. 2013. 6. 7. SQRT의 최적화 속도가 느린 sqrt를 다양한 알고리즘으로 구현하여 테스트해 보았습니다. 1) ASMsqrt : FPU를 이용한 어셈코드__forceinline float ASMsqrt(float src) // FPU { float t; _asm { fld src; fsqrt; fstp t; } return t; } 2) fSQRT : GPG 책에 나오는 알고르즘#define SQRTTABLESIZE 256 /* Note: code below assumes this is 256. */ unsigned int ZSQRTTABLE[SQRTTABLESIZE] = { 531980127, 532026288, 532072271, 532118079, 532163712, 532209174, 532254465, 532299589, 53.. 2013. 5. 21. 알고리즘 관계복잡도 Big-O Complexity ChartExcellentGoodFairBadHorribleO(1), O(log n)O(n)O(n log n)O(n^2)O(2^n)O(n!)OperationsElementsKnow Thy Complexities!Hi there! This webpage covers the space and time Big-O complexities of common algorithms used in Computer Science. When preparing for technical interviews in the past, I found myself spending hours crawling the internet putting together the best, average, and wor.. 2013. 5. 14. 해시테이블 자료구조 : 해시테이블 (Hash Table) 해시(Hash)는 키 값을 해시 함수(Hash function)으로 해싱하여 해시테이블의 특정 위치로 직접 엑세스하도록 만든 방식이다. 키 값을 통해 직접 엑세스하기 위해서 모든 가능한 키 값을 갖는 배열을 만들면, 배열크기가 엄청나게 커지게 된다. 예를 들어, 주민등록번호를 키 값으로 하는 경우, 000000-0000000 부터 999999-9999999까지 10의 13승의 배열 공간이 필요한데, 만약 회원수가 1000명인 경우, 1000명을 저장하기 위해 10^13의 엄청난 배열 공간이 필요하게 된다. 이렇게 낭비되는 공간을 줄이기 위해 해시 함수를 사용하게 되는데, 이 함수는 적은 공간 안에서 모든 키를 직접 찾아갈 수 있도록 해준다. 하지만 경우에 따.. 2013. 4. 25. 이진검색트리 자료구조 : 이진검색트리 (Binary Search Tree) 이진트리(Tree)의 특수한 형태로 자주 사용되는 트리로서 이진검색트리 (Binary Search Tree)가 있다. 이진검색트리는 이진트리의 모든 속성을 가짐과 동시에 중요한 또 하나의 속성을 가지고 있는데, 그것은 특정 노드에서 자신의 노드보다 작은 값들은 모두 왼쪽에 있고, 큰 값들은 모두 오른쪽에 위치한다는 점이다. 또한 중복된 값을 허락하지 않는다. 따라서 전체 트리가 소트되어 있는 것과 같은 효과를 같게 되어 검색에 있어 배열이나 이진트리처럼 순차적으로 모든 노드를 검색하는 것(O(n))이 아니라, 매 검색마다 검색영역을 절반으로 줄여 O(log n)으로 검색할 수 있게 된다. 하지만 노드들이 한쪽으로 일렬로 기울어진 Skewed .. 2013. 4. 25. 이전 1 다음