시간 복잡도
- O(big-O) : big-O는 시간의 상한을 나타낸다. 배열의 모든 값을 출력하는 알고리즘은 O(N)으로 표현할 수 있을 뿐만 아니라 O(N³), 이 외에 N보다 큰 big-O 시간으로 표현할 수도 있다.
상한 수행 시간 - Ω(big-Omega) : Ω는 등가 개념 혹은 하한을 나타낸다. 배열의 모든 값을 출력하는 알고리즘은 Ω(N)뿐만 아니라 Ω(logN) 혹은 Ω(1)로도 표현할 수 있다
해당 알고리즘은 Ω 수행 시간보다 빠를 수 없게 된다
하한 수행 시간 - θ(big theta) : 학계에서는 θ는 O와 Ω 둘 다 의미한다. 즉, 어떤 알고리즘의 수행 시간이 O(N)이면서 Ω(N)이라면, 이 알고리즘의 수행시간을 θ(N)로 표현할 수 있다
딱 맞는 수행 시간
최선의 경우, 최악의 경우, 평균적인 경우
퀵 정렬의 관점에서 살펴보면 '축'이 되는 원소 하나를 무작위로 뽑은 뒤 이보다 작은 원소들은 앞에, 큰 원소들은 뒤에 놓이도록 원소의 위치를 바꾼다. 그 결과 부분정렬이 완성되고 그 뒤 왼쪽과 오른쪽 부분을 이와 비슷한 방식으로 재귀적으로 정렬해 나간다
- 최선의 경우 : 만약 모든 원소가 동일 하다면 퀵 정렬은 평균적으로 단순히 배열을 한 차례 순회하고 끝날 것이다. 수행 시간은 O(N)이 된다.(퀵 정렬의 구현 방식에 따라 조금 달라질 수 있다. 배열이 정렬되어 있을 떄 굉장히 빠르게 동작하는 구현 방식도 존재한다)
- 최악의 경우 : 배열에서 가장 큰 원소가 계속해서 축이 된다면(배열이 역순으로 정렬되어 있고 부분 배열의 첫 번째 원소를 항상 축으로 잡는 경우) 재귀 호출이 배열을 절반 크기의 부분 배열로 나누지 못하고 고작 하나 줄어든 크기의 부분 배열로 나누게 된다.
따라서 수행시간은 O(N²)로 악화된다 - 평균적인 경우 : 축이 되는 원소가 가장 작거나 가장 클 순 있지만, 이런 일이 반복적으로 일어나는 경우가 많지 않다.
따라서 수행시간이 평균적으로 O(NlogN)이다
공간 복잡도
알고리즘에서는 시간 뿐 아니라 메모리(공간)도 신경써야 한다
공간 복잡도는 시간 복잡도와 평행선을 달리는 개념이다.
크기가 n인 배열을 만들고자 한다면, O(n)의 공간이 필요하다. nxn크기의 2차원 배열을 만들고자 한다면, O(n²)의 공간이 필요하다
재귀 호출에서 사용하는 스택 공간 또한 공간 복잡도 계산에 포함된다.
다음 코드는 O(n) 시간과 O(n)공간을 사용한다
int sum(int n) {
if(n<=0) {
return 0;
}
return n + sum(n-1);
}호출될 때마다 스택의 깊이는 깊어진다
// 0과 n사이에서 인접한 두 원소의 합을 구하는 함수
int pairSumSequence(int n) {
int sum = 0;
for(int i=0; i<n; i++) {
sum += pairSum(i, i+1);
}
return sum;
}
int pairSum(int a, int b) {
return a+b;
}위 코드는 pairSum함수를 대략 O(n)번 호출했지만, 이 함수들이 호출 스택에 동시에 존재하지는 않으므로 O(1)공간만 사용한다
상수항은 무시한다
big-O 표기법은 수행 시간이 어떻게 변화하는지를 표현해주는 도귀다. 따라서 O(N)이 언제나 O(2N)보다 나은 것은 아니다
O(N²+N²)은 O(N²)이 된다. 이처럼 마지막 N²항을 무시해도 된다
지배적이지 않은 항은 무시한다
수식에서 지배적이지 않은 항은 무시해도 된다
- O(N²+N)은 O(N²)이 된다
- O(N+logN)은 O(N)이 된다
- O(5*2ⁿ+1000N¹⁰⁰)은 O(2ⁿ)이 된다
O(B²+A)는 하나의 항으로 줄일 수 없다. (A와 B사이에 특별한 관계가 없는 이상)
// 덧셈 수행 시간 : O(A+B)
for(int a:arrA) {
print(a);
}
for(int b:arrB) {
print(b);
}A의 일을 한 뒤에 B의 일을 수행한다. 따라서 전체 수행한 일은 O(A+B)가 된다
만약 알고리즘이 "A일을 모두 끝마친 후에 B일을 수행하라" 의 형태면
A와 B의 수행 시간을 더해야 한다
// 곱셈 수행 시간 : O(A*B)
for(int a:arrA){
for(int b:arrB){
print(a+","+b);
}
}A의 각 원소에 대해 B의 일을 수행한다. 따라서 전체 수행한 일은 O(A*B)가 된다
만약 알고리즘이 "A일을 할 때마다 B일을 수행하라" 의 형태라면
A와 B의 수행 시간을 곱해야한다
상환 시간
ArrayList(동적 가변크기 배열)은 배열의 역할을 함과 동시에 크기가 자유롭게 조절되는 자료구조이다.
원소 삽입 시 필요에 따라 배열의 크기를 증가시킬 수 있기 때문에 ArrayList의 공간의 바닥날 일은 없다
ArrayList는 배열로 구현되어 있다. 배열의 용량이 꽉 찼을때 ArrayList 클래스는 기존보다 크기가 두 배 더 큰 배열을 만든 뒤, 이전 배열의 모든 원소를 새 배열로 복사한다
배열이 가득 차 있는 경우, 배열에 N개의 원소가 들어 있을 때 새로운 원소를 삽입하려면 O(N)이 걸린다
왜냐하면 크기가 2N인 배열을 새로 만들고 기존의 모든 원소를 새 배열로 복사해야 하기 때문이다
따라서 이 경우에 삽입 연산은 O(N) 시간이 소요된다
하지만 배열이 가득 차 있는 경우는 극히 드물다. 대다수의 경우에는 배열에 가용 공간이 존재하고 이때 삽입 연산은 O(1)이 걸린다
두가지 경우를 포함한 전체 구행 시간을 따져봐야 하는데, 최악의 경우는 가끔 발생하지만 한번 발생하면 그 후로 오랫동안 나타나지 않으므로 비용(수행 시간)을 분할 상환한다는 개념이다
X개의 원소를 삽입했을 때 필요한 시간은 O(2X)이고, 이를 분할 상환해보면 삽입 한 번에 필요한 시간은 O(1)이다.
log N 수행시간
이진탐색은 N개의 정렬된 원소가 들어있는 배열에서 원소 x를 찾을 때 사용된다
먼저 원소 x와 배열의 중간값을 비교한다. 'x==중간값'을 만족하면 이를 반환한다
'x<중간값'일 때는 배열의 왼쪽 부분을 재탐색하고
'x>중간값'일 경우에는 배열의 오른쪽 부분을 재탐색한다
2ⁿ= N을 만족하는 ⁿ은 무엇인가? 에서 사용 되는 것이 로그(log)이다
2⁴=16 -> log₂16= 4
log₂N=n -> 2ⁿ= N어떤 문제에서 원소의 개수가 절반씩 줄어든다면 그 문제의 수행 시간은 O(logN)이 될 가능성이 크다
big-O에선 로그의 밑을 고려할 필요가 없다
재귀적으로 수행 시간 구하기
int f(int n) {
if(n<=1) {
return 1;
}
return f(n-1) + f(n+1);
}함수 f가 두 번 호출된 것을 보고 성급하게 O(N²)이라고 생각하면 오답이다
수행 시간을 추측하지 말고 코드를 하나씩 읽어나가면서 수행 시간을 계산하면
f(4)는 f(3)을 두번 호출한다.
트리의 깊이가 N이고 각 노드(함수 호출)는 두 개의 자식 노드를 갖고 있다.
따라서 깊이가 한 단계 깊어질 때마다 이전보다 두 배 더 많이 호출하게 된다
다수의 호출로 이루어진 재귀 함수에서 수행시간은 보통 O(Nⁿ)로 표현된다(N:분기, ⁿ:깊이)
분기란 재귀 함수가 자신을 재호출하는 횟수를 뜻한다. 따라서 수행 시간은 O(2ⁿ)이 된다
로그의 밑은 상수항으로 취급되기 때문에 big-O기법에서는 로그의 밑은 무시해도 되지만 지수에서는 지수의 밑을 무시하면 안된다.
2ⁿ과 8ⁿ을 비교하면 이 사이에는 2²ⁿ만큼의 차이가 있다.
이 차이(2²ⁿ)는 지수항이므로 상수항과는 아주 큰 차이가 있다
이 알고리즘의 복잡도는 O(N)이 될 것이다. 전체 노드의 개수는 O(2ⁿ)이지만, 특정 시각에 사용하는 공간의 크기는 O(N)이다. 따라서 필요한 가용 메모리의 크기는 O(N)이면 충분하다
// 균형 이진 탐색 트리 예제
// 균형 이진 탐색 트리에서 모든 노드으 값을 더하는 코드. 수행시간은?
int sum(Node node) {
if(node==null) {
return 0;
}
return sum(node.left) + node.value + sum(node.right);
}코드는 무엇을 의미하는가?
이 코드는 트리의 각 노드를 한 번씩 방문한 뒤 각 노드에서(재귀 호출 부분 제외) 상수 시간에 해당하는 일을 수행
따라서, 수행 시간은 노드의 개수와 선형 관계에 있다
즉, N개의 노드가 있을 때 수행시간은 O(N)이 된다
깊이 판단 > N개의 노드가 있다면 깊이는 대략 logN이 된다
위 수식에 따르면 수행시간은 O(2^n)이 된다
O(1) : 입력 자료의 수(n)에 관계없이 일정한 실행 시간을 갖는 알고리즘(Constant Time)
-
배열에서 특정 인덱스 찾기, 해시 테이블 추가, 스택에서 Push, Pop
O(log n) : 초반엔 빠르지만 후반부 갈수록 시간이 증가함 -
이진 탐색
O(n) : 입력 자료의 크기가 N일 경우 N 번만큼의 수행 시간을 가진다.(linear) -
연결 리스트 순회, 최댓값 찾기, for 문
O(n log n) : 선형 로그형, 데이터의 수가 2배로 늘 때, 연산 횟수가 2배 조금 넘게 증가한다. -
퀵 정렬, 병합 정렬, 힙 정렬 등
O(n^2) : 주로 2중 for loop를 사용하여 조합 가능한 모든 쌍을 대상으로 하는 경우가 전형적(quadratic) -
버블 정렬, 삽입 정렬, 거품 정렬, 선택 정렬
O(n^3) : 3 차형(cubic)
O(2^n) : 지수형 빅오, '지수적 증가'는 무서운 연산 횟수 증가를 야기한다. -
피보나치수열
O(c^n) : 최악의 시간 복잡도 - exponential -
recursion
O(n!) : 계승(factorial)
// 소수판별 함수 예제
boolean isPrime(int n) {
for(int x = 2; x*x <=n; x++) {
if(n%x==0) {
return false;
}
}
return true;
}for 루프의 내부 코드는 상수 시간에 동작한다
따라서 최악의 경우 for 루프가 몇 번 반복하는지만 세어보면 시간 복잡도를 구현할 수 있다
이 코드에서 루프는 x=2에서 x*x=n 까지 반복한다
다시 말해서 x=√n(x가 n의 제곱근이 될 댸 까지) 반복한다는 뜻이다
따라서 이 코드에서 for 루프는 아래와 같다
boolean isPrime(int n) {
for(int x = 2; x*x <= sqrt(n); x++) {
if(n%x==0) {
return false;
}
}
return true;
}시간 복잡도는 O(√n)이 된다
// n의 계승(factorial) n!을 구하는 코드
int factorial(int n) {
if(n <0) {
return -1;
} else if(n==0) {
return 1;
}else {
return n*factorial(n-1);
}
}단순히 n부터 1까지 반복하는 재귀 함수이므로 O(n)이 된다
// 문자열로 나타낼 수 있는 순열(permutation)의 개수를 구하는 코드
void permutation(String str) {
permutation(str,"");
}
void permutation(String str, String perfix) {
if(str.length()==0) {
System.out.println(prefix);
} else {
for(int i=0; i<str.length(); i++) {
String rem = str.substring(0,i)+str.substring(i+1);
permutation(rem, prefix + str.charAt(i));
}
}
}permutation함수가 얼마나 많이 호출되는지, 각 호출마다 걸리는 시간이 얼마나 되는지 살펴보자
순열이 완성되는 시점에서 permutation함수가 몇번이나 호출되는가?
순열을 생성하고 싶다면 각 자리에 들어갈 문자를 골라야 한다
길이가 7인 문자열이 주어졌을 때, 첫번째 자리는 7개의 선택권이 있다
여기서 문자 하나를 선택했다면 그 다음 자리에는 6개의 선택권이 있다.
따라서 전체 가능한 경우는 7654321, 다시 말해 7!(7의 계승)이 된다
n!개의 순열이 존재한다는 뜻이고 따라서 순열 생성이 완성되는 시점(prefix가 모든 순열을 표현한다고 했을 때)에 permutation함수는 n!번 호출된다
말단 노드의 개수는 n!이 될 것이고 루트에서 각 말단 노드까지의 거리는 n이 된다
따라서 전체 노드(함수 호출)의 개수는 n*n!개를 넘지 못한다
permutation 함수는 O(nn!)번(상한) 호출되고 한 번 호출될 때마다 O(N)의 시간이 걸리므로
총 수행 시간은 O(n²n!)을 넘지 않을 것이다
