C언어로 쉽게 풀어쓴 [자료구조] 시작 자료구조/알고리즘/빅오 표기법

자료구조란 :

자료를 구조화 시키는것 ex) 스택, 큐, 링크드리스트, 트리, 그래프 등등

알고리즘이란 :

입력에 맞추어서 어떤 문제를 처리에 맞게 해결하려는 과정
(문제를 풀기 위한 단계적인 과정)

알고리즘의 성능 분석

1. 직접 수행 방법

#include <stdio.h>
#include <stdlib.h>
#include <time.h>


int main(void)
{
	clock_t start, stop;
	double  duration;
	start = clock();	// 측정 시작

	for (int i = 0; i < MAX; i++) {
			;
	}// 의미 없는 반복 루프
	stop = clock();	// 측정 종료
	duration = (double)(stop - start) / CLOCKS_PER_SEC;
	printf("수행시간은 %f초입니다.\n", duration);
	return 0;
}

clock 함수로 호출 프로세서에 의하여 사용된 CPU시간을 직접 계산
문제점 : 알고리즘이 복잡하면 bad, 반드시 똑같은 하드웨어, 소프트웨어 환경

2. 간접 수행 방법  - 시간 복잡도 함수 - 빅오 표기법

시간 복잡도 : 알고리즘을 이루고 있는 연산들이 몇 번이나 수행되는지를 숫자로 표시한것 즉 연산의 수행횟수를 사용한다.

빅오 표기법 : 시간 복잡도 함수의 증가에 별로 기여하지 못하는 항을 생략가능
ex) n^2+1 : n이 무수히 커지면 +1은 영향을 별로 안끼친다.

따라서 O(n^2) 기본 연산의 횟수가 다항식으로 표현되었을 경우 다항식의 최고차항만을 남기고 다른 항들과 상수항을 버리는 것

알고리즘 시간 복잡도 척도 : 최악의 경우의 수행시간
(평균 수행시간 구하기 힘들어서)

int seq_search(int list[], int n, int key)
{
	int i;
	for (i = 0; i < n; i++)
		if (list[i] == key)
			return i;  /* 탐색에 성공하면 키 값의 인덱스 반환 */
	return -1;    /* 탐색에 실패하면 -1 반환 */
}

순차 탐색에서
최선의 경우 : 찾고자 하는 숫자가 배열의 맨 처음에 있는 경우 - O(1)
최악의 경우 : 숫자가 배열의 맨 마지막에 있는 경우 - O(n)
평균의 경우 : 모든 숫자들이 탐색될 가능성 1/n, (1+2+..+n)/n = (n+1)/2 - O(n)