책 '코딩 인터뷰 완전 분석(게일 라크만 맥도웰)' 을 읽고 정리한 글입니다.
big-O
시간의 상한. 상한 또는 평균을 의미한다.
대개는 상한을 의미하는데, 간혹가다가 평균을 의미할 때도 있다.
공간 복잡도
공간(메모리)을 얼마나 사용하느냐를 의미한다.
모든 변수들이 사용될 때 사용하는 메모리를 측정해야하는건가? 하는 혼선이 생길 수 있다.
→ No. 그런걸 얘기하지는 X
동시에 사용되는 메모리만 측정한다.
책에서는 factorial에 대한 예를 들었다.
호출될때마다 재귀가 되기 때문에, sum3을 실행될 시점에 sum4가 아직 끝나지 않음
콜 스택이 계속 쌓인다.
결국은, 공간이 가장 많이 사용되는 시점의 공간 복잡도가 얼마인지를 얘기하는 것.
예제 및 연습 문제 (책 69p)
예제 1.
같은 길이의 for 문 2번 순회 → O(n)
∵ O(A + B) = O(N)
예제 2.
O(N) 시간이 걸리는 루프 * n번 반복 = O(N^2)
∴ O(N^2)
예제 3.
i = 0일 때 → j = 1 ~ n 순회 ⇒ n번 돎
i = 1일 때 → j = 2 ~ n 순회 ⇒ n-1 번 돎
i = 2일 때 → j = 3 ~ n 순회 ⇒ n-2 번 돎
…
i = n일 때 → j = n-1 ~ n 순회 ⇒ 1번 돎
각 i의 값마다 돈 횟수 더하기
n + (n - 1) + (n - 2) + … + 1 = n(n + 1) / 2
⇒ O(N(N + 1) / 2)
= O(N(N + 1))
= O(N^2 + N)
= O(N^2)
∴ O(N^2)
예제 4.
맨 안쪽의 if문은 바로 판별이 나기 때문에 O(1)시간이 걸려서 없는 취급해도 됨
arrayA의 길이를 A, arrayB의 길이를 B라고 했을 때,
arrayA의 원소마다 arrayB의 길이만큼 반복하기 때문에 ⇒ A*B ⇒ 걸리는 시간은 O(AB)
∴ O(AB)
예제 5.
O(10000AB) = O(AB)
∴ O(AB)
예제 6.
O(N / 2) = O(N)
∴ O(N)
예제 7.
- O(N + P)O(N + P) = O(N + N/2) = O(3N / 2) = O(N)
- P를 N / 2 라고 치환
- O(2N) = O(N)
- O(N + logN)그래서 O(N)
- 책 66페이지 그래프를 보면 O(logN)은 O(N)보다 훨씬 더디게 증가함
- O(N + M)그래서 O(N + M)
- N과 M이 서로 어떤 상관 관계가 있는지, 무엇이 더 지배적인지 모름
