[C 자료구조] 자료구조와, 알고리즘 성능 분석 방법

내용 : 자료구조의 정의와, 시간복잡도, 공간 복잡도의 개념에 대해 공부한다.

 

1. 자료구조란

- 정의 : 데이터를 표현하고 저장하는 방법에 대해서 설명한다.

자료구조의 분류

 

파일도 데이터를 저장하는 도구이기 때문에 파일의 구조도 또한 자료구조에 포함이 돤다.

앞으로 공부할 내용은 선형구조와 비선형 구조를 공부한다.

 

    - 선형 자료구조 : 자료를 표현 및 저장하는 방식이 선형이다. 즉, 데이터를 선의 형태로 나란히 혹은 일렬로 저장하는 방식이다.

 

    - 비선형 자료구조 : 데이터를 나란히 저장하지 않는 구조, 선형구조에 비해 어렵다.

 

 

2. 알고리즘

-정의 : 표현 및 저장된 데이터를 대상으로하는 '문제의 해결방법'을 의미한다.

자료구조에 따라 알고리즘은 달라지며, 알고리즘은 자료구조에 의존적이다.

 

 

3. 알고리즘 성능 분석 방법

알고리즘의 속도 및 메모리 사용량을 분석하여 최적의 알고리즘을 찾기 위한 과정.

 

알고리즘의 속도를 평가할 때는 연산의 횟수를 센다  ->  처리해야 할 데이터의 수 n에 대한 연산횟수의 함수 T(n)을 구성한다.

 

상황에 따라 알고리즘을 적절히 사용하는것이 필요하다.

 

 

    - 시간 복잡도 (Time Complexity) : 시간복잡도란 알고리즘이 문제를 해결하기위한 시간(연산)의 횟수를 말한다.

 

    - 공간 복잡도 (Space Complexity) : 공간복잡도란 알고리즘이 차지하는 메모리의 용량을 평가기준으로 둔다.

 

4. 분석하기

#include <stdio.h>
int LSearch(int ar[], int len, int target) {
	int i;
	for (i = 0; i < len; i++) {
		if (ar[i] == target) {
			return 1;
		}

	}
	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); // 배열에서 4 탐색


	idx = LSearch(arr, sizeof(arr) / sizeof(int), 7);

	if (idx == -1)
		printf("탐색 실패");

	else
		printf("타겟 저장 인덱스 : %d", idx); // 배열에서 7 탐색
}

 

위는 순차 탐색 코드이다. 소스코드에서 실제로 탐색을 하는 코드는 아래와 같다.

 

for (i = 0; i < len; i++) {
	if (ar[i] == target) {
		return 1;
	}
}

 

이 알고리즘에서 사용된 연산자는 [< , ++, ==]이다. 이 중에서 연산을 적게 수행하는 탐색 알고리즘은 "=="를 적게 사용한 것이다.