[코딩 인터뷰 완전 분석] big-O

책 '코딩 인터뷰 완전 분석(게일 라크만 맥도웰)' 을 읽고 정리한 글입니다.

 

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이 서로 어떤 상관 관계가 있는지, 무엇이 더 지배적인지 모름