자료구조(Data Structure)
자료구조는 효율적으로 데이터를 관리하고
수정, 삭제, 탐색, 저장할 수 있는
데이터의 집합을 말한다.
복잡도
복잡도는 시간 복잡도와 공간 복잡도로 나뉜다.
시간 복잡도
빅오 표기법
시간 복잡도란 '문제를 해결하는데 걸리는
시간과 입력의 함수 관계'를 가리킨다.
어떠한 알고리즘의 로직이 '얼마나 오랜 시간'이
걸리는지를 나타내는 데 쓰이며,
보통 빅오 표기법으로 나타낸다.
예를 들어 '입력 크기 n'의 모든 입력에 대한
알고리즘에 필요한 시간이
10n2 + n이라고 한다면 다음과 같은 코드를
상상할 수 있다.
빅 오 표기법이란 입력 법위 n을 기준으로 해서
로직이 몇 번 반복되는지 나타내는 것인데,
위의 코드의 시간 복잡도를 빅 오 표기법으로
나타내면 O(n2)이 된다.
'가장 영향을 많이 끼치는' 항의 계수를 없애고
나머지 항을도 없앤 것이다.
시간 복잡도의 존재 이유
시간 복잡도는 효율적인 코드로 개선하는데
쓰이는 척도가 된다.
시간 복잡도의 속도 비교
위의 그림처럼 O(1)과 O(n)은 입력 크기가
커질수록 차이가 많이 나는 것을 볼 수 있다.
O(n2)보다는 O(n), O(n)보다는 O(1)을
지향해야 한다.
공간 복잡도
공간 복잡도는 프로그램을 실행시켰을 때
필요로 하느 자원 공간의 양을 말한다.
정적 변수로 선언된 것 말고도 동적으로
재귀적인 함수로 인해
공간을 계속해서 필요로 할 경우도 포함한다.
예를 들어 이의 코드처럼 되어 있는 배열이
있다고 하면
a 배열은 1004 * 4 바이트의 크기를 가지게 된다.
공간 복잡도란 이런 것을 의미한다.
자료구조에서의 시간 복잡도
자료구조를 쓸 때는 이러한 시간 복잡도를
잘 생각해야 한다.
다음은 자주 쓰는 자료구조의 시간 복잡도를
나타내 것이다.
보통 시간 복잡도를 생각할 때 평균, 최악의
시간 복잡도를 고려하면서 사용한다.
다음은 자료구조의 평균 시간 복잡도를
나타낸 표이다.
다음은 자료구조의 최악 시간 복잡도를
나타낸 표이다.
<면접을 위한 CS 전공지식 노트>
