알고리즘 개념[기초] - 시간, 공간복잡도

참고 유튭 영상

시간복잡도(Time Complexity)

• 입력의 크기와 문제를 해결하는데 걸리는 시간의 상관관계

빅오표기법(Big-O Notation)

• 주어진 식을 값이 가장 큰 대표향만 남겨서 나타내는 방법.

O(N) : 5N + 3, 2N + 10lgN, 10N
O(N^2) : N^2 + 2N + 4, 6N^2 + 20N + 10lgN
O(NlgN) : NlgN + 30N + 10, 5NlgN + 6
O(1) : 5, 16, 36

시간복잡도를 알아내는 방법

• O(N)

• O(N^2)

• O(√N)

• O(lgN)
• N이 2^k ~ 2^k+1 인 경우, 결국, N 이하의 수는 K이므로, O(K)가 되고, K 값은 log로 나타내면, lgN 이므로, 시간 복잡도는 lgN이 됩니다.

공간 복잡도(Space Complexity)

• 입력의 크기와 문제를 해결하는데 필요한 공간의 상관관계.

기억할 점

• 512MB = 1.2억개의 int