전북대학교 알고리즘 합병정렬 5조 안준철

1. 알고리즘 이란?

원래는 인도에서 아랍를 거쳐 유럽에 보급된 필산(筆算)을 뜻하며, 아랍의 수학자인 알콰리즈미의 이름에서 유래한다.

어떠한 문제를 효율적으로 풀기 위한 방법의 단계나 절차 정도로 설명할 수 있을 것이다. 즉, 문제가 주어져 있을 때,

그냥 아무렇게나 풀지 않고 좀더 효율적으로 풀기 위해 알고리즘 사용하는 것이다.

또한, 알고리즘은 수학용어와 컴퓨터 용어 두 가지로 나누어 설명할 수 있다.

1) 수학용어로서 알고리즘은 잘 정의되고 명백한 규칙들의 집합 또는 유한 번의 단계 내에서 문제를 풀기 위한 과정이다.

   예를 들면, 주어진 정확도에 맞도록 x의 코사인 값을 계산하기 위한 대수적인 과정도 알고리즘에 해당된다.

   경험적 지식(heuristic)과 반대되는 용어이다.

2) 컴퓨터용어로서 알고리즘은 어떤 문제의 해결을 위해 컴퓨터가 사용 가능한 정확한 방법을 말한다.

    알고리즘은 여러 단계의 유한한 집합으로 구성되는데, 여기서 각 단계는 하나 또는 그 이상의 연산을 필요로 한다.

2. 알고리즘의 조건

알고리즘은 일반적으로 다음의 조건을 만족해야 한다.

①입력 : 외부에서 제공되는 자료가 0개 이상 존재한다.

②출력 : 적어도 1개 이상의 결과를 내어야 한다.

③명확성 : 각 명령어들은 명확하고 모호하지 않아야 한다.

④유한성 : 알고리즘의 명령어들은 유한번의 수행후에 종료되어야 한다. 이것은 수행 시간 의 현실적인 유한성을 의미한다.

⑤효과성 : 모든 명령어들은 원칙적으로 종이와 연필만으로 수행될 수 있는 기본적인 것이어야 한다.

3. 알고리즘의 연구 분야

① 고안 : 완벽한 자동화를 통한 알고리즘의 개발은 거의 불가능하다. 따라서 이미 증명된 유용한 알고리즘들을 습득함으로써 보다 유용한

              알고리즘을 개발하는데 그 의미가 있다.

② 검증 : 고안된 알고리즘이 합당한 입력값에 대하여 올바른 결과를 계산해 내는지를  밝히는 절차가 필요하다.

              알고리즘 검증은 고안된 알고리즘이 프로그래밍 언어와는 독립적으로 올바르게 작동할 수 있음을 보여주는데 그 목적이 있다.

③ 분석 : 고안된 알고리즘을 실행하기 위해 필요한 실행시간과 필요로 하는 기억장치를 결정하는 것이다.

④ 테스트 : 디버깅, 성능분석

4.알고리즘의 분석 기준

① 정확성 : 적당한 입력에 대해서 유한 시간내에 올바른 답을 산출하는가를 판단.

② 작업량 : 전체 알고리즘에서 수행되는 가장 중요한 연산들만으로 작업량을 측정. 해결하고자 하는 문제의 중요 연산이 여러개인 경우에는

                각각의 중요 연산들의 합으로 간주하거나 중요 연산들에 가중치를 두어 계산

③ 기억 장소 사용량

④ 단순성

⑤ 최적성 : 그 알고리즘보다 더 적은 중요 연산을 수행하는 알고리즘은 없는가? 최적이란   가장 잘 알려진 이 아니라 가장 좋은의 의미이다.

5. 평균과 최악의 경우 분석

O(1) : 입력 자료의 수에 관계없이 일정한 실행 시간을 갖는 알고리즘

O(log N) : 주로 커다란 문제를 일정한 크기를 갖는 작은 문제로 쪼갤 때 나타나는 유형

O(N) : 입력 자료에 따라 선형적으로 실행 시간이 걸리는 경우

O(N log N) : 커다란 문제를 독립적인 작은 문제로 쪼개어 각각에 대해 독립적으로 해결하고, 나중에 다시 그것들을 하나로 모으는 경우에 나타남.

O(N2) : 이중 루프 내에서 입력 자료를 처리하는 경우에 나타남.그러나 N의 크기가 작을 때에는 N2이 NlogN보다 작을 수 있음.

O(N3) : 삼중 루프.

O(2n) : 가끔씩 알고리즘을 처음 개발할 때 나타날 수 있는 수행시간..

6. 알고리즘의 종류

알고리즘의 종류는 셀 수 없이 많다. 많이 쓰이는 알고리즘으로는 소트와, 탐색 알고리즘의 DFS, BFS, 기하 알고리즘의

Convex Hull(알고리즘이라기보다는 문제에 가깝다), 탐색 알고리즘의 이분탐색, 선형탐색, 블록 탐색, 암호화 알고리즘 등이 있다.

 훨씬 더 많은 종류의 알고리즘이 있으나 가장 쉽게 접할 수 있는 알고리즘만 모아 보았다.

7. 알고리즘의 예

정렬 알고리즘

정렬 알고리즘은 내부정렬과 외부정렬로 나눌 수 있다.

내부정렬(internal sorting)은 정렬하고자 하는 모든 요소들(elements)이 동시에 주 메모리(main memory)에서 정열되어 지는 것을 말하며,

외부정렬(external sorting)은 반대로 정렬하고자 하는 특정 요소들(elements)이 주 메모리(main memory)에서 정열되고,

나머지 대부분 요소들은 외부저장 장치(secondary memory)에 존재하는 것이다.

내부정렬에는 다음과 같은 것이 있다.

  거품 정렬 (bubble sort)

  삽입 정렬 (insertion sort)

  셸 정렬 (shell sort)

  선택 정렬 (select sort)

외부정렬에는 다음과 같은 것이 있다.

  퀵 정렬 (quick sort)

출처:

http://alg.devlife.net/Algorithms/Algorithms.aspx
http://alg.devlife.net/Algorithms/Algorithms.aspx
http://alg.devlife.net/Algorithms/Algorithms.aspx

이 글과 관련있는 글을 자동검색한 결과입니다 [?]

• 전북대학교 알고리즘 합병정렬 3조 by hwanny84
• 전북대학교 알고리즘 합병정렬 5조 - 알고리즘 & 자료구조 by prettyhip