자료구조와 알고리즘의 이해

시간 복잡도(Time Complexity) : 어떤 알고리즘이 어떠한 상황에서 더 빠르고 더 느리냐

공간 복잡도(Space Complexity) : 어떤 알고리즘이 어떠한 상황에서 메모리를 적게 쓰고 또 많이 쓰냐

 

순차 탐색(Linear Search) T(n)=n

#include <stdio.h>

int LSearch(int ar[], int len, int target)
{
	int i;
	for (i = 0; i < len; i++)
	{
		if (ar[i] == target)
			return i;    // 찾은 대상의 인덱스 값 반환
	}
	return -1;    // 찾지 못했음을 의미하는 값 반환
}

int main(void)
{
	int arr[] = { 3, 5, 2, 4, 9 };
	int idx;

	idx = LSearch(arr, sizeof(arr) / sizeof(int), 4);
	if (idx == -1)
		printf("탐색 실패 \n");
	else
		printf("타겟 저장 인덱스: %d \n", idx);

	idx = LSearch(arr, sizeof(arr) / sizeof(int), 7);
	if (idx == -1)
		printf("탐색 실패 \n");
	else
		printf("타겟 저장 인덱스: %d \n", idx);

	return 0;
}

이진 탐색(Binary Search) T(n)=log₂n

#include <stdio.h>

int BSearch(int ar[], int len, int target)
{
	int first = 0;   // 탐색 대상의 시작 인덱스 값
	int last = len - 1;   // 탐색 대상의 마지막 인덱스 값
	int mid;

	while (first <= last)
	{
		mid = (first + last) / 2;   // 탐색 대상의 중앙을 찾는다. 

		if (target == ar[mid])   // 중앙에 저장된 것이 타겟이라면
		{
			return mid;
		}
		else    // 타겟이 아니라면 
		{
			if (target < ar[mid])
				last = mid - 1;   // 뒷부분을 탐색 대상에서 제외
			else
				first = mid + 1;   // 앞부분을 탐색 대상에서 제외
		}
	}
	return -1;   // 찾지 못했을 때 반환되는 값 -1
}

int main(void)
{
	int arr[] = { 1, 3, 5, 7, 9 };
	int idx;

	idx = BSearch(arr, sizeof(arr) / sizeof(int), 7);
	if (idx == -1)
		printf("탐색 실패 \n");
	else
		printf("타겟 저장 인덱스: %d \n", idx);

	idx = BSearch(arr, sizeof(arr) / sizeof(int), 4);
	if (idx == -1)
		printf("탐색 실패 \n");
	else
		printf("타겟 저장 인덱스: %d \n", idx);

	return 0;
}

 

빅-오 표기법(Big-Oh-Notation)

T(n)이 다항식으로 표현이 된 경우, 최고차항의 차수가 빅-오가 된다.

 

성능(수행시간, 연산횟수)의 대소별 정렬

O(1) : 상수형 빅-오. 연산횟수가 고정인 유형의 알고리즘을 대표

O(logn) : 로그형 빅-오. 데이터 수의 증가율에 비해서 연산횟수의 증가율이 훨씬 낮은 알고리즘(바람직)

O(n) : 선형 빅-오. 데이터의 수와 연산횟수가 비례

O(nlogn) : 선형로그형 빅-오. 연산횟수는 두 배를 조금 넘게 증가

O(n^2) : 데이터 수의 제곱에 해당하는 연산횟수를 요구. 중첩된 반복문 내에서 발생. 바람직x

O(n^3) : 데이터 수의 세제곱. 적용하기에 무리

O(2^n) : 지수형 빅-오. 사용하기에 매우 무리