[패캠강의][작성중]이산수학 - ch4. 알고리즘과 시간복잡도

 

1. 개요

 

컴퓨터 공학적 알고리즘 보다는 수학적 알고리즘의 의미를 학습한다.

 

알고리즘

문제를 해결하기 위한 방법을 순차적으로 나열한 것

 

알고리즘의 특징

입력 : 입력값을 가진다.

출력 : 출력값을 가진다.

유한성(finiteness) : 유한 시간 내에 종료되어야 한다.

정확성(precision) : 각각의 중간과정은 명확하게 서술되어야 한다.

일반성(generality) : 여러 입력값에 대해 적용 가능해야 한다.

 

 

알고리즘 분석 기준

정확도 : 값이 얼마나 정확한가

코드 복잡도 : 코드가 인간이 보기에 얼마나 복잡한가

공간 복잡도 : RAM, 하드디스크 등의 하드웨어를 얼마나 사용하는가

시간 복잡도 : 주어진 입력자료에 대해 실행시간이 얼마나 긴 가

 

정확도와 시간 복잡도가 가장 객관적이고 중요할 수 있는 개념이다.

 

 

시간 복잡도 표기법

두 양의 정수 c와 n0가 존재하여 n ≥n0 인 모든 n에서 |f(n)|≤c|g(n)| 를 만족하면 f(n)=O(g(n))이라고 쓰고, f(n)은 Big-O 또는 줄여서 O(g(n))이다 라고 읽는다. 이러한 표기법을 빅-오 표기법(notation)이라고 부른다.

일반적으로 g(n)에 들어가는 함수는 1,log⁡n, n, n log⁡n, n^2, n^3, n! 등이 있다.

 

참조 2의 그림

 

예를 들어 f(n) = 2n^2 + 3n + 1이고, g(n) = n^2 이라면 n > n0 일 때 부등식 |f(n)| < c|g(n)|을 만족하는 c와 n0쌍은 (6,1), (5,2), (4,3) 등이 있을 수 있다. 따라서 2n^2 + 3n + 1 = O(n^2) 이다. 다시 말해 빅오 표기법은 n에 따른 함수의 상한을 나타낸다.

 

 

 

 

---

참조

 

1. 패스트 캠퍼스 - 한 번에 끝내는 컴퓨터 공학 전공필수 & 인공지능 심화 초격차 패키지 Online.

Part2. 이산수학 - 강승현 강사님

 

2. 블로그 - SoySauce['Record']

https://velog.io/@leobit/%EB%B3%B5%EC%9E%A1%EB%8F%84Complexity