[자료구조-01] 자료구조, 시간복잡도

1. 자료구조(data structure)

- 컴퓨터 과학에서 효율적인 접근 및 수정을 가능케 하는 자료의 조직, 관리, 저장

- 데이터 값의 모임, 데이터 간의 관계, 데이터에 적용할 수 있는 함수나 명령

- 자료구조를 선택한 후 알고리즘을 사용

 

자료구조의 종류

 

 

2. 시간복잡도(time complexity)

(1) 시간복잡도란?

- 알고리즘의 실행 시간 분석

+) 공간 복잡도(space complexity) : 알고리즘이 사용하는 기억 공간 분석

 

- 알고리즘의 절대적인 실행 시간 X

- 알고리즘을 이루고 있는 연산들이 몇 번 실행되는지 숫자로 표시 O

 

- 시간복잡도가 클수록 알고리즘의 실행이 오래 걸림

 

(2) 시간 복잡도 함수

- 연산의 개수를 입력의 개수 n의 함수로 나타낸 것

 

T(n)

T : 함수
n : 입력의 개수

 

(3) 빅오 표기법(big-oh notation)

- 시간 복잡도 함수에서 불필요한 정보를 제거하여 시간 복잡도를 쉽게 표시하는 방법

- 알고리즘이 n에 비례하는 실행시간을 가진다 = 시간 복잡도가 O(n)이다

- 시간 복잡도 함수 T(n)의 최고차항의 차수가 빅오가 됨

- O(n)은 "빅오 of n"이라고 읽음

 

자주 사용되는 빅오 표기법

 

ex)

 

함수	빅오 표기법
f(n) = 5	O(1)
f(n) = 2n + 1	O(n)
f(n) = 3n² + 1	O(n²)
f(n) = 5 * 2ⁿ + 10n² + 100	O(2ⁿ)

 

- 빅오 표기법 외에도 빅오메가 표기법, 빅세타 표기법이 있음

 

- 똑같은 알고리즘도 주어지는 입력의 집합에 따라 다른 실행시간을 보일 수 있음

 

① 최선의 경우(best case) : 실행시간이 가장 적은 경우

② 평균적인 경우(average case) : 알고리즘의 모든 입력을 고려하고 각 입력이 발생하는 확률을 고려한 평균적인 실행 시간

③ 최악의 경우(worst case) : 자료 집합 중에서 알고리즘의 실행 시간이 가장 오래 걸리는 경우

 

- 알고리즘의 실행 시간을 이야기할 때는 최악의 경우의 실행 시간을 사용함

 (평균 실행 시간은 광범위한 자료 집합에 대해서는 구하기 어려울 수 있기 때문)