자료구조 복잡도

자료구조는 효율적으로 데이터를 관리하고 수정,삭제,탐색,저장할 수 있는 데이터 집합을 말한다.

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

시간 복잡도

시간 복잡도란 ‘문제를 해결하는 데 걸리는 시간과 입력의 함수 관계’를 가리킨다.

어떠한 알고리즘의 로직이 ‘얼마나 오랜 시간’이 걸리는지를 나타내는 데 쓰이며, 보통 빅오표기법으로 나타낸다.

빅오 표기법이란 입력 범위 n을 기준으로 해서 로직이 몇 번 반복되는지 나타내는 것이다.

‘가장 영향을 많이 끼치는’ 항의 상수 인자를 빼고 나머지 항을 없앤 것이다.

입력 크기가 커질수록 연산량이 가장 많이 커지는 항은 n은 제곱항이고, 다른 것은 그에 비해 미미하므로 가장 큰 값만 고려하면 된다.

시간 복잡도는 효율적인 코드로 개선하는 데 쓰이는 척도가 된다.

예를들어, 로직이 O(n^2)의 시간 복잡도를 가지고 9초 걸릴경우 O(n)의 시간 복잡도를 가지는 알고리즘으로 개선하면 3초로 줄어들게 된다.

O(1) -> O(logn) -> O(n) -> O(nlogn) -> O(n^2) -> O(2^n) -> O(n!) 순서대로 속도가 느려진다.

상수 함수 -> 로그 함수 -> 선형 함수 -> 다항 함수 -> 지수 함수 -> 재귀 함수

공간 복잡도는 프로그램을 실행시켰을 때 필요로 하는 자원 공간의 양을 말한다.

정적 변수로 선언된 것 말고도 동적으로 재귀적인 함수로 인해 공간을 계속해서 필요로 할 경우도 포함된다.

시간 복잡도를 생각할 때 평균, 그리고 최약의 시간 복잡도를 고려해야한다.

Big-O 표기법별 대표 알고리즘이다.