💁♀️ 시간 복잡도 (Time complexity)
연산을 수행할 때 처리 속도의 기준은 무엇일까? 내 컴퓨터에서 10분 걸리는 연산이 있다고 가정했을 때, 이 연산은 어떤 컴퓨터에서 수행해도 정확하게 10분이 걸릴까? 정답은 아니다. 시간은 연산을 실행하는 하드웨어에 따라 항상 바뀐다. 따라서 시간을 기준으로 속도를 측정하면 신뢰할 수 없다.
대신 연산의 속도를 측정할 때 얼마나 많은 단계(step)가 필요한가를 참고할 수 있다. 시간 복잡도는 연산을 수행할 때 단계에 비해 시간이 얼마만큼 걸리는지를 정량화한 것이다. 알고리즘을 구상할 때 시간 복잡도를 염두에 두어 짜면, 알고리즘의 효율성이 좋아진다. 효율적인 알고리즘은 입력값이 커짐에 따라 증가하는 시간의 비율을 최소화한 알고리즘을 의미한다.
👉 빅 O 표기법 (Big-O)
빅 O 표기법은 시간 복잡도를 표현하는 대표적인 방법이다. (나머지는 빅-오메가, 빅-세타가 있다.) 빅 O 표기법의 핵심은 입력값의 변화에 따라 연산을 실행할 때, 연산 횟수에 비해 시간이 얼마만큼 걸리는가?를 표기한 것이다. 그래프를 보면 알 수 있듯 O(1)에 가까울수록 시간 복잡도가 좋고, O(n!)에 다가갈수록 시간 복잡도가 나빠진다. O(1), O(log n) 등 다양한 빅 O 시간 복잡도가 어떤 의미인지 하나하나 살펴보자.
O(1)
O(1)은 데이터 크기에 상관없이 알고리즘에 필요한 단계 수가 일정하다는 의미다. 배열에서 값을 읽어오거나, 배열 끝에 값을 삽입/삭제하는 것이 O(1)의 시간 복잡도를 가진다.
O(log n)
O(log n)은 데이터가 두 배로 증가할 때마다 한 단계씩 늘어나는 알고리즘이다. 이러한 유형의 알고리즘을 로그 시간(log time)의 시간 복잡도라고 하며, O(1)와 O(N)의 사이 어디쯤엔가 있다. O(log n)의 시간 복잡도를 가진 알고리즘으로 이진 탐색이 있다. 이진 탐색은 원하는 값을 탐색할 때, 노드를 이동할 때마다 경우의 수가 절반으로 줄어든다.
O(N)
O(n)은 데이터 원소 수만큼의 단계가 필요하다. 이러한 유형의 알고리즘을 선형 시간(linear time)이라고 부른다. (O(1)은 반대로 상수 시간(constant time)이라고 부른다.) 그래프에서 보면 알 수 있듯이 O(n)은 완벽한 대각선을 그린다. 데이터가 추가될 때마다 그만큼의 단계가 늘어나기 때문이다.
O(n^2)
O(n^2)는 데이터 원소가 n개일 때 n^2 단계가 필요하다. O(N)보다도 데이터의 증가에 따른 단계 증가가 급격하기 때문에 비효율적이인 편에 속한다. O(n^2)를 이차 시간(quadratic time)이라고도 부르며, 대표적으로 중첩 루프(ex. 중첩된 for문) 알고리즘이 이 시간 복잡도를 가진다.
O(2^n)
O(2^n)은 데이터 원소가 n개일 때 2^n 단계가 필요하다. 대표적인 예시가 피보나치 수를 구하는 알고리즘이다. n번째 피보나치 수를 구하기 위해서는 n-2번째, n-1번째 피보나치 수를 구해야하므로 1+2+4+8+2^(n-1)번 연산을 해야 한다.
✨ 빅 O 표기법에서 상수 생략하는 이유
빅 O 표기법은 데이터 원소 수에 비례해 얼마나 많은 단계가 필요한가를 표현한 것이다. 이 표기법에는 따라야 하는 규칙이 있는데, 바로 상수를 생략하는 것이다. O(2N)이든 O(100N)이든, 빅 O 표기법에서는 지수가 아닌 수는 생략한다.
알고리즘의 장기적인 증가율을 보기 때문에, 상수로 인해 어떤 알고리즘이 잠시 빨라도 이것을 그래프로 나타냈을 때 특정 시점을 지나면 빅 O 표기법에서 원래 빠른 알고리즘이 추월해서 점차 빨라지기만 한다. 절대 상수가 덜 중요하거나 의미 없어서 생략하는 것은 아니고, 빅 O 표기법에서 이것을 상관하지 않기로 정한 것이다.
참고 자료
『 누구나 자료 구조와 알고리즘』
참고하면 좋을 자료
