1장 자료구조와 알고리즘
- 정리의 기반은 학교 강의 노트와 [c언어로 쉽게 풀어쓴 자료구조]를 참고하였습니다.
저의 정리가 옳지 않다면 피드백 부탁드립니다.
알고리즘의 특징
- 0개 이상의 입력
- 1개 이상의 출력
- 명령어 명확(명확성)
- 한정된 수의 단계 후 반드시 종료(유한성)
- 명령어들은 종이와 연필, 또는 컴퓨터로 실행 가능한 연산(유효성)
알고리즘의 시간 복잡도 : 연산들이 몇번 수행되는지
알고리즘의 공간 복잡도 : 기억 공간 분석
빅오 표기법
- 2개의 함수 f(n)과 g(n)이 주어졌을 때 모든 n > n0에 대하여 f(n) <= g(n)을 만족하는 2개의 상수 c와 n0가 존재하면 f(n) = O(g(n))이다.
- 그냥 단순히 생각하면 차수가 가장 큰 것을 나타내는 표기법이다. ex) f(n) = n^3 + n^2 가 있으면 O(f(n)) = n^3 인 셈.
- 알고리즘의 점근 성능이다.
- 상한 성능
+a 빅오메가 표기법 : 엄격한 하한
+a 빅 세타 표기법 : 상한 + 하한
알고리즘의 경우
말 그대로 받아들이면 된다. 보통 최악의 경우와 평균의 경우가 언급된다.
- 최악의 경우
- 최선의 경우
- 평균의 경우