이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다.
4장 빅오, 자료형
1) 빅오
- 빅오란?
- 입력값이 무한대로 향할 때 함수의 상한을 설명하는 수학적 표기법
= 점근적 실행 시간(Asymptotic Running Time)을 표기할 때 가장 널리 쓰이는 수학적 표기법 중 하나 - 시간 복잡도(Time Complexity) = 점근적 실행 시간
어떤 알고리즘을 수행하는 데 걸리는 시간을 설명하는 계산 복잡도(Computational Complexity) - 빅오로 시간 복잡도를 표현할 때는 최고차항만 표기, 계수 무시
(ex) $$4n^2+3n+4 \approx O(n^2)$$
- 입력값이 무한대로 향할 때 함수의 상한을 설명하는 수학적 표기법
- 빅오의 종류
1 O(1) 해시 테이블 상수 시간 매우 가치있음 2 O(log n) 이진 탐색 입력에 영향이 적음 3 O(n) 순차 탐색 선형 시간 입력값에 비례 4 O(nlog n) 팀소트, 병합정렬 효율이 좋은 정렬 알고리즘이 해당 5 O(n2) 버블 정렬 지수 시간 비효율적인 알고리즘 6 O(2n) 피보나치 + 재귀 7 O(n!) TSP + brute force 가장 느린 알고리즘
- O(1) - 상수 시간
- 입력값이 커도 실행 시간이 일정
- 매우 가치가 큰만큼 신중해야함
- 상수 시간이 매우 크면 의미가 없음
- (ex) 해시 테이블
- O(log n)
- 큰 입력값에도 영향이 적은 편
- (ex) 이진 검색
- O(n) - 선형 시간
- 실행 시간이 입력값에 비례
- 모든 입력값을 적어도 한 번 이상 살펴봐야하는 경우
- (ex) 정렬되지 않은 리스트에서 최댓값/최소값 찾을 때?
- 단순한 순차탐색의 경우를 의미하는 듯
- O(nlog n)
- 대부분 효율 좋은 정렬 알고리즘의 시간복잡도
- 적어도 한 번 이상 비교해야하는 비교 기반 정렬 알고리즘은 이보다 빠를 수 없음
- 그러나 입력값이 최선인 경우 비교를 건너 뛰어 O(n)이 될 수 있음
- 팀소트(Timsort) - (ex) 병합 정렬
- O(n2)
- 비효율적인 알고리즘의 시간복잡도
- (ex) 버블 정렬
- O(2n)
- (ex)피보나치 수를 재귀로 계산하는 알고리즘의 시간복잡도
- 각 함수호출마다 최대 2번 재귀호출
- n값이 커질 때마다 재귀호출의 depth가 늘어남 - n2과 비교할 때
- n = 4까지는 큰 차이가 없음
- n = 15일 때, 225와 32768로 145배 이상 차이가 벌어짐
- (ex)피보나치 수를 재귀로 계산하는 알고리즘의 시간복잡도
- O(n!)
- (ex) TSP를 brute force로 해결하는 알고리즘의 시간복잡도
- 가장 느린 알고리즘?
- 가장 느린지는 모르겠지만, NP problem 중 대표적인 문제에 해당
- O(1) - 상수 시간
- 공간 복잡도
- 빅오는 공간 복잡도를 표현하는 데에도 쓰임
- 보통 시간과 공간은 트레이드 오프 관계
- 상한과 최악
- 빅오(O)는 상한(Upper Bound)를 의미
- 빅오메가(Ω)는 하한(Lower Bound), 빅세타(Θ)는 평균
- 학계와 달리 업계는 빅세타와 빅오를 합쳐서, 상한 시간으로 단순 표현
- [주의] 상한을 최악의 경우와 혼동하는 것
- 빅오 표기법은 복잡한 함수를 적당히 표현한 방법임
- 최악의 경우/ 평균적인 경우의 시간 복잡도와 아무 관계가 없는 개념
- 참고자료
2021.07.02 - [개발/개발지식] - 빅오(O)는 왜 최악의 경우가 아닐까
빅오(O)는 왜 최악의 경우가 아닐까
상한보다 최악이 있는가 헷갈리는 부분이라 고민을 해보고 싶어서 작성한다. 먼저 시간 복잡도에서 빅오는 충분히 큰 입력을 가정하며, 입력에 대한 연산수로 알고리즘의 실행 시간을 표기하는
pythaac.tistory.com
- 분할 상환 분석 (Amortized Analysis)
- 알고리즘의 복잡도를 계산할 때, 최악의 경우만 살펴보는 것이 비관적이란 이유로 등장한 분석 방법
- 분할 상환 분석이 유용한 대표적인 예 : 동적 배열
- 동적 배열에서 doubling이 일어나는 일은 어쩌다 한 번 뿐임
- 그럼에도 doubling으로 인해 아이템 삽입 시간 복잡도가 O(n)
- 이 경우, 최악의 경우를 여러 번에 걸쳐 골고루 나눠주는 형태로 시간 복잡도를 계산(분할 상환, 또는 상환이라 함)
- 이로 인해 동적 배열의 삽입 시간 복잡도는 O(1) - 참고자료
2021.07.09 - [개발/개발지식] - [번역 - Cornell Univ.] 분할 상환 분석 (Amortized Analysis)
[번역 - Cornell Univ.] 분할 상환 분석 (Amortized Analysis)
출처 : http://www.cs.cornell.edu/courses/cs3110/2011sp/Lectures/lec20-amortized/amortized.htm Lecture 20: Amortized Analysis Lecture 20: Amortized Analysis The claim that hash tables have O(1) expec..
pythaac.tistory.com
- 병렬화
- 일부 알고리즘은 병렬화로 실행 속도를 높일 수 있음
- 딥러닝의 인기와 함께 병렬화가 주목받고 있음
- GPU는 병렬 연산을 위한 대표적인 장치
- GPU의 각 코어는 CPU보다 느리지만 수천여 개로, CPU보다 수백 배 더 많은 연산을 동시에 수행 - 알고리즘이 병렬화가 가능한지는 근래 알고리즘의 우수성 평가에 매우 중요한 척도 중 하나
2) 자료형
- 파이썬 자료형
출처 : <파이썬 알고리즘 인터뷰> p.107, 책만, 2020 - 숫자
- 파이썬에는 숫자 정수형으로 int만 제공
- PEP 237을 통해, 임의 정밀도(Arbitrary-Precision) 정수형인 int 하나만 제공
- bool은 내부적으로 int의 서브 클래스
- True == 1, False == 0 (True == 2는 False) - 매핑
- key와 자료형으로 구성된 복합 자료형
- 딕셔너리가 해당 - 집합
- 중복된 값을 갖지 않는 자료형
- 선언 : a = set() 또는 a = {1, 2, 3}
- 딕셔너리와 동일하게 중괄호를 사용하는 것 주의
- 입력 순서가 유지되지 않음 - 시퀀스
- 순열 같은 의미 : 어떤 특정 대상의 순서 있는 나열
- str과 list 비교 : str은 문자의 순서 있는 나열, list는 다양한 값의 순서 있는 나열
- 시퀀스는 Mutable과 Immutable로 나뉨
- Immutable : str, tuple, bytes
- "str은 값을 바꿀 수 있는데?"라는 의문 ->2021.06.29 - [개발/개발지식] - 구글 파이썬 스타일 가이드 - 2.12 Default Argument Values (Mutable vs Immutable)
- 또한 str은 Immutable 객체로 str[0] = 'd'와 같은 값의 변경이 불가능
- 숫자
- 원시 타입
- C나 Java에서 제공하는 int, float, long 등과 같은 타입형
C 원시 타입 Java 원시 타입, 객체 Python 객체 - 원시 타입을 객체로 변환했을 때
- Pros
- 문자로 변환
- 16진수로 변환
- shifting 같은 비트 조작 - Cons
- 메모리 점유율
- 계산 속도 감소
- Pros
- C나 Java에서 제공하는 int, float, long 등과 같은 타입형
- 객체
- 불변객체와 가변객체 ->2021.06.29 - [개발/개발지식] - 구글 파이썬 스타일 가이드 - 2.12 Default Argument Values (Mutable vs Immutable)
- is와 ==
- is는 id를 비교하는 함수
- ==는 값을 비교하는 연산자
- None은 null로서 값이 정의되지 않으므로 ==로 비교 불가 - Python은 객체로 이루어져있어 속도가 느림
- 원시 타입은 메모리에서 값을 꺼내 한 번 연산하면 끝이지만, Python은 객체에서 값을 꺼내는 것도 오래걸림
- NumPy의 경우 빠른 속도로 유명한데, C로 만든 모듈로 내부적으로 C의 원시 타입으로 처리하기 때문
- 자료구조, 자료형, 추상 자료형
- 자료구조 : 데이터에 효율적으로 접근하고 조작하기 위한 데이터의 조직, 관리, 저장구조
- 자료형 : 컴파일러 또는 인터프리터에게 프로그래머가 데이터를 어떻게 사용하는지 알려주는 일종의 데이터 속성
- 추상 자료형(ADT) : 자료형에 대한 수학적 모델, 해당 유형의 자료에 대한 연산들을 명기한 것
참고자료: (제작중.......)
'책읽기' 카테고리의 다른 글
[파이썬 알고리즘 인터뷰][문자열] 유효한 팰린드롬 (0) | 2021.07.16 |
---|---|
[데이터 분석을 위한 SQL 레시피][1장] 빅데이터 시대에 요구되는 분석력이란? (0) | 2021.07.15 |
[파이썬 알고리즘 인터뷰] 2부 - 파이썬 (~ 5장 - 리스트, 딕셔너리) (0) | 2021.07.12 |
[파이썬 알고리즘 인터뷰] 2부 - 파이썬 (~ 3장 - 파이썬) (0) | 2021.06.29 |
[파이썬 알고리즘 인터뷰] 1부 - 코딩 인터뷰 (0) | 2021.06.23 |