- 캡슐화 : 정보 은닉
- 추상화 : 데이터 객체의 명세와 구현을 분리하는 것
- 데이터 타입 : 객체들과 이들 객체들에 대해 동작하는 연산들의 집합(int, 산술연산자)
- 추상 데이터 타입(ADT) : 기능의 구현을 나타내지 않고 정의만 한 것
- 복잡도(complexity) : 프로그램은 실행하는 하드웨어에 따라 실행 시간이 다르므로 컴퓨터에 관계없이 시간과 공간을 추산하는 것
시간 복잡도, 공간 복잡도
- 성능 평가 : 성능 분석(사전 예측), 성능 측정(사후 검사)
(1) 성능 분석
- 공간 복잡도 : 필요한 공간의 크기, 고정공간과 가변공간
- 시간 복잡도 : 프로그램이 실행될 때 피료한 실행분의 실행 횟수(count문 삽입, 실행문의 빈도수 계산)
- 성능 분석을 위한 점근 표기법
* 점근 표기법이란? 대략적으로 수행시간이나 공간을 예측하기 위해 사용
1) 빅오(O)
상한선 표기법
모든 n, n ≥n0 에 대해 f(n) ≤cg(n) 인 두 개의 상수 c 와 n0가 존재한다면 f(n) = O(g(n) )
만약 f(n) = am nm + … + a1 n + a0 이면, f(n) = O(nm)
2) 오메가(Ω)
하한선 표기법
모든 n, n ≥n0 에 대해 f(n) ≥ cg(n) 인 두 개의 상수 c 와 n0가 존재한다면 f(n) = Ω(g(n) )
3) 세타(Θ)
모든 n, n ≥n0 에 대해 c1 g(n) ≤ f(n) ≤c2 g(n) 인 세 개의 상수 c1 , c2 와 n0가 존재한다면 f(n) = Θ(g(n) )
(2) 성능 측정
- time 함수 사용(시간이 0인 경우, 여러 번 반복한 후 전체 시간을 반복 횟수로 나눔)
(3) 테스트 데이터의 생성
- 일반적으로 쉽게 테스트 데이터를 얻을 수 없음
- 최악의 경우 : 대규모의 무작위 데이터에 대한 결과값들 중 최대값
- 평균의 경우 : 대유모의 무작위 데이터에 대한 결과값들 중 평균값
