2.1. 빅오 표기법

모든 n > n0에 대해 0 <= f(n) <= cg(n)인 양의 상수 c, n0가 존재하면 f(n) = O(g(n))

• f(n) = 2n+5, n0 = 5, c = 3일 경우, cg(n) = 3n
• f(n)과 cg(n)이 만나는 지점인 n0 이후부터는 항상 모든 n에 대하여 f(n) < cg(n)이며, f(n) > 0 만족
• 빅오는 상한을 의미함 : f(n)은 n0 이상부터 cg(n)의 상한을 절대 넘지 않는다.

2.1.1. 종류

1. O(1) : 상수 시간. 자료구조에 저장된 데이터와 개수와 상관없이 정해진 연산 안에서 알고리즘 마무리
   ex) 동적 배열의 인덱싱
2. O(log n) : 로그 시간.
   ex) 이진트리계열의 연산(삽입,삭제, 탐색)
3. O(n) : 선형시간. 데이터 개수 늘어날 수록 선형으로 연산 시간 증가
   ex) 연결리스트의 탐색연산, 동적배열 삽입, 삭제(마지막 원소 추가하는 연산은 제외)
4. O(nlog n) : 선형 로그 시간
   ex) 퀵 정렬, 병합 정렬
5. O(n2), O(n3) : 데이터 개수에 따라 가파르게 연산 횟수 증가
   ex) 이중 for 문, 삼중 for 문
6. O(2n) : 지수 시간.

2.2. 추상데이터 타입(ADT)

객체나 연산의 명세에서 객체의 표현이나 연산의 구현을 감춘 것.

• 객체의 표현 : 파이썬은 자료형이 없으므로 실제 메모에 어떠한 크기로 저장되는지 감추어져 있음.
• 연산의 구현 : 내부적으로 어떻게 구현되는지를 감춤

2.2.1. 데이터 타입

데이터를 저장하는 객체(object)와 객체가 할 수 있는 연산(operation)의 집합.

• 객체 : 데이터 타입이 나타낼 수 있는 모든 타입의 집합
• 연산 : = 메서드, 즉, 연산 명세 시 메서드 이름, 매개변수, 반환값 반드시 표기