[기술면접] 자료구조 | 시간복잡도와 공간복잡도
💡 시간복잡도와 공간복잡도란 무엇일까?
시간 복잡도는 얼마나 빠르게 실행되는지(응답에 걸리는 시간),
공간 복잡도는 메모리 공간이 얼마나 필요한지(얼마나 많은 자원을 쓰는지)를 판단하는 지표이다.
시간 복잡도와 공간 복잡도는 반비례하는 경향이 있어, 보통 알고리즘의 성능을 판단할 때는 시간 복잡도를 위주로 판단하게 된다.
보다 전문적인 용어 쓰기 :
시간복잡도: 알고리즘이 실행될 때 필요한 ‘입력 값’과 ‘연산 수행 시간’에 따라 효율적인 알고리즘을 나타내는 척도를 의미한다.
공간복잡도: 알고리즘이 실행될 때 필요한 ‘메모리 공간의 양’을 의미합니다.
빅오 표기법
‘빅오 표기법(Big-O notation)’를 통해 표현하며 수치가 작을수록 효율적인 알고리즘이다.
최악인 경우의 시간 복잡도를 나타내며, 상수값은 지우고 단순화하여 표현하므로 정확한 값을 나타내지는 않는다.
최악인 경우의 시간 복잡도 = 어느 정도의 실행 속도를 보장함을 나타내는 것이고 지표로써 활용된다.
어떤 알고리즘을 선택할 때는 시간복잡도(우선고려)와 공간 복잡도를 모두 최악의 경우를 고려하여 선택한다.
- 시간 복잡도가 작은 알고리즘을 선택하면, 입력값이 매우 커졌을 때도 더 빠른 실행 시간을 보장할 수 있다
- 또한 입력 크기가 작을 때는 차이가 미미하지만 크기가 커질수록 차이는 크게 벌어진다고 한다
정렬 알고리즘에서의 시간 vs 공간복잡도
참고 :
https://adjh54.tistory.com/186