[알고리즘] 1주차: 02. 알고리즘 설계와 분석의 기초

02. 알고리즘 설계와 분석의 기초

1. 알고리즘의 표현 - 의사코드 pseudo code
   • 프로그램 작성 시 각 모듈이 작동하는 논리를 표현하기 위한 언어
   • 일반적인 언어로 프로그래밍 코드와 유사하게 표현
   • 알고리즘 표현 or 모델링에 사용

2. 점근적 분석 : 입력 크기가 클 때 분석 방법
   • 변수가 커짐에 따라 함수가 증가하는 비율을 표현하는 방법
   • 무한을 간단하게 표기
   • Big O, theta, omega
3. Big O notation
   • 최악의 경우 소요되는 시간
   • 계수와 상수는 버림. 차수만 중요
4. 세타 표기법 : 점근적 증가율이 f(n)과 일치하는 모든 함수 집합 (평균)
5. 빅오 표기법 : 점근적 증가율이 f(n)을 넘지 않는 모든 함수 집합 (상한)
6. 오메가 표기법 : 점근적 증가율이 적어도 f(n)이 되는 모든 함수 집합 (하한)
   
   

문제

1. ( 오메가 ) 표기로 나타낸 하한과 ( 빅오 ) 표기로 나타낸 상한이 일치하면 상한과 하한이 일치해서 ( 세타 ) 표기를 사용할 수 있다.
2. 변수의 크기가 충분히 큰 경우에 변수가 커짐에 따라 함수가 증가하는 비율을 표현하는 방법을 살펴보았다. 이를 함수의 점근적 증가율이라고 하고, 그 표기법을 ( 점근적 표기법 ) 이라 한다.

 

출처

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

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

알고리즘