복잡도 (시간복잡도, 공간복잡도)
복잡도를 나타낼 때에 자주 사용되는 함수
낮음 ◀----------------------------------------------------------------------------▶높음
1 log n n n log n n^2 n^3 n^4 n^k‥‥ 2^n
예)
int[] a = new int[100];
int[] b;
// a배열에 값 입력
b = a; << 이 대입문의 복잡도는 레퍼런스변수의 주소값 복사이므로 O(1)이다
보통 실제로 사용가능한 알고리즘은 다루는 데이터의 양에 따라 다르지만, 복잡도가
O(1), O(log n), O(n), O(n log n), O(n^2) 정도이다.
선형탐색과 이진탐색의 검색시의 시간 복잡도를 구해보자.
[선형탐색]
public Object search(int key) {
int i;
i = 0; // (1)
while(i < n) { // (2)
if (table[i].key == key) // (3)
return (table[i].data); // (4) 발견시 한번
i++ // (5)
}
return null; // (6) 발견하지 못했을때 한번
}
실행회수 복잡도
(1)번 1 O(1)
(2)번 n/2 O(n)
(3)번 n/2 O(n)
(4)번 1 O(1)
(5)번 n/2 O(n)
(6)번 1 O(1)
검색알고리즘의 시간복잡도는 각 행의 복잡도의 합을 구하면 된다
(2), (3), (5)는 모두 O(n) 이니 O(n) + O(n) + O(n) = O(n)이다.
총 합은 (1), (4), (6)는 모두 O(1) 이니 O(1) + O(1) + O(1) 에 위 복잡도를 합하여
search 메소드의 복잡도 = O(1) + O(1) + O(1) + O(n)
= O(max(1,1,1,n))
= O(n) 이다.
즉 선형탐색은 탐색을 1회 실행하는데 테이블에 등록되어있는 데이터의 개수에 비례한
시간이 걸리게된다.
[이진탐색]
<오름차순으로 정렬되있는 데이타 배열에서>
public Object search(int key) {
int low, high, middle;
low = 0; // (1)
high = n - 1; // (2)
while(low <= high) { // (3)
middle = (low + high) / 2; // (4)
if (key == table[middle].key) // (5)
return table[middle].data; // (6)
else if (key < table[middle].key) // (7)
high = middle - 1; // (8)
else // key > table[middle].key
low = middle + 1; // (9)
}
return null; // (10)
}
실행회수 복잡도
(1)번 1 O(1)
(2)번 1 O(1)
(3)번 (4) ~ (9)의 복잡도를 합한것이 된다.(실행횟수또한마찬가지)
(4) ~ (9) 루프 한번당 각 행은 최대 한번씩 실행되며 복잡도는 O(1)이다
(10)번 1 O(1)
위 (3)번의 실행횟수는 O(log n)이다. (이진탐색은 한번 탐색시마다 반씩 쪼개어 탐색되어지기때문에)
결국 (3) ~ (9)의 복잡도는 루프내부의 복잡도((4)~(9)) O(1) * O(log n) = O(log n)이다.
총 search메소드의 복잡도는
O(1) + O(log n) + O(1) = O(max(1, log n, 1))
= O(log n) 이다
선형탐색과 이진탐색의 데이타 등록시의 복잡도
[선형탐색]
public void add(int key, Object data) {
if (n >= MAX) {
// error 처리
}
table[n++] = new Entry(key, data);
}
위의 각 행들은 O(1)이다 . 선형탐색에서의 데이타 등록 처리의 복잡도는 명확히 O(1)이다.
[이진탐색]
public void add(int key, Object data) {
int pos;
pos = 데이터를 삽입할 위치; // (1)
배열에서 pos보다 뒤에 있는 요소들을 모두 1씩 민다; // (2)
table[pos] = new Entry(key, data); // (3)
}
(1)행은 삽입할 위치를 찾기위해 이진탐색을 하므로 O(log n)이다
(2)행은 평균 n/2개의 데이터를 이동할 필요가 있으므로 O(n)이다.
(3)행은 O(1)이다
전체 데이타를 등록하는
add메소드의 복잡도 = O(log n) + O(n) + O(1)
= O(max(log n, n, 1))
= O(n) 이다
즉 이진탐색의 데이타 등록의 복잡도는 테이블에 등록된 요소의 개수n에 비례한다.
데이타의 1개요소일때는 O(n)이지만 n개 요소일때는 O(n2) 이다.
이 시간 복잡도를 줄일 수 있는 방법으로 등록시에 선형탐색과 같이 등록순서대로 등록후 O(n)
정렬하는 방법이 있다.
정렬알고리즘에는 복잡도가 O(n log n)인 것이 있기 때문에 결과적으로
이진탐색의 데이타 등록의 전체복잡도는
O(n)등록 + O(n log n)정렬 = O(max(n, n log n))
= O(n log n) 으로 줄일 수 있다.
결론적으로 이진탐색은 '프로그램의 실행 중에 빈번한 데이터 등록을 하면서 동시에 탐색을 한다'
라는 경우에 사용하는 것은 적절치 않다.
- 2008.01 15:27 -
복잡도를 나타낼 때에 자주 사용되는 함수
증가율
낮음 ◀----------------------------------------------------------------------------▶높음
1 log n n n log n n^2 n^3 n^4 n^k‥‥ 2^n
예)
int[] a = new int[100];
int[] b;
// a배열에 값 입력
b = a; << 이 대입문의 복잡도는 레퍼런스변수의 주소값 복사이므로 O(1)이다
보통 실제로 사용가능한 알고리즘은 다루는 데이터의 양에 따라 다르지만, 복잡도가
O(1), O(log n), O(n), O(n log n), O(n^2) 정도이다.
선형탐색과 이진탐색의 검색시의 시간 복잡도를 구해보자.
[선형탐색]
public Object search(int key) {
int i;
i = 0; // (1)
while(i < n) { // (2)
if (table[i].key == key) // (3)
return (table[i].data); // (4) 발견시 한번
i++ // (5)
}
return null; // (6) 발견하지 못했을때 한번
}
실행회수 복잡도
(1)번 1 O(1)
(2)번 n/2 O(n)
(3)번 n/2 O(n)
(4)번 1 O(1)
(5)번 n/2 O(n)
(6)번 1 O(1)
검색알고리즘의 시간복잡도는 각 행의 복잡도의 합을 구하면 된다
(2), (3), (5)는 모두 O(n) 이니 O(n) + O(n) + O(n) = O(n)이다.
총 합은 (1), (4), (6)는 모두 O(1) 이니 O(1) + O(1) + O(1) 에 위 복잡도를 합하여
search 메소드의 복잡도 = O(1) + O(1) + O(1) + O(n)
= O(max(1,1,1,n))
= O(n) 이다.
즉 선형탐색은 탐색을 1회 실행하는데 테이블에 등록되어있는 데이터의 개수에 비례한
시간이 걸리게된다.
[이진탐색]
<오름차순으로 정렬되있는 데이타 배열에서>
public Object search(int key) {
int low, high, middle;
low = 0; // (1)
high = n - 1; // (2)
while(low <= high) { // (3)
middle = (low + high) / 2; // (4)
if (key == table[middle].key) // (5)
return table[middle].data; // (6)
else if (key < table[middle].key) // (7)
high = middle - 1; // (8)
else // key > table[middle].key
low = middle + 1; // (9)
}
return null; // (10)
}
실행회수 복잡도
(1)번 1 O(1)
(2)번 1 O(1)
(3)번 (4) ~ (9)의 복잡도를 합한것이 된다.(실행횟수또한마찬가지)
(4) ~ (9) 루프 한번당 각 행은 최대 한번씩 실행되며 복잡도는 O(1)이다
(10)번 1 O(1)
위 (3)번의 실행횟수는 O(log n)이다. (이진탐색은 한번 탐색시마다 반씩 쪼개어 탐색되어지기때문에)
결국 (3) ~ (9)의 복잡도는 루프내부의 복잡도((4)~(9)) O(1) * O(log n) = O(log n)이다.
총 search메소드의 복잡도는
O(1) + O(log n) + O(1) = O(max(1, log n, 1))
= O(log n) 이다
선형탐색과 이진탐색의 데이타 등록시의 복잡도
[선형탐색]
public void add(int key, Object data) {
if (n >= MAX) {
// error 처리
}
table[n++] = new Entry(key, data);
}
위의 각 행들은 O(1)이다 . 선형탐색에서의 데이타 등록 처리의 복잡도는 명확히 O(1)이다.
[이진탐색]
public void add(int key, Object data) {
int pos;
pos = 데이터를 삽입할 위치; // (1)
배열에서 pos보다 뒤에 있는 요소들을 모두 1씩 민다; // (2)
table[pos] = new Entry(key, data); // (3)
}
(1)행은 삽입할 위치를 찾기위해 이진탐색을 하므로 O(log n)이다
(2)행은 평균 n/2개의 데이터를 이동할 필요가 있으므로 O(n)이다.
(3)행은 O(1)이다
전체 데이타를 등록하는
add메소드의 복잡도 = O(log n) + O(n) + O(1)
= O(max(log n, n, 1))
= O(n) 이다
즉 이진탐색의 데이타 등록의 복잡도는 테이블에 등록된 요소의 개수n에 비례한다.
데이타의 1개요소일때는 O(n)이지만 n개 요소일때는 O(n2) 이다.
이 시간 복잡도를 줄일 수 있는 방법으로 등록시에 선형탐색과 같이 등록순서대로 등록후 O(n)
정렬하는 방법이 있다.
정렬알고리즘에는 복잡도가 O(n log n)인 것이 있기 때문에 결과적으로
이진탐색의 데이타 등록의 전체복잡도는
O(n)등록 + O(n log n)정렬 = O(max(n, n log n))
= O(n log n) 으로 줄일 수 있다.
결론적으로 이진탐색은 '프로그램의 실행 중에 빈번한 데이터 등록을 하면서 동시에 탐색을 한다'
라는 경우에 사용하는 것은 적절치 않다.
- 2008.01 15:27 -
'language > java' 카테고리의 다른 글
java.mail패키지를 이용한 JSP페이지에서 SMTP서버 메일 전송 (0) | 2008.04.18 |
---|---|
exe 파일 만들기 (0) | 2008.02.12 |
I/O의 기본 개념 & Stream (0) | 2008.01.21 |
javadoc 활용(클래스 문서화 시키기) & jar 활용(압축 및 배치) (1) | 2008.01.20 |
java.io.*; (0) | 2008.01.20 |