*시간복잡도 공간복잡도를 다 까먹어서 간략하게 정리하기 위한 글이다. 기억 환기를 위한 글이므로 꼼꼼한 개념 설명보다는 문제에 맞닥뜨렸을 때 기억해내고 사용해내는데 목적이 맞추어져 있음
.
.
.
.
시간복잡도 : 알고리즘에서 연산이 몇번이나 진행되는가
공간복잡도 : 알고리즘에서 필요한 메모리가 얼마나 되는가
- 그리고 프로그래밍 문제를 보면 O(n), O(n^2) 등등 뭐 이렇게 짜라는 문제를 가끔 맞닥뜨린다. 이 표기법이 바로 빅오 표기법이다.
1. 시간복잡도
- 시간복잡도는 보통 n을 통해 나타낸다. n을 통해 나타나지 않는 건 O(1) 처럼 어떤 값을 넣든 걸리는 시간이 똑같은 프로그램이라고 생각하면 된다. 정확하지는 않지만 반복문이 몇번 돌아가게 되는가를 생각하면 편할 듯.
- n에 비례하기만 하면 모두 O(n)으로 나타낸다. 결국 O(4n) O(2n)모두 O(n)으로 나타낸다는 말
- O(n^2+n+1)=O(n^2)이다. 가장 큰 것만 가져온다.
- O(n^2)는 금방 생각해낼 수 있을 것 같다. 이중포문이 그 예시다. 바깥 포문이 한번 돌때 안의 포문이 n번 도므로 바깥 포문이 n번 돌면 n*n = n^2이 된다.
- O(logN)이 감이 안 잡혔을 때 봤던 거. 감사합니다.
(출처는 https://stackoverflow.com/questions/17122807/big-o-ologn-code-example)
while (x > 0) { x /= 2; }
This will be:
Iteration | x
----------+-------
0 | x
1 | x/2
2 | x/4
... | ...
... | ...
k | x/2^k
while문은 결국 longN번 반복되고 이것이 시간복잡도가 된다.
- 입력하는 데이터에 따라서 시간복잡도가 달라질 수 있다. 최선, 평균, 최악의 경우가 있는데 보통은 최악의 경우를 시간 복잡도의 척도로 삼는다. 평균적인 경우를 구하는건 너무 복잡하다.
ex)
최선의 경우 : 찾을려는 숫자가 맨 앞에 있을 때. O(1)
평균적인 경우 : 찾을려는 숫자는 모든 순서에 있을 수 있다. N개의 숫자가 있을 때 i번째 찾고자 하는 숫자가 있었다고 하자. 결국 Σ i (1부터 n까지) 가 된다. 이걸 평균하기 위해서 n으로 나누면 n+1/2가 된다. 결국 O(n+1/2)이므로 O(n)이다.
최악의경우 : 찾을려는 숫자가 맨 뒤에 있을 때. O(n)
2. 공간복잡도
- 공간복잡도는 얼마나 데이터가 쌓이게 되냐를 생각해 보면 된다. 배열을 입력한다면 그 배열의 크기인 O(n)이 공간복잡도가 되는 식이다. (2차원 배열이라면 O(n^2)...!)
- 그래서 결국 변수 하나를 통해서 값을 받아서 배열에 넣는다면 공간 복잡도가 O(n+1)이 된다.
- 재귀함수일때에도 공간복잡도를 따져줄 수 있다. 조금 복잡하지만 몇 번 재귀함수에 들어가는지를 따지면 금방 알 수 있게 된다.