[알고리즘] 1주차: 01. 알고리즘 개요

01. 알고리즘 개요

1. 알고리즘 : 문제해결을 위한 방법을 수학적 명령이나 규칙의 집합으로 표현한 것
2. 알고리즘의 효율
   1. 문제해결 관점 : 최소시간
   2. 방법의 기술 관점 : 결과물이 같아도 방법이 서로 다름 -> 가장 빠른 방법이 가장 효율적이다
3. 알고리즘: 명확(프로그래밍 언어로 변환 용이)하고 효율적(처리 시간,공간(메모리))이어야함
4. 소요시간을 얼마나 소모하는가 : 최악, 평균... 데이터 양에 따라 대략적으로 얼마나...
5. 알고리즘의 수행시간
   • 상수 시간 : n의 크기와 상관 없이 일정한 시간 소요
   • 선형 시간 : n의 크기에 비례하여 수행 시간 증가
   • 제곱 시간 : n의 제곱에 비례하여 수행 시간 증가
   • 재귀 호출 : 예시; 팩토리얼 구하기 n에 비례해서 증가어떤 문제 안에 크기만 다른 같은 문제들이 포함되기도 함 (수열의 점화식) ... 수학적 귀납법수학적 귀납법 : 작은 문제에 대한 결론이 옳다고 가정하고 자신과 작은 문제와의 관계를 볼 때 자신에게도 결론이 옳다는 것을 보이는 것예) 병합정렬 merge sort : 한번 호출할때마다 반씩 줄어들어서 log(2n)번 호출이 됨

---

문제

1. 알고리즘의 수행시간은 입력의 크기에 비례한다

    알고리즘이 수행되는데 걸리는 시간은 입력 데이터의 크기가 얼마나 되는가에 따라 비례하여 증가

 

2. 작은 문제에 대해 결론이 옳음을 가정하고 자신과 이 작은 문제의 관계를 통해서 자신에게도 결론이 옳음을 보이는 것을 수학적 귀납법이라 한다.

 

 

 

출처

K-MOOC : 선복근 교수님 - 알고리즘

http://www.kmooc.kr/courses/course-v1:HOSEO+HOSEOSW01+2021_12/about 

알고리즘