시간 복잡도와 공간 복잡도는 알고리즘 성능을 판단하는 지표입니다.
그렇다면 알고리즘 성능 분석은 왜 필요할까요?
알고리즘 성능 분석의 필요성
프로그램의 규모는 시간이 지날수록 방대해지고 있습니다. 즉, 처리해야하는 데이터의 양이 많아진다는 것입니다.
입력하는 데이터의 양이 적은 경우에는 크게 신경쓰지 않아도 상관이 없을 수 있지만 그 양이 많아지면 알고리즘 간의 효율성 차이는 커질 수 밖에 없습니다.
효율적인 알고리즘이란,
알고리즘이 수행을 시작하여 결과가 도출될 때까지 실행에 걸리는 시간이 짧고 연산하는 컴퓨터 내의 메모리와 같은 자원을 덜 사용하는 것이 효율적이라고 할 수 있습니다.
시간 복잡도
시간 복잡도는 알고리즘의 절대적인 실행 시간을 나타내는 것이 아닌 알고리즘을 수행하는데 연산들이 몇 번 이루어지는 지를 숫자로 표기합니다.
여기서 연산이란 산술, 대입, 비교, 이동을 이야기합니다.
여기서 연산의 실행 횟수는 입력한 데이터의 개수를 나타내는 n에 따라 변하게 됩니다.
빅오(BIG-O) 표기법
빅오 표기법이란, 시간 복잡도 함수에서 상대적으로 불필요한 연산을 제거하여 알고리즘의 분석을 조금 더 간편하게 할 목적으로 시간 복잡도를 표기하는 방법입니다.
공간 복잡도
공간 복잡도는 프로그램을 실행시킨 후 완료하는 데 필요로 하는 자원공간의 약을 말합니다.
요약
시간 복잡도는 "얼마나 빠르게 실행되느냐", 공간 복잡도는 "얼마나 많은 자원을 필요로하느냐"를 의미합니다.
여기서 말하는 좋은 알고리즘이란 "빠르게 실행되며, 적은 자원을 필요로하는 알고리즘"을 의미 할 것입니다.
하지만, 시간과 공간은 반비례적인 경향이 있기에 알고리즘의 척도는 시간 복잡도를 위주로 판단합니다. 아무래도 현대에는 메모리의 공간이 넉넉한 경우가 많기 때문에 시간 복잡도 위주로 판단하는 것이라고 생각합니다.
Reference
