이런 이유로 우리는 기본 연산(산술/ 비교...)이 몇번 실행되는지를 통해서 측정하게 된다.
다만 이 경우 또한 입력 데이터에 따라서 달라진다.
예를 들어서 정렬 알고리즘의 기본연산 횟수를 세어보려고 한다.
극단적으로 생각해서, 입력으로 들어오는 값이 이미 정렬된 채로 들어오는 경우가 있을 수 있다.
반대로 정렬과 완전히 반대 상태로 들어올 수도 있다. 이 두 경우의 기본 연산 횟수는 동일하지 않을 것이다.
이런 문제를 해결하기 위해서 알고리즘의 실행시간을 분석할 때는 점근적인 방식을 통해서 이야기한다.
그래서 뭘 점근적으로 볼거냐? 세가지 정도를 점근적으로 표기하여 사용한다.
최악의 경우 (O - notation)
최선의 경우 (Omega - notation)
최악=최선의 경우 (Theta - notation)
빅 오 표기법
빅 오 표기법(O- notation)은 알고리즘에서 최악의 경우 실행시간을 나타낸다.
즉, 입력의 크기가 n일 때, 알고리즘의 기본 연산의 횟수 f(n)의 상한선을 나타낼 때 빅 오 표기법으로 나타낸다.
빅 오의 정의는 아래의 슬라이드를 참고하자.
오메가 표기법
오베가 표기법은 알고리즘에서 최선의 경우 실행시간을 나타낸다.
입력의 크기가 n일때 알고리즘의 기본 연산의 횟수 f(n)의 하한선을 의미한다.
오메가 표기법의 예시는 아래와 같다
세타 표기법
세타 표기법은 알고리즘에서 빅 오와 오메가 표기법의 교집합을 의미한다. 따라서 실행시간에 대하여 좀 더 정확한 예측을 수행할 수 있다.
시간복잡도
다만 대부분의 경우 우리는 최악의 경우를 두고 알고리즘을 평가하게 된다. 오메가가 낮아도, 빅오가 클 수도 있는 것이다. 이런 이유로 주로 알고리즘의 시간복잡도에 대해서 이야기 할 때 우리는 빅 오 표기법을 사용한다.
공간 복잡도
알고리즘의 실행 시간 뿐만 아니라, 알고리즘이 메모리를 얼마나 사용하는지에 대한 척도도 알고리즘의 효율성 평가에 중요한 부분이다.
이렇게 알고리즘의 메모리 사용량에 대한 표기를 우리는 공간 복잡도 라고 부른다.
이는 입력의 크기 n에 따라서 알고리즘이 사용하는 메모리의 양을 말한다.
이 또한 최악의 경우를 고려하는것이 합리적이므로 빅 오 표기법을 일반적으로 활용한다.
Trade Off
시간복잡도와 공간복잡도는 트레이드 오프 관계에 있다.
시간 복잡도를 개선하면 공간 복잡도에서 효율이 나빠지는 것이다. 예를 들면 다음과 같은 알고리즘을 생각할 수 있다.
메모이제이션을 사용하는 경우 DP와 같은 알고리즘에서 중복 계산을 피하기 위해 이미 계산한 값을 메모리에 저장하여 사용하는 것을 말한다. 이 경우 중복 계산을 피해 시간 복잡도를 줄이게 되지만, 공간복잡도는 증가한다.
재귀 호출 재귀 호출이 길어지게 되면 스택의 사용으로 메모리를 많이 사용하게 되지만, 일부 알고리즘에서는 반복문 보다 빠른 시간에 문제를 해결한다.
퀴즈
최선, 최악, 평균 경우의 시간 복잡도가 각각 무엇을 의미하는지, 구체적인 예를 들어 설명하세요.
최선의 경우: 알고리즘이 가장 빨리 끝날 수 있는 시나리오. 입력 n에 대해서 알고리즘 실행 시간의 점근적인 upper bound 를 의미한다
최악의 경우: 알고리즘이 가장 느리게 동작하는 시나리오. 입력 n에 대해서 알고리즘 실행 시간의 점근적인 lower bound 를 의미한다
평균의 경우: 일반적인 상황에서의 시간 복잡도. 입력 n에 대해서 알고리즘 실행 시간의 점근적인 tight bound 를 의미한다
예를 들어 insertion sort 알고리즘을 살펴보자
시간 복잡도와 공간 복잡도를 설명한 뒤, 특정 알고리즘을 예시로 들어 두 개념 간의 트레이드오프(trade-off)가 발생하는 상황을 설명하세요.
(1) 시간 복잡도
(2) 공간 복잡도
(3) 트레이드 오프 관계 설명
(4) 예시 - 메모이제이션, 머지소트 // 재귀호출
시간 복잡도는 알고리즘이 실행되는 데 걸리는 시간의 상한선을 나타내며, 공간 복잡도는 알고리즘이 사용하는 메모리의 양을 나타냅니다. 두 개념은 종종 트레이드오프 관계에 있습니다. 더 적은 시간을 사용하기 위해 더 많은 메모리를 사용하거나, 반대로 메모리 절약을 위해 시간이 더 오래 걸리는 경우가 있습니다.
예시: 병합 정렬(merge sort)의 시간 복잡도는 O(n log n)으로 효율적이지만, 추가적인 배열이 필요하므로 공간 복잡도는 O(n)입니다.
