코드스테이츠 47일차
오늘로 자료구조에 대한 스프린트가 모두 끝났다.
주말동안 정리해보면서 다음주에 있을 알고리즘, HA에 대비해야겠다.
새로 배운 것들
Time Complexity(시간 복잡도)
시간 복잡도는 컴퓨터가 데이터를 연산하는데 걸리는 시간을 표현하는 방법이다.
문제가 클 수록 컴퓨터가 연산하는데 시간이 많이 걸리게 되며
문제 해결에 걸리는 시간을 표현할 때에는 big-O Notation을 사용해 표현하며 big-O Notation은 최악의 상황을 고려해 표현하는 방식이다.
시간 복잡도를 표현하는 방법으로는 Big-Ω(최선의 경우), big-Θ(평균적인 경우)도 있다.
big-O에 비해 많이 사용하지 않기 때문에 있다는 것만 알아두면 된다
시간 복잡도의 표현
O(1)
문제의 크기가 크더라도 연산에 걸리는 시간이 일정한 경우이며 Constatnt Time이라고도 한다.
이 경우 연산을 단 한번만 하게 되는 경우이다.
대표적인 예시로는 배열에서 특정 인덱스를 찾거나 연결 리스트에서 값을 추가하거나 해시테이블에서 데이터를 추가하는 연산이 있다.
O(logn)
초반엔 문제해결에 걸리는 시간이 많이 걸리지만 시간이 지날수록
문제해결에 걸리는 시간이 점점 줄어드는 경우이며 Logarithmic이라고도 한다.
이런 시간 복잡도를 가지는 이유는 한번 순환을 한 이후
다음 순환 시에는 순환해야될 데이터의 경우의 수가 줄어들기 때문이다.
대표적인 예시로는 이진 탐색 트리가 있다. 다만 이진 탐색 트리에서 구조가 최악의 경우일 때 O(n)의 시간을 가질수도 있다.
이를 방지하기 위해 depth를 일정하게 유지시키게 만든다.
O(n)
문제 해결에 걸리는 시간이 일정하게 증가하는 경우이며 Linear라고도 한다.
대표적인 예시로는 연결 리스트에서의 검색, 삭제, 배열에서의 검색, 추가, 삭제, 반복문등이 있다.
O(n^2)
문제 해결에 걸리는 시간이 연산해야될 것들이 많아지면
처리 시간이 기하급수적으로 증가하는 경우이며 Quadratic이라고도 한다.
대표적인 예시로는 이중 반복문이 있다.
O(c^n)
최악의 시간 복잡도이며 문제 해결에 걸리는 시간이
처음부터 처리 시간이 기하급수적으로 증가하는 경우이며 exponential이라고도 한다.
이 경우는 최악의 경우이기 때문에 반드시 계산법의 수정이 필요하다.
대표적인 예시로는 피보나치 수열을 구하는 함수가 있다.
자료구조에 따른 시간 복잡도는 아래의 표와 같다.
보다 자세한 내용은 아래의 링크에서 볼 수 있다.
bigocheatsheet
알아둬야할 것들
- 알고리즘
