longbeom

복잡도 시간 복잡도와 공간 복잡도로 나뉜다. 빅오 표기법 시간 복잡도란 '문제를 해결하는 데 걸리는 시간과 입력의 함수 관계'를 가리킨다. 알고리즘의 로직이 '얼마나 오랜 시간'이 걸리는지를 나타내는 데 쓰이며, 보통 빅오 표기법으로 나타낸다. 다음 코드는 '입력 크기 n'의 모든 입력에 대한 알고리즘에 필요한 시간이 10n^2 + n이라고 했을 때의 내용이다. for (int i = 0; i < 10; i++) { for (int j = 0; j < n; j++) { for (int k = 0; k < n; k++) { if (true) cout

조인 하나의 테이블이 아닌 두 개 이상의 테이블을 묶어서 하나의 결과물을 만드는 것을 말한다. MySQL에서는 JOIN, MongoDB에서는 lookup이라는 쿼리로 처리한다. MongoDB에서는 조인 연산에 대해 관계형 데이터베이스보다 성능이 떨어지기 때문에 사용을 지양한다. 따라서 여러 테이블을 조인하는 작업이 많은 경우 MongoDB보다는 관계형 데이터베이스를 써야 한다. 내부 조인 (inner join) 왼쪽 테이블과 오른쪽 테이블의 두 행이 모두 일치하는 행이 있는 부분만 표기한다. SELECT * FROM TableA A INNER JOIN TableB B ON A.key = B.key 왼쪽 조인 (left outer join) 왼쪽 테이블의 모든 행이 결과 테이블에 표기된다. 테이블 B의 일..

인덱스의 필요성 인덱스는 데이터를 빠르게 찾을 수 있는 하나의 장치이다. 책의 색인과도 같다. B-트리 인덱스는 보통 B-트리 자료구조로 이루어져 있다. 이는 루트 노드, 리프 노드, 그리고 루프와 리프 사이의 브랜치 노드로 나뉜다. 트리 탐색은 맨 위 루트 노드부터 탐색이 일어나며 브랜치 노드를 거쳐 리프 노드까지 도달해서 해당 데이터가 가리키는 데이터 포인터를 통해 결괏값을 반환하게 된다. 인덱스가 효율적인 이유와 대수확장성 인덱스가 효율적인 이유는 효율적인 단계를 거쳐 모든 요소에 접근할 수 있는 균형 잡힌 트리 구조와 트리 깊이의 대수확장성 때문이다. 대수확장성이란 트리 깊이가 리프 노드 수에 비해 매우 느리게 성장하는 것을 의미한다. 기본적으로 인덱스가 한 깊이씩 증가할 때 마다 최대 인덱스 항..