Intro

자료구조

• 자료를 담는 추상적인 틀
• 컴퓨터의 자원이 한정적이기 때문에 제약된 조건내에서 최선의 결과를 내야 한다.
• 데이터의 형태와 쓰임에 가장 적합한 자료구조를 써야한다.

알고리즘

• 어떤 문제가 주어졌을 때, 문제를 풀기위한 동작 절차

점근 표기법

• 빅오 표기법 : 상한 점근
• 세타 표기법 : 상한/하한 점근
• 오메가 표기법 : 하한 점근

빅오(Big-O) 표기법

• 가장 큰 영향력이 있는 항만 표시 : O(N^3 + N^2 + N) -> O(N^3)
• 계수는 무시 : O(2N + 1) -> O(N)
• O(1) < O(logN) < O(N) < O(NlogN) < O(N^2) < O(2^N)

공간 복잡도

• 데이터 관리에 필요한 공간
• 데이터 양의 변화에 따른 공간의 변화
• 예상 소요 공간 측정

시간 복잡도

• 데이터 처리에 소요되는 시간
• 데이터 양의 변화에 따른 소요 시간의 변화
• 지연장애가 발생했을 때의 근거를 찾을 수 있다.
• O(1) : 입력 데이터의 크기와 상관없이 항상 일정한 시간이 걸리는 알고리즘 ( 배열의 random aceess, Hash )
• O(N) : 입력 데이터의 크기에 비례해서 시간이 소요되는 알고리즘 ( for 문 )
• O(logN) : 이진탐색 (Binary search)
• O(N^2) : 입력 데이터의 제곱에 비례해서 시간이 소요되는 알고리즘 ( 2중 for 문)
• O(NlogN) : Merge sort