알고리즘 및 공간시간 복잡도

자료구조 2주차 정리

추상 자료형

• 자료형 (data type)

실수, 정수, 불리언 자료형등 여려 종류의 데이터를 식별하는 분류이다

 

• 추상 자료형(ADT)

컴퓨터 과학에서 자료의 표현 및 기능의 구현을 명시하는 대신 자료의 속성 및 기능을 나열하는 자료형 복소수, 리스트, 스택, 큐, 맵, 우선순위 큐, 집합등

 

알고리즘

• 문제 해결을 위한 체계적 단계
• 순서도, 의사코드. 일반적인 언어로 작성 가능

 

알고리즘 특성

1. 입력 : 문제와 관련된 입력이 0개 이상 존재
2. 출력: 입력을 처리한 출력이 반드시 있어야 한다
3. 일반성: 같은 유형의 문제에 대해 항상 적용할 수 있어야한다
4. 유한성: 입력은 제한된 개수의 명령 단계를 거쳐 출력을 내고 반드시 종료 되어야 한다
5. 효율성: 문제 해결 과정이 효율적이어야 한다

 

알고리즘의 표현

• 순서도(flow chart)

명령의 종류와 기능에 따라 도표를 만들고 명령들의 순서대로 도표를 나열해 표현

 

• 의사코드 (pseudo code)

일반적인 언어와 프로그래밍 언어를 섞어서 만듦(특정 규칙은 없다)

//pseudo code
if (조건문) then {

} elseif(조건문) {

} else
endif 블록의 시작과 끝을 표시한다

 

 

복잡도

공간 복잡도

프로그램을 실행시켜 완료하는데 필요하는 기억 장소의 크기 (고정 공간 + 가변 공간으로 나타냄)

컴퓨터 기억장소에 제약이 있기 때문에 공간 복잡도는 중요하다

float sum (float list[], int n) {
	float tempsum = 0;
	int i;
	for (i=0;i<n;i++) {
		tempsum += list[i];
	return tempsum;
	}
}
// n개의 데이터를 더하는 프로그램

필요한 공간은 프로그램 사이즈 = 데이터 사이즈 = n+ 3 (n, tempsum,i)

공간복잡도 계산에서는 단순히 입력 파라미터로 전달되는 메모리 공간을 제외한다 -> list[]의 주소값 4byte만 전달

 

시간 복잡도

프로그램을 실행시켜 완료하는데 필요한 컴퓨터 시간 실행 시간을 나타낸것이 아니라 알고리즘을 수행하는데 연산들이 몇번 이루어지는 지를 숫자로 표기

• Big-O-Noration(빅오 표기법)

가장 많이쓰이는 표기법으로 알고리즘 실행시간의 상한을 나타낸 표기법(최악을 표기)

• 오메가 표기법

오메가 표기법은 알고리즘 실행시간의 하한을 나타낸 표기법

• 세타 표기법 알고리즘 실행시간의 평균 시간을 나타낸 표기법

 

빅오 표기법