자료구조&기본 알고리즘 입문(자바)- 복잡도
○복잡도
프로그램의 실행 속도는 프로그램이 동작하는 하드웨어나 컴파일러 등의 조건에 따라 달라진다.
알고리즘의 성능을 객관적으로 평가하는 기준을 복잡도(complexity)라고 한다.
복잡도는 하단과 같은 두 가지 요소를 가지고 있다
1. 시간 복잡도(time complexity): 실행에 필요한 시간을 평가한 것
2. 공간 복잡도(space complexity) : 기억 영여과 파일 공간이 얼마나 필요한 것을 평가한 것
복잡도를 표기할 때 사용하는 O는 Order에서 따온 것으로 , O(n)은 'O-n', 'Order n' 'n의 Order' 라고 읽는다
○ 선형 검색의 시간 복잡도
static int seqSearch(int[] a, int n, int key){
int i = 0;
while(i<n) {
if(a[i] == key)
return i; // 검색 성공
i++;
}
return -1; // 검색 실패
}변수 i에 대입하는 횟수는 처음 한 번 실행후 없다. 이렇게 한 번만 실행하는 경우 복잡도는 O(1)로 표기한다.
물론 메서드에서 값을 반환하는 경우도 한 번만 실행하기 때문에 O(1)로 표기한다. 배열의 맨 끝에 도달했는지를 판단하는 경우와 현재 검사하고 있는 요소와 찾고자 하는 값이 같은지를 판단하는 경우 평균실행 횟수는 n/2이다. 이처럼 n에
비례하는 횟수 만큼 실행하는 경우의 복잡도를 O(n)으로 표기한다.
그런데 n이 점점 커지면 O(n)에 필요한 계산 시간은 n에 비례하여 점점 길어진다. 이와 달리 O(1)에 필요한 계싼 시간은 변하지 않는다. 일반적으로 O(f(n))과 O(g(n))의 복잡도를 계산하는 방법은 아래와 같다.
O(f(n)) + O(g(n)) = O(max(f(n), g(n))) // max(a,b,)는 a와 b 가운데 큰 쪽을 나타내는 메서드
2개 이상의 복잡도로 구성된 알고리즘의 전체 복잡도는 차원이 더 높은 쪽의 복잡도를 우선시 한다.
둘이 아니라 셋 이상의 계산으로 구성된 알고리즘도 마찬가지다. 다시 말해 전체 복잡도는 차원이 가장 높은
복잡도를 선택하다. 그러므로 선형 알고리즘의 복잡도를 구하면 아래처럼 O(n)이 된다.
O(!) + O(n) + O(n) + O(1) + O(n) + O(1) = O(max(!, n, n, 1, n, 1, ) ) = O(n)
○ 이진 검색의 시간 복잡도
이진 검색법을 이용하면 검색할 요소의 범위를 절반 씩 좁힐 수 있다.
static int binSearch(int[]a, int n, int key) {
int pl = 0; // 검색 범위 맨 앞의 인덱스
int pr = n-1; // 검색 범위 맨 끝의 인덱스
do{
int pc = (pl + pr) / 2; // 중앙 요소의 인덱스
if(a[pc] == key)
return pc; // 검색 성공
else if(a[pc] < key)
pl = pc + 1; // 검색 범위를 뒤쪽 반으로 좁힘
else
pr = pc -1; // 검색 범위를 앞쪽 반으로 좁힘
} while (pl<=pr);
return -1; // 검색 실패
}이진 검색 검색 알고리즘의 복잡도를 구하면 다음과 같은 O(log n)을 얻을 수 있다.
O(1) + O(!) + O(long n) + O(long n) + O(!) + O(long n) + ... + O(1) = O(log n)
○ Arrays.binarySeach에 의한 이진 검색
Java는 배열에서 이진 검색을 하는 메서드를 표준 라이브러리로 제공 한다. 이진 검색 표준 라이버르리의 메서드로는
java.util.Arrays 클래스의 binarySeach 메서드가 있다. binarySearch 메서드는 다음과 같은 장점이 있다.
장점1: 이진 검색 메서드를 직접 코딩할 필요가 없다
장점2: 모든 자료형 배열에서 검색할 수 있다.
binarySearch 메서드는 오릋마순으로 정렬된 배열 a를 가정하고, 키 값이 key인 요소를 이진 검색한다.
binarySearch 메서드는 자료형에 따라 9가지 방법으로 오버로등(overloading)되어 있따.
검색에 성공한 경우
key와 일치하는 요소의 인덱스를 반환한다. 일치하는 요소가 여러개 있다면 무작위의 인덱스를 반환한다.
맨 앞의 인덱스나 어떤 특정한 인덱스를 번환하지 않는다
검색에 실패한 경우
반환 값은 삽입 포인트를 x라고 할 때 -x -1을 반환한다. 삽입 포인트는 검색하기 위해 지정한 key보가 큰 요소 중 첫 번쨰 요소의 인덱스다. 만약 배열의 모든 요소가 key보다 작다면 배열의 길이를 삽입 포인트로 정한다.
import java.util.Arrays;
import java.util.Scanner;
// Arrays.binarySearch로 이진 검색
class BinarySearchTester {
public static void main(String[] args) {
Scanner stdIn = new Scanner(System.in);
System.out.print("요솟수：");
int num = stdIn.nextInt();
int[] x = new int[num]; // 요솟수가 num인 배열
System.out.println("오름차순으로 입력하세요.");
System.out.print("x[0]："); // 배열의 첫 요소를 먼저 입력.
x[0] = stdIn.nextInt();
for (int i = 1; i < num; i++) {
do {
System.out.print("x[" + i + "]：");
x[i] = stdIn.nextInt();
} while (x[i] < x[i - 1]); // 바로 앞의 요소보다 작으면 다시 입력합.
}
System.out.print("검색할 값："); // 키 값을 입력 받음
int ky = stdIn.nextInt();
int idx = Arrays.binarySearch(x, ky); // 배열 x에서 키 값이 ky인 요소를 검색
if (idx < 0)
System.out.println("그 값의 요소가 없습니다.");
else
System.out.println(ky+"은(는) x[" + idx + "]에 있습니다.");
}
}
○ 자연 정렬로 정렬된 배열에서 검색하기
자연 정렬에서 대소 관계를 비교하는 메서드를 사용하여 검색하는 프로그램. 검색 대상인 x는 문자열 배열.
문자열을 ky에 입력하고 배열 x와 키 값 ky를 binarySearch메서드에 전달하면 검색할 수 있다.
import java.util.Arrays;
import java.util.Scanner;
// 문자열의 배열(Java의 키워드)에서 검색
class StringBinarySearch {
public static void main(String[] args) {
Scanner stdIn = new Scanner(System.in);
// Java에서 사용하는 키워드.
String[] x = {
"abstract", "assert", "boolean", "break", "byte",
"case", "catch", "char", "class", "const",
"continue", "default", "do", "double", "else",
"enum", "extends", "final", "finally", "float",
"for", "goto", "if", "implements", "import",
"instanceof", "int", "interface", "long", "native",
"new", "package", "private", "protected", "public",
"return", "short", "static", "strictfp", "super",
"switch", "synchronized", "this", "throw", "throws",
"transient", "try", "void", "volatile", "while"
};
System.out.print("원하는 기워드를 입력 : "); // 키값을 입력
String ky = stdIn.next();
int idx = Arrays.binarySearch(x, ky); // 배열 x에서 값이 ky인 요소를 검색
if (idx < 0)
System.out.println("해당 키워드가 없습니다.");
else
System.out.println("해당 키워드는 x[" + idx + "]에 있습니다.");
}
}
자연 정렬(natural ordering)?
binarySearch 메서드에 배열과 키 값을 전달하는 방법으로 검색할 수 있는 이유는 String 클래스가
Comparable<T> 인터페이스와 compareTO 메서드를 구현하고 있기 때문이다.
다음은 자연정렬에 대한 설명을 하기 위한 저연 정렬 상태와 그렇지 않은 상태의 예시다
| 문자열 정렬 | 자연 정렬 |
| 텍스트1.txt 텍스트10.txt 텍스트100.txt 텍스트2.txt 텍스트21.txt |
텍스트1.txt 텍스트2.txt 텍스트10.txt 텍스트21.txt 텍스트100.txt |
둘 다 ' 정렬이 되었다'라는 사실에는 문제가 없다. 하지만 문자열 정렬은 자연스럽지 못한데, 컴퓨터의 문자열 정렬은
동일한 위치에 있는 문자의 대소 비교를 통해 정렬하기 때문에 왼쪽과 같은 결과가 나온다. 사람에게는 오른쪽 형태의
정렬이 더 자연스럽기 때문에, 이러한 정렬을 '자연정렬'이라고 부른다.
○ 자연 정렬로 정렬되지 않은 배열에서 검색하기
자연 정렬로 정렬되지 않은 배열에서의 검색은 제너릭 메서드(generic method)로 하면 된다.
제너릭 메서드의 첫 번쨰 매개변수 a는 검색 대상이고, 두 전쨰 매개변수 key는 키 값이다.
제너릭 메서드는 자료형에 구애받지 않는다. 따라서 매개변수로 전달하는 자료형은 Integer 등등 어떤 것을
전달해도 좋다.
그렇지만 배열의 요소가 어떤 순서로 줄지어 있는지, 각 요소의 대소 관계를 어떻게 판단할 것인지에 대해서는 binarySearch 메서드에 알려주어야 한다. 이 정보는 세 번쨰 매개변수 c 에 전달한다.
static <T> int binarSearch (T[] a, T key, Comparator<? super T> c )
세 번째 매개변수 c에는 co parator를 전달한다. comparator의 근원은 다음과 같이 정의된
java.util.Comparator 인터페이스이다
// java.util.Comparator의 정의
package java.util;
public interface Comparator <T> {
int compare(T o1, T o2);
boolean equals(Object obj);
}객체의 대소 관계를 판단하는 comparator를 직접 구현하려면 COnparator 인터페이스를 구현한 클래스를 정의하고
그 클래스형의 인스턴스를 생성해야 한다. 그런 다음 매개변수로 전달된 두 객체의 대소 관계를 비교하여 그 결과를
다음과 같이 반환하는 compare 메서드를 구현하면 된다.
public int compare(T da, T d2){
if(d1 > d2) return 양수;
if(d1 < d2) return 음수;
if(d1 == d2) return 0;
}따라서 클래스 x에 대한 comparator 은 다음과 같다.
import java.util.Comparator;
//클래스 X의 내부에서 comparator를 정의하는 방법은 다음과 같다.
class X {
// // 필드, 메소드 등
public static final Comparator<T> COMPARATOR = new Comp();
private static class Comp implements Comparator<T> {
public int compare(T d1, T d2) {
// // d1이 d2보다 크면 양의 값 반환
// // d1이 d2보다 작으면 음의 값 반환
// // d1이 d2와 같으면 0 반환
}
}
}Comparator 인터페이스와 compare 메서드를 구현 한 클래스를 먼저 작성한다. 그 후에 클래스의 인스턴스를 생성한다. 즉, 생성한 인스턴스를 comparator라고 부른다.
comparator의 사용법은 binarySearch 메서드이 세 번쨰 매개변수로 클래스 X의 클래스 변수인 X,COMPARATOR를 전달하면 된다. 호출된 binarySearch 메서드는 전달받은 comparator를 기준으로 배열 요소의 대소 관계를 판단하여 이진 검색을 수행한다.
다음은 키 순서대로 정렬된 신체검사 데이터의 배열에서 특정한 사람의 키를 검색하는 포르그램이다.
import java.util.Arrays;
import java.util.Scanner;
import java.util.Comparator;
// 신체검사 데이터 배열에서 이진 검색하기
class PhysExamSearch {
// 신체검사 데이터를 정의.
static class PhyscData {
private String name; // 이름
private int height; // 키
private double vision; // 시력
// 생성자
public PhyscData(String name, int height, double vision) {
this.name = name; this.height = height; this.vision = vision;
}
// 문자열을 반환하는 메서드(정보 확인용)
public String toString() {
return name + " " + height + " " + vision;
}
// 오름차순으로 정렬하기 위한 comparator
public static final Comparator<PhyscData> HEIGHT_ORDER =
new HeightOrderComparator();
private static class HeightOrderComparator implements Comparator<PhyscData> {
public int compare(PhyscData d1, PhyscData d2) {
return (d1.height > d2.height) ? 1 :
(d1.height < d2.height) ? -1 : 0;
}
}
}
public static void main(String[] args) {
Scanner stdIn = new Scanner(System.in);
PhyscData[] x = { // 키의 오름차순으로 정렬
new PhyscData("이나령", 162, 0.3),
new PhyscData("유지훈", 168, 0.4),
new PhyscData("김한결", 169, 0.8),
new PhyscData("홍준기", 171, 1.5),
new PhyscData("전서현", 173, 0.7),
new PhyscData("이호연", 174, 1.2),
new PhyscData("이수민", 175, 2.0),
};
System.out.print("몇 cm인 사람을 찾고 있나요?：");
int height = stdIn.nextInt(); // 키 값 입력
int idx = Arrays.binarySearch(
x, // 배열x에서
new PhyscData("", height, 0.0), // 키가 height인 요소를
PhyscData.HEIGHT_ORDER // HEIGHT_ORDER에 의해 검색
);
if (idx < 0)
System.out.println("요소가 없습니다.");
else {
System.out.println("x[" + idx + "]에 있습니다.");
System.out.println("찾은 데이터：" + x[idx]);
}
}
}-출처: 자료구조와 함꼐 배우는 알고리즘 입문[자바편] 책 중
http://www.yes24.com/Product/Goods/60547893