반응형 자료구조3 DataBase Index에서 기본적으로 HashTable이 아닌 B-Tree를 쓰는 이유 의문의 시작 해시 테이블은 삽입, 삭제, 탐색 시 평균적으로 O(1)의 시간복잡도를 가지는 좋은 성능의 자료구조인데 DateBase에서 Index로 사용안하는지 갑자기 의문이 생겼다. 지금 생각해보면 조금만 고민하면 답을 찾을 수 있는데 왜 안보였는지... 서치를 해보니 나와 같은 의문점을 가진 사람들이 꽤 있어서 자료가 찾기 편했다. 바로 알아보자! 자료구조 비교 HashTable HashTable이란 Key와 Value로 데이터를 저장하는 자료구조 중 하나로써, 데이터의 삽입, 삭제, 탐색에 평균적으로 O(1)이라는 빠른 성능의 시간복잡도를 자랑하는 자료구조이다. HashTable의 프로세스를 알아보면, 검색하고자 하는 키값을 입력받아서 해시함수를 통해 반환받은 HashCode를 배열의 Index로 .. 2023. 1. 9. Big-O 표기법과 처리속도에 관하여 Big-O는 알고리즘의 성능을 수학적으로 표현해주는 표기법이다. 이것으로 알고리즘의 시간과 공간 복잡도를 표현할 수 있다. 시간과 공간 복잡도의 표현을 통해 정확한 알고리즘 시간을 산출하기보다, 데이터나 요청의 증가율에 따른 성능을 예측하는 것을 목표로 한다. Big-O 표기법을 알바오자. 먼저, 첫번째로 O(1)알고리즘이 있다. 이 알고리즘은 입력데이터의 크기와 상관없이 일정한 시간이 걸리는 알고리즘을 말한다. 위의 예와 같이 어떠한 데이터가 들어와도 동일한 시간이 걸리는 것을 보증한다. 이러한 경우를 O(1) 시간복잡도를 가진다고 표현한다. 그래프로 표현하면 아래와 같다. 두번째로, O(n)알고리즘이 있다. O(n)알고리즘은 입력 데이터의 크기에 비례해서 처리시간이 걸리는 알고리즘을 표현한다. 위의 .. 2021. 8. 16. 자료구조 : 자바로 스택(Stack) 구현하기 스택이란 무엇인가. 위와 같이 한쪽이 막혀있는 형태의 자료구조로 생각하면 된다. 따라서 데이터의 삽입과 삭제가 스택구조에서 제일 꼭대기인 "TOP"에서만 이루어 진다. 이러한 특성때문에 제일 처음 들어온 데이터가 제일 마지막으로 출력되며 이것을 First In Last Out => FILO라고 표현하기도 한다. 자바로 구현하기 앞서 객체를 정의해보자. 1. Stack 이라는 객체가 있다. Stack은 "TOP" 즉, 꼭대기의 값을 기억하는 특성이 있다. 그리고 값을 삽입하는 push, 값을 출력하는 pop, 비어있는지 확인하는 isEmpty라는 세 가지 행위를 할 수 있다. 2. Stack 안에는 값을 기억하는 Node라는 객체가 있다. Node의 특성으로는 값을 가지며, 본인보다 바로 아래의 노드의 주.. 2020. 12. 21. 이전 1 다음 반응형
