ㅇ 알고리즘의 조건
- 입력 : 0개 이상 - 출력 : 1개 이상 - 명백성 - 유한성 - 유효성
ㅇ 알고리즘의 기술 방법
자연어 : 읽기 쉽지만 의미 전달 모호해질 수 있다
흐름도 : 직관적이고 이해하기 쉬우나 복잡한 알고리즘의 경우 상당히 복잡해진다
의사코드(pseudo-code) : 핵심적인 내용에 집중가능
프로그래밍 언어 : 구체적 사항 때문에 핵심적인 내용 이해 방해할 수 있다.
ㅇ 자료형(data type) : ( 데이터 + 연산)
ㅇ 추상 데이터 타입 (ADT) : (객체 + 연산)
: 데이터나 연산이 무엇(What) 인가는 정의 되지만 어떻게(How) 컴퓨터 상에 구현할 것인지는 정의되지 않는다.
ㅇ 알고리즘의 성능분석
- 수행 시간 측정
- 알고리즘의 복잡도 분석 (1.시간 복잡도 2.공간 복잡도)
1) 시간 복잡도 : 알고리즘을 이루고 있는 연산들이 몇 번이나 수행되는지 숫자로 표시 ex) 빅오표기법
2) 공간 복잡도
ㅇ 빅오 표기법 : 연산의 횟수를 대략적으로 표기 한것
: 자료의 개수가 많은 경우에는 차수가 가장 큰 항이 가장 영향을 크게 미치므로 다른 항은 무시 될 수 있다
: 함수의 상한을 표시
O(1) : 상수형
O(logn) : 로그형
O(n) : 선형
O(nlogn) : 선형로그형
O(n²) : 2차형
O(n³) : 3차형
O(2ⁿ) : 지수형
O(n!) : 팩토리얼형