자료구조와 알고리즘 기초 ( 공간 복잡도, 시간 복잡도, 빅오 표기법 Big-O)

컴퓨터의 자원은 한정적이므로 제한된 제약조건 내에 정확한 결과를 내야한다.

그렇기에 데이터의 형태와 쓰임에 가장 적합한 자료구조를 쓰는 것은 매우 중요하다.

 

자료 =(data) 자료구조=(data structure)

자료(데이터)를 어디에 어떻게 관리할지

-> 검색, 순회(iterate) , 저장, 삭제, 변경

 

자료구조의 특징

각각의 자료구조의 장점과 한계가 존재한다.

 

알고리즘

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

 

 

빅오 표기법

예시) 집에서 학교까지 가는 방법

버스, 지하철, 걸어서 가는 방법 등 여러가지 방법등이 있는데 빅오 표기법은 여러가지 방법들을 시간과 공간적 방면에서 비교할 수 있게 해준다.

 

점근 표기법

1. 빅오(Big-O) 표기법( 상한 점근)

2. 세타 표기법( 상한/하한 점근)

3. 오메가 표기법(하한 점근)

 

BIG-O의 특징

시간 복잡도 크기 비교

공간 복잡도

데이터 관리에 필요한 공간

 

데이터 양의 변화에 따른 공간의 변화

예상 소요 공간 측정

 

 

시간 복잡도

데이터 처리에 소요되는 시간

데이터 양의 변화에 따른 소요 시간의 변화

예상 처리 시간을 측정

지연 장애가 발생했을 때 왜 발생했는지를 찾을 수 있는 근거

 

O(1)

입력 데이터의 크기와 상관없이 항상 일정한 시간이 걸리는 알고리즘

case:

배열의 Random Access

Hash function

 

O(N)

입력 데이터의 크기에 비례해서 시간이 소요되는 알고리즘

case:

for 문

 

 

O(N∧2)

입력 데이터의 제곱에 비례해서 시간이 소요되는 알고리즘

case:

이중 for문

 

O(logN)

이진 탐색(Binary search) (업다운 게임이라고 생각하면 편함)

한번 계산이 될때 마다 데이터의 양이 절반씩 줄어드는 formular가 O(logN)의 시간 복잡도를 가진다.

 

K번 시행을 할때 logN의 시간 복잡도를 가진다.

 

 

O(NlogN)

case:

Merge sort

절반씩 데이터를 나누고 나눈 값을 비교하여 정렬한다.