자료구조란?
프로그램이란 , 데이터를 표현하고, 그렇게 표현된 데이터를 처리하는것이다. 이때, 데이터의 표현은 데이터의 저장을 포함하는개념이며 , 데이터의 저장을 담당하는 것이 자료구조이다.
선형구조의 자료구조는 리스트 , 스택 , 큐 가있고 , 비선형구조의 자료구조는 트리 , 그래프가 있다.
알고리즘이란?
알고리즘은 자료구조등으로 표현 및 저장된 데이터를 대상으로하는 문제의 해결방법이다.
알고리즘은 자료구조에 의존적이다. ( 자료구조에 따라서 효율적인 알고리즘은 달라진다 )
알고리즘의 성능 분석방법
알고리즘을 평가하는 두가지 요소는 속도와 메모리 사용량에 관한것이다. 속도에 해당하는 알고리즘의 수행시간 분석결과를 시간복잡도라고 하고 , 메모리 사용량에 대한 분석결과를 가리켜 공간복잡도라고 한다.
메모리를 적게쓰고 속도또한 빨라야 최적의 알고리즘이지만 , 보통 일반적으로 알고리즘을 평가할때는 메모리의 사용량보다 실행속도에 초점을둔다.
알고리즘의 수행속도를 평가할때는 연산의 횟수를센 후 , 처리해야할 데이터 수 n 에 대한 연산횟수의 함수 T(n)을 구성하면된다. ( 연산횟수를 통해 알고리즘의 빠르기를 결정한다 )
이때 중요한것은 n 에 대한 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;
}
T(n)을 구하는방법
T(n)을 구할때는 , 핵심이 되는 연산을 찾아서 ( 핵심이 되는 연산이란 , 그 연산이 이루어졌을때 다른 연산들또한 연산횟수가 늘어나는것을 말한다 , 위 함수의 경우 == 연산이다 ) 핵심 연산의 횟수를 대상으로 시간 복잡도를 분석하면된다,
알고리즘의 성능을 판단하는데 있어서 중요한것은 최악의 경우(n개의 데이터에서 n 번의 수행횟수를 가질경우 )이다.
순차 탐색 알고리즘의 시간복잡도 : 최악의경우
최악의 경우 , 데이터의 수가 n 개일때 , 최악의 경우에 해당하는 연산횟수는 n 이다.
따라서 T(n) = n 이다.
순차 탐색 알고리즘의 시간복잡도 : 평균적인 경우
가정 1. 탐색 대상이 배열에 존재하지 않을 확률을 50%라고가정.
가정 2. 배열의 첫 요소부터 마지막 요소까지 탐색대상이 존재할 확률은 동일하다.
탐색대상이 존재하지 않을경우의 연산횟수 n
탐색대상이 존재하는 경우의 연산횟수 n/2 ( 탐색대상이 존재할확률이 동일하므로)
배열에 존재하거나 존재하지않을경우의 확률이 50%이므로 , (n+n/2)/2 = 3/4*n 이다.
이진탐색 알고리즘의 소개
이진탐색은 순차탐색보다 훨씬 좋은 성능을 보인다 . 하지만 이를 적용하기위해서는 배열이 정렬되어있어야한다.