240408 Java - 시간복잡도

※자료 구조

자료(데이터)의 집합으로 데이터들을 어떤 형태로 저장해 둘 것인가에 대해 연구해 놓은 형태

 

※알고리즘

어떤 문제를 해결하기 위한 절차, 방법, 명령어들의 집합을 총칭

문제를 해결해 나가는 절차

• 입력, 출력, 유한성, 명백성, 효과성을 만족
• 분석을 통해 좋고 나쁨을 평가할 수 있음
• 논리이며 실질적인 개발에 적용되는 기초적인 아이디어
• 정해진 상황에서 더 효율적으로 문제를 해결해주는 알고리즘은 분명히 존재하고 알고리즘 분석을 통해 증명

어디에 사용?

• 개발 전체에 사용
• 효율적인 알고리즘을 사용함으로써 원하는 결과를 도출
• 종합적인 개발 역량을 평가하기 좋은 용도

프로그램과 알고리즘

• 프로그램 : 컴퓨터 상에서 실행할 수 있도록 컴퓨터가 이해할 수 있는 언어로 작성하는 것
• 알고리즘 : 프로그램을 작성하기 이전 단계에서 사람이 이해할 수 있도록 절차를 작성하는 것

알고리즘

• 컴퓨터로 문제를 해결하기 위한 다양한 처리 절차의 연구 결과는 이미 만들어짐
• 개량된 알고리즘들 중에서 좋은 알고리즘들이 현재 다수의 컴퓨터 프로그램에서 사용

알고리즘 종류

기술 계산을 위한 알고리즘

• 유클리드 호제법(최대 공약수)
• 사다리꼴의 법칙(정적분)
• 에라토스테네스의 체(소수)
• 가우스 소거법(방정식)
• 데이크스트라 알고리즘(최적 경로)

 

검색을 위한 알고리즘 : 많은 양의 데이터 중에서 원하는 데이터를 찾아내기 위한 알고리즘

• 선형 검색(리니어 서치) 처음부터 하나씩 찾아내는 방식
• 이전 검색(바이너리 서치) 

 

정렬 알고리즘 : 한 줄로 늘어선 데이터를 오름차순 또는 내림차순으로 정렬하는 알고리즘

• 단순 선택 정렬
• 단순 삽입 정렬
• 단순 교환 정렬(버블 정렬)
• 병합 정렬
• 셀 정렬
• 퀵 정렬

 

문자열 패턴 매칭을 위한 알고리즘 : 문자열 중 지정한 문자열의 패턴(부분 문자열)과 일치하는 부분을 찾아내기 위한 알고리즘

• 단순 문자열 일치
• KMP 알고리즘
• BM 알고리즘

알고리즘 선택 방법

• 사람이 이해하기 쉽고 프로그램으로 작성하기도 쉬운가
• 실행중에 메모리 영역을 작게 차지하는가? 메모리가 작은 컴퓨터 상에서도 동작한다 라는 이점이 있음
• 가장 중요시 되는 것은 계산 => 주어진 입력값으로 결과를 내기까지의 걸리는 시간
• 알고리즘 간 실행시간의 차이 뿐만 아니라 같은 알고리즘에서도 입력의 크기에 따라 알고리즘 계산 시간이 얼마만큼 달라지는지도 고려해야함

복잡도 : 알고리즘의 성능을 나타내는 지표

1. 시간 복잡도 특정한 크기의 입력에 대해 알고리즘의 수행 시간 분석
2. 공간 복잡도 특정한 크기의 입력에 대하여 알고리즘의 메모리 사용량 분석

=> 알고리즘이 얼마나 효율적인가? 를 증명 : 시간 계산량과 영역 계산량을 기준으로 함

 

 

시간 복잡도(알고리즘 시간 계산량)

• 프로그램을 실행시켜 종료까지의 시간을 측정하는 방식
• 연산, 조건비교, 변수대입 등의 조작(스탭, 단계) 들을 하나의 단위로, 각각의 실행 횟수로 측정
• 실행하는 컴퓨터의 성능
• 주변 기기와 데이터의 입출력에 걸리는 시간 등에 영향을 받으므로 객관적인 값으로 볼 수 없음

 

공간복잡도(알고리즘 영역 계산량)

• 알고리즘 실행시 사용되는 "공간적 자원의 크기"
• 상수영역, 변수 영역, 배열 영역, 스택같은 작업 영역 등의 총합계, 사용하는 메모리 영역의 크기를 뜻함

 

알고리즘 계산시간을 표현하는 방법

1. Big-O notation : worst case

