4장_빅오,자료형 요약정리

빅오란?

입력값이 무한대로 향할 때 함수의 상한을 설명하는 수학적 표기방법 , 점근적 실행 시간을 표기할 때 널리 쓰이는 방법이다. 

시간 복잡도와 공간 복잡도를 표현하는데 쓰인다. 

알고리즘은 보통 "시간과 공간이 trade-off 관계"이다. 

 

점근적 실행시간 = 시간 복잡도 

시간 복잡도: 어떤 알고리즘을 수행하는데 걸리는 시간을 설명하는 계산 복잡도 

 

O(1) : 입력값이 아무리 커도 실행시간은 일정하다. 최고의 알고리즘 but 상수값이 너무 클 경우 의미가 없으므로 신중하게 써야 한다. 

Ex) 해시 테이블의 조회 및 삽입 (11장)

 

O(log n): 입력값만큼 실행시간이 영향을 받지만 , 웬만한 n의 크기에 대해서 매우 견고하다. 

Ex) 이진검색(18장)

 

O(n): 알고리즘에 수행하는 데 걸리는 시간이 입력값에 비례한다 = '선형 시간 알고리즘'

대표적으로 정렬되지 않은 리스트에서 최댓값, 최솟값을 찾는 경우이며 모든 입력값을 적어도 한번 살펴봐야 한다. 

 

O(n log n): 효율 좋은 알고리즘이 여기에 해당, 입력값이 최선인 경우 , 비교를 건너뛰어 O(n)이 될 수 있으며

팀 소트(TImsort)가 이런 로직을 갖는다. 

Ex) 병합 정렬

 

O(n^2): 비효율적 정렬 알고리즘이 해당한다. 

Ex) 버블 정렬(17장)

 

O(2^n): 피보나치수(23장)을 재귀로 계산하는 알고리즘이 해당한다.

 

O(n!): 외판원 문제 (각 도시를 방문하고 돌아오는 가장 짧은 경로 찾기)가 해당한다. 

 

빅오 표기법은 주어진 (최선/최악/평균) 경우의 수행 시간의 "상한"을 나타낸다. 

가장 빨리 실행될 때 (하한) , 가장 늦게 실행될 때 (상한)을 뜻하며 

가장 늦게 실행될 때 빅오(O), 가장 빨리 실행될 때 빅오메가, 평균적으로는 빅세타로 지칭한다. 

 

set : 중복된 값을 갖지 않는 집합 자료형 , 입력 순서가 유지되지 않는다. (집합은 딕셔너리와 다르게 키값은 없고 값만 선언한다. )

a={1,2,3}

 

파이썬은 모든 것이 객체이다. 객체는 느린 속도와 더 많은 메모리를 차지하지만 , 다양한 기능을 제공한다. 

 

비교 연산자 'is'와 '=='

 

is :  id() 값을 비교하는 함수 

== : 값을 비교하는 함수