빅오, 자료형
- 빅오
입력 값(데이터 갯수)이 무한대로 향할 때 함수의 상한(실행 시간의 추기)을 설명하는 수학적 표기 방법
시간 복잡도와 공간 복잡도를 표기하는 방법 중 하나
- 시간 복잡도
어떤 알고리즘을 수행하는 데 걸리는 시간을 설명하는 계산 복잡도
최고차항만을 표기하며 계수는 무시함
- O(1)
입력값이 아무리 커도 실행 시간이 일정한 경우
- O(log n)
실행 시간이 입력값에 영향을 받는 경우
매우 큰 입력값에도 크게 영향을 받지 않음
- O(n)
알고리즘을 수행하는 데 걸리는 시간이 입력값에 비례하는 경우
- O(n log n)
대부분의 효율 좋은 정렬 알고리즘
- O (n^2)
비효율적인 정렬 알고리즘
- O(2^n)
피보나치 수를 재귀로 계산하는 알고리즘
O (n^2) 보다 훨씬 큼
- O(n!)
외판원 문제를 브루트 포스로 푸는 경우
가장 느린 알고리즘
- 공간 복잡도
어떤 알고리즘을 수행하는 데 걸리는 공간(메모리)을 설명하는 계산 복잡도
- 트레이드 오프
알고리즘은 시간 복잡도와 공간 복합도가 반비례적인게 일반적
아닐 수도 있음
- 상한과 최악
빅오는 상한을 의미
빅오 표기법은 정확하게 쓰기에는 너무 길고 복잡한 함수를 ‘적당히 정확하게’ 표현하는 방법이라 최악의 경우/평균적인 경우의 시간 복잡도와 관계가 없음
- 상한, 하안 평균
빅 오는 n 이 매우 클 때의 전체적인 큰 그림에 집중함
빅오 표기법은 주어진 (최선/최악/평균) 경우의 수행 시간의 상한을 나타냄
- 상한
가장 늦게 실행될 때
빅 오를 뜻 함
- 하안
가장 빨리 실행될 때
빅 오메가를 뜻 함
- 평균
평균적으로 실행될 때
빅 세타를 뜻 함
- 최악, 평균, 최선
알고리즘의 자원의 사용량을 말함
- 분할 상환 분석
최악의 경우를 여러 번에 걸쳐 골고루 나눠주는 형태로 알고리즘의 시간 복잡도를 계산하는 것
알고리즘의 복잡도를 계산할 때 알고리즘 전체를 보지 않고 최악의 경우만을 살펴보는 것은 지나치게 비관적이라는 이유로 등장함
- 병렬화
문제를 여러 개의 CPU 로 풀어 시간을 단축시키는 것
알고리즘 자체의 시간 복잡도 외에도 알고리즘이 병렬화가 가능한지도 알고리즘 우수성 평가 척도 중 하나가 됨
- 자료형
- 숫자
불변형
가변 정밀도라 정밀도 보장 가능
- 논리 자료형
True 는 1, False 는 0 이라는 값 가지고 있어서 숫자형에 들어감
- 임의 정밀도
무제한 자릿수를 제공하는 정수형
정수를 숫자의 배열로 간주하는 것
계산 속도가 저하되지만 언어를 단순한 구조로 만들 수 있고 오버플로우를 고민할 필요가 없음
- 매핑
키와 자료형으로 구성된 복합 자료형
딕셔너리가 속함
- 집합
중복된 값을 갖지 않는 자료형
입력 순서 유지되지 않음
- 시퀸스
특정 대상의 순서 있는 나열
- 불변
값을 변경할 수 없는 시퀸스
문자열, 튜플, 바이트가 있음
- 가변
값을 변경할 수 있는 시퀸스
list 가 있음
- 원시 타입
- 원시 타입
메모리에 정확하게 타입 크기만큼의 공간을 할당하고 그 공간을 오로지 값으로 채워 넣음
매우 빠른 연산이 가능
- 객체
값에 여러 기능을 추가한 것
메모리를 많이 소모하며 상대적으로 느림
파이썬은 모든 것이 객체
- 불변 객체
변할 수 없는 객체
문자, 숫자, 가변 시퀸스가 해당함
변수의 값이 바뀌면 참조값 (메모리 주소 값)이 바뀜
- 가변 객체
변할 수 있는 객체
list 와 딕셔너리가 해당함
변수의 값이 바뀌면 참조값(메모리 주소 값)이 바뀌지 않음
- is 와 ==
is 는 id() (메모리 주소 값)을 비교하는 함수
== 는 값을 비교
- 속도
파이썬은 모든 것을 객체로 해서 느림
값을 꺼내는 데만 해도 헤더에서 타입 코드를 찾는 등의 여러 단계의 부가 작업 필요
값을 다루기 편리함
- 자료구조, 자료형, 추상 자료형
자료구조는 데이터에 효율적으로 접근하고 조작하기 위한 데이터의 조직, 관리, 저장 구조
자료형은 컴파일러나 인터프리터에게 프로그래머가 데이터를 어떻게 사용하는지 알려주는 일종의 데이터 속성
추상 자료형은 해당 유형의 자료에 대한 연산들은 명기한 것이며 행동만 정의할 뿐 실제 구현 방법은 명시하지 않음