자료구조와 알고리즘

자료구조란?

프로그램이란 데이터를 표현

알고리즘이란?

표현된 데이터를 처리

 

자료구조 분류

 

알고리즘을 평가하는 두 가지 요소
- 시간 복잡도

- 공간 복잡도

시간 복잡도의 평가 방법
- 중심이 되는 특정 연산의 횟수를 세어서 평가를 한다.
- 데이터의 수에 대한 연산횟수의 함수 T(n)을 구한다.

 

O(1) - 상수 시간 
알고리즘이 문제를 해결하는데 오직 한 단계만 거친다.

O(log n) - 로그 시간
문제를 해결하는데 필요한 단계들이 연산마다 특정 요인에 의해 줄어든다.

O(n) - 직선적 시간
문제를 해결하기 위한 단계의 수와 입력값 n이 1:1 관계를 가진다.

O(n^2) - 2차 시간
문제를 해결하기 위한 단계의 수는 입력값 n의 제곱이다.

O(C^n) - 지수 시간
문제를 해결하기 위한 단계의 수는 주어진 상수 값 C의 n제곱이다.

 

---

 

이진 탐색 알고리즘(Binary Search)
- 데이터가 무조건 정렬되어 있어야 한다.
- 이진 탐색 알고리즘은 정렬된 데이터가 아니면 적용이 불가능하다.

1. 배열 시작 인덱스와 마지막 인덱스 값을 합하여 2로 나눈다.
   그 인덱스에 해당하는 값이 3인지 확인한다.
   
   
2. 그 값이 찾는 값 3보다 크면 앞쪽 반 배열만 확인한다.(정렬된 데이터여서 가능)
   
   
3. 반씩 나누고 3과 비교하면서 찾아나간다.
   
   
4. 시간 복잡도는 O(logn)을 가진다.(탐색 대상이 절반씩 줄어드므로)
   
   

binarySearch(A,value,low,high)
	if(high <= low)
		return -1	//not found
	mid = (low + high) / 2
    if(A[mid] > value)
		return binarySearch(A,value,low,mid-1)
    else if(A[mid] < value)
		return binarySearch(A,value,mid+1,high)
	else
		return mid

 

 

 

순차 탐색 알고리즘(Linear Search)
- 맨 앞에서 부터 맨 끝까지 순서대로 탐색을 진행하는 알고리즘이다.
- 시간 복잡도는 O(n)을 가진다.(worst case)