빅오, 자료형
빅오
- 빅오는 입력값이 무한대로 향할때 함수의 상한을 설명하는 수학적 표기 방법
빅오 표기법의 종류
O(1)
O(log n)
- 로그는 매우 큰 입력값에도 크게 영향을 받지 않는 편
- 대표적으로 이진 검색
O(n)
- 입력값과 수행 시간이 비례
- 이 시간복잡도를 가지는 알고리즘을 선형 시간 알고리즘이라고 함
- 정렬되지 않은 리스트에서 최댓값 또는 최솟값을 찾는 경우에 해당
O(n log n)
- 병합 정렬을 비롯한 대부분의 효율 좋은 정렬 알고리즘에 해당
- 모든 수에 대해 한 번 이상은 비교해야 하는 비교 기반 정렬 알고리즘의 최선의 시간 복잡도
- Timesor와 같이 모든 비교를 건너뛸 경우, O(n) 이 될 수 있음
O(n^2)
- 버블 정렬과 같은 비효율적인 정렬 알고리즘에 해당
O(2^n)
- 피보나치 수를 재귀로 계산하는 알고리즘에 해당
- O(2^n)보다 훨씬 큼
O(n!)
- 가장 느린 알고리즘
- 각 도시를 방문하고 돌아오는 가장 짧은 경로를 찾는 외판원 문제를 브루트 포스로 풀이할 때가 이에 해당
상한과 최악
- 빅오(O)는 상한, 빅오메가는 하한, 빅세타는 평균을 의미
- 빅오 표기는 주어진 최선/최악/평균에 대한 경우의 수에서 수행 시간의 상한을 나타냄
분할 상환 분석
- 분할 상환 분석(Amortized Analysis)은 빅오와 함께 함수의 동작을 설명할 때 중요한 분석 방법 중 하나
- 상각이라고도 표현함
- 최악의 경우를 여러 번에 걸쳐 골고루 나눠주는 형태로 알고리즘의 시간 복잡도를 계산
병렬화
- 딥러닝과 같이 GPU의 병렬 연산을 통해 실행 속도를 높일 수 있음
자료형
파이썬 자료형
- 파이썬 기초에서 다뤘음
is 내장 함수는 참조하는 id()함수가 리턴하는 값을 비교하고, ==는 값을 비교하는 연산자
자료구조, 자료형, 추상 자료형
자료구조
- 컴퓨터과학에서는 데이터에 효율적으로 접근하고 조작하기 위한 데이터의 조직, 관리, 저장 구조를 말함
자료형
- 컴파일러 또는 인터프리터에게 프로그래머가 데이터를 어떻게 사용하는지를 알려주는 일종의 데이터 속성(Attribute)
- 자료구조에 비해 훨씬 구체적
- 복합 자료형 : 자료형의 관점에서 여러 원시 자료형을 조합한 자료구조
추상 자료형
- 추상 자료형 : 자료형에 대한 수학적 모델을 지칭
- 실제 구현 방법은 명시하지 않고, 행동만을 정의