데이터 구조와 복잡도

데이터 구조

데이터 구조, data structure의 중요성

ds가 중요한 이유는 무엇인가?
-> 당연하지만 데이터 관리 때문이다.

ds를 잘 알고 있다면 적절한 데이터 구조를 선택해 응용 프로그램의 성능향상, 표준화, 가독성, 유지보수 등 적절하게 데이터 관리를 할 수 있게 된다.

데이터 구조는 크게 두가지의 구조로 나눌 수 있다.

1. 선형 자료 구조 (ex. linked list, array, vector, stack, queue ..)
2. 비선형 자료 구조 (ex. graph, tree, heap, priority queue, map, set ..)

위의 자료구조 내용들은 다음에 하나씩 더 자세하게 다루도록 하겠다.

복잡도

복잡도는 시간 복잡도와 공간 복잡도로 나뉜다.

복잡도가 필요한 이유는 무엇인가?
-> 코드를 개선하기 위한 척도이다.

1. 시간 복잡도
   

시간 복잡도란 입력 크기에 대해 어떤 알고리즘이 실행되는 데 걸리는 시간이다.

보통 O(빅오)표기법으로 나타낸다.
예를 들어 입력한 크기 n에 대해서 for문이 한번 돌아간다면 시간이 n만큼 들 것이다.
입력한 크기 n에 대해서 이중 for문이 돌아간다면 시간이 n^2만큼 들 것이다.
각각의 시간 복잡도를 O(n), O(n^2)이라고 할수 있다.

가장 영향을 많이 주는 항을 O안에 적어준다.
예를 들어 코드가 돌아가는데 필요한 시간이 n^2 + 10n 일 때 빅오 표기법으로 나타내면 O(n^2)이다.
입력이 커질수록 차수가 작은 항들은 영향이 작아지기 때문이다.

걸리는 시간 비교 : O(n^2) > O(n) > O(1)

1. 공간 복잡도
   

공간 복잡도란 코드를 실행시켰을 때에 필요로 하는 공간의 양을 말한다.

예를 들어:

int a[100];

위와 같은 배열이 선언되었다고 하면 a는 100 * 4 바이트의 크기를 갖게 된다.
이런 공간을 의미한다.

마무리:
데이터 구조의 중요성과 복잡도에 대해 공부해 보았다. 다음에는 선형 데이터 구조를 공부해보도록 하겠다.