• 알고리즘의 시간 복잡도를 나타내는 표기법
• 특정 알고리즘이 문제상황을 해결하는데 걸리는 시간
• 계산 시간이 아무리 오래 걸려도 이보다는 오래 걸리지 않는 시간을 기준으로 알고리즘의 성능 표기하는 것

※알고리즘은 연산이 많아질수록 그 속도가 오래 걸림
※시간복잡도는 알고리즘 내 연산의 횟수(스탭)와 관계가 있음

 

package test23;

public class Big_O {

	//복잡도 : 알고리즘의 성능을 나타내는 지표 => 시간 복잡도, 공간 복잡도(특정한 크기의 입력에 대하여 알고리즘의 메모리 사용량을 분석)
	
	//시간 복잡도 : 입력 크기가 증가하면 연산 횟수가 얼마나 증가하는가?
	
	//1. O(1) : 입력값의 크기에 상관없이 일정한 시간 소요 -> 상수 시간
	//n 충분히 큰 값 / 상수값 : 고정된 값(연산에 영향을 크게 미치지 않음)
	public static void show1(int arr[]) {
		
		System.out.println(arr[3]); //스탭
		
	}
	
	
	//2. O(log n) : 입력 크기(n)이 커지면 연산 횟수가 log n 에 비례해서 증가 -> 로그 시간
	//이진 탐색 : 알고리즘의 각 단계에서 입력의 상단부분(절반)을 방문하지 않고 지나감
	//ex) 데이터 10개 중 중간값을 찾아 중간 값에 해당되지 않는 영역(1/2)은 탐색에서 제외 -> 3번만 비교
	//log 10 = 3.321928094887
	
	
	//3. O(n) : 입력 크기(n)이 커지면 연산 횟수가 n에 비례해서 증가 -> 선형 시간 
	//for문
	public static void show2(int n) { //스탭
		int sum = 0;
		for(int i = 0 ; i <= n ; i++) {
			sum += i;
			System.out.println("sum = "+ sum);
		}
	}
	
	
	//4. O(n log n) : 입력 크기(n)이 커지면 연산 횟수가 log 곱에 비례해서 증가 -> 선형 로그 시간
	//퀵 정렬, 병합 정렬, 힙 정렬
	// 반으로 계속 나눌 때 log n / 합칠 때 데이터의 개수(n)만큼 비교
	
	
	//5. O(n^2) : 입력 크기(n)이 커지면 연산 횟수가 n^2에 비례해서 증가 -> 2차 시간
	//소요되는 시간이 제곱으로 증가
	//이중 for 문, 삽입정렬, 거품(버블)정렬, 선택정렬
	//n개가 늘어나면 n^2을 반복해야함
	
	//거품정렬
	public static void bubble(int[] arr) {
		for(int i = 0; i < arr.length; i++) { //배열(기본 데이터)
			for(int j = 0; j< arr.length -i - 1;j++) { //배열의 다음 위치를 찾아감)
				if(arr[j]>arr[j+1]) { //위치 바꾸기
					int temp = arr[j];
					arr[j] = arr[j+1];
					arr[j+1] = temp;
				}
			}
		}
	}
	
	
	//6. O(2^n) : 입력 크기(n)가 커지면 연산 횟수가 2^n에 비례해서 증가 ->지수 시간
	//피보나치 수열 : (n-2)항 + (n - 1)항
	public static int fibonacci(int num) {
		if(num ==0) return 0;
		if(num ==1) return 1;
		
		//재귀 함수 : 자신의 함수를 함수 내에서 재호출하여 사용
		return fibonacci(num - 1) + fibonacci(num - 2);
	}
	
	public static void main(String[] args) {

		int[] arr = {10,20,30,40,50};
		show1(arr);
		
		System.out.println("=============================");
		
		show2(10);
		
		System.out.println("=============================");
		
		int[] arr1 = {3,4,5,2,3,1,7,8};
		bubble(arr1);
		for(int data : arr1) {
			System.out.print(data + " ");
		}
		
		System.out.println();
		System.out.println("=============================");
		
		int fibonacciResult = fibonacci(11);
		//1 1 2 3 5 8 13 21 34 55 89
		System.out.println(fibonacciResult);
		
		
	}

}

 

 

O(1) < O(log n) < O(n) < O(n log n) < O(n^2) < O(2^n) < O(n!)

<- 시간복잡도 낮음                                      시간복잡도 높음 ->

※연산의 수행 횟수는 보통 프로그램에 주어지는 입력의 개수 n에 따라 변하게 됨