알고리즘과 알고리즘의 성능

알고리즘의 정의

• 어떤 일을 하는 절차를 말한다.
• 컴퓨터에서는 프로그램이 수행할 작업을 말한다.
• 정의 : Definition
  • 명령의 집합
• 조건 : Criteria - 알고리즘이 갖출 조건
  • 입력이 있다.
  • 출력이 있다.
  • 명확해야한다.
  • 유한성
• 알고리즘의 서술은 3가지 기능(순서, 반복, 조건)으로 한다.

일상생활의 알고리즘의 예

• 알고리즘은 명령어들이 다음과 같이 3가지로 합성된다.
  • 순차 : 명령어 다음에 명령어가 나온다. (순서가 정해져 있다.)
  • 반복 : 명령어가 반복이 된다.
  • 조건 : 조건에 따라 명령의 수행이 결정된다.

컴퓨터의 알고리즘의 예

• 데이터 개수 n개에서 큰 수를 찾는 알고리즘을 기술하여 보자.
• 데이터를 한 개씩 읽어서 가장 큰 수 라고 기억된 수와 비교하여 큰 수를 찾아 나간다.

정렬과 검색 알고리즘

• 정렬 : 흩어져 있는 데이터를 키 값 (주민번호, 학번 등)을 이용하여 순서대로 열거하는 알고리즘
• 검색 : 데이터에서 키 값에 해당 되는 데이터를 찾는 알고리즘

정렬 알고리즘

• 정렬 : n개의 데이터를 정렬한다
• 선택정렬 : n개의 데이터를 놓고 가장 작은 수를 골라 정렬될 장소에 이동한다. (n-1)개 데이터를 매번 한 개씩 줄어든 데이터로 위의 과정을 반복한다.
• 코드

void selection_sort(int *a, int*b){
int i, j, small, temp;
//int a[10], b[10];
small=0;
for (i=0;i<1;i++){if(a[small]>a[i])small=i;}
b[0]=a[small];a[small]=99; //이 문장에서 b 배열의 숫자를 변경하면 된디야
...
}

• 선택 정렬 알고리즘 : 가장 작은 수를 선택하여 재 배치
• 코드

void selection_sort(int*a, int*b){
int i, j, small, temp;//int a[10], b[10];
for (j=0;j<10;j++{
small=j;
for (int i=(j+1);i<10;i++){
if(a[small]>a[i])small=i;}
temp=a[small];a[small]=a[j];a[j]=temp;}}

• 선택정렬 알고리즘 작성
  1. 정렬되지 않은 데이터에서 가장 작은 수를 골라 정렬된 리스트의 (i 번째, i=0, 1,2,….)에 붙인다.
  2.  for(i=0;i<n-1;i++){ list[i] 부터 list[n-1] 까지 비교하여 가장 작은 수가 list[min]이라 하자;
  3. list[i]와 list[min]을 교환한다;

for (i=0;i<n-1;i++){
min = i;
for(j=i+1;j<n;j++){
if(list[j]<list[min]) min=j;}
temp=list[min]; list[min]=list[i]; list[i]=temp;}

•  

검색 알고리즘

• 검색 : n 개의 데이터를 검색한다
• 선형 검색 알고리즘 : 가장 간단한 검색 알고리즘, n개의 데이터를 놓고 한 개씩 검색하는 방법이다.
• 이진검색 : 데이터가 정렬이 된 상태에서 검색하는 방법, 이진 검색은 전체 데이터의 중간에 있는 데이터를 비교하면서 찾는 데이터가 앞/뒤 중 어디 있는지 알 수 있다.

알고리즘의 성능

• 성능
  • 성능 분석
    • 컴퓨터에 상관없이 시간과 공간의 추산에 초점을 둔다.
    • 복잡도 이론
  • 성능 측정
    • 컴퓨터에 의존적인 사건을 알아 내는 것이다. 컴퓨터에서 직접 실행하여 정확한 시간을 측정한다.
• 공간 복잡도 : 프로그램을 실행시켜 완료되는데 필요로 하는 기억 장소의 크기
• 시간 복잡도 : 프로그램을 실행시켜 완료하는 데 필요한 컴퓨터 시간의 양을 의미

 

자세한 사항 : https://tame-neptune-1a0.notion.site/2-6f4bec8e87ab44f1b93ade109c6236c2