자료구조

개념 : 모델링된 데이터를 컴퓨터에 저장하는 방식

 

종류 )

- 선형 구조 : 리스트, 스택, 큐

- 비선형 구조 : 트리, 그래프

 

알고리즘 : 작업의 구체적 수행 방식, 특정한 일을 수행하는 명령어들의 유한 집합, 단계쩍 절차

작업을 위해 데이터가 필요한데, 이 데이터를 저장하는 방식이 자료구조

즉, 프로그램 = 알고리즘 + 자료구조 

 

알고리즘 조건 )

- 입력 : 0개 이상의 입력 데이터

- 출력 : 적어도 하나의 결과

- 명백성 : 각 명령어들이 모호함 없이 명확

- 유한성 : 한정된 수의 단계 뒤에는 반드시 종료

- 유효성 : 실행 가능한 연산 

 

수행 시간 측정 

- 두 알고리즘 직접 구현 후, 실제 수행 시간 측정

#include <stdio.h> 
#include <stdlib.h> 
#include <time.h> //시간 패키지
int   main( void ) 
{ 
   clock_t start, finish; 
   double  duration; 
   start = clock();  //시작
    // 수행시간을 측정하고 하는 코드.... 
    
    
     // .... 
   finish = clock();  //끝
   duration = (double)(finish - start) / CLOCKS_PER_SEC; //끝 - 시작 시간
   
   printf("%f 초입니다.\n", duration); 
} 

 

 

복잡도 분석 )

 - 직접 구현하지 않고 수행 시간 분석

 - 알고리즘 연산 횟수를 측정하여 비교

 - 시간 복잡도, 공간 복잡도

 

시간 복잡도

- 알고리즘을 이루는 명령들이 몇 번 수행되는지 숫자로 표시

 (산술, 대입, 비교 연산)

- 연산의 수행 횟수는 입력된 개수(n)에 의해 결정되므로 n의 함수로 표시된다 -> T(n)

   ex) T(n)= n^2+n+1 일 때,

             n이 커지면 +n 이나 +1의 영향력은 무시할 만하다.

                결국 n^2만 고려해도 충분하다.

 --> O (빅 오) 표기법 : 가장 크게 영향을 미치는 항 만 고려 

          ex) T(n)= n^2+n+1 일 때, 시간 복잡도는 O(n^2)