빅오의 사전적 정의는 입력값이 무한대로 향할 때 함수의 상한을 설명하는 수학적 표기방법이다.
시간복잡도는 어떤 알고리즘을 수행하는 데 걸리는 시간을 설명하는 계산복잡도를 의미한다.
ex) 입력값 n에 대해 4n^2+3n+4번 계산 시 시간복잡도는 O(n^2)이된다.
입력값이 무한대로 향할 때 함수의 상한을 설명하는 수학적 표기방법 -> 빅O
O(1) : 입력값이 아무리 커도 실행 시간은 일정하다
O(logn) : n에 거의 영향을 안 받는다.
O(n) : 입력한 값 만큼 실행시간에 영향을 받는다. 선형시간 알고리즘
O(nlogn) : 모든 값을 한번 이상 비교해야 한다. 비교기반 알고리즘은 O(nlogn)보다 작을 수 없어요
O(n^2) : 비효율적인 시간복잡도이다.
O(2^n) : 피보나치수를 재귀함수로 계산시 시간복잡도이다.
O(n!) : 외판원 문제풀이시 사용한다고 한다.
각각의 시간복잡도의 유형에 따른 자료구조 유형이 있다.
알고리즘은 시간과 공간의 트레이드 오프라고 한다. 즉 시간이 많이 들면 공간이 적게 들고, 시간이 적게들면 공간이 많이 든다.(하지만 예외는 존재한다고 한다)
분할 상환 분석 : 최악의 경우를 여러 번에 걸쳐 골고루 나눠주는 형태로 알고리즘의 시간 복잡도를 계산한다.
가령 아이템 삽입시 가끔 더블링이 발생 할 수 있는 데(더블링이면 O(1)인경우 O(n)이 되는 경우 인 듯) 이때 아이템삽입시 시간 복잡도가 O(n)이라고 하면 지나치게 비관적이고 정확하지도 않다고 한다. 따라서 최악의 경우를 여러번 나눠주어 분할 하는 것이 분할 상황 분석이다.
정리 -> 빅오라는 개념이 존재한다. 빅오는 입력이 무한대일 때 함수의 상한을 설명하는 수학적 표기법이다. 시간복잡도의 유형에는 매칭되는 자료구조가 존재한다. 시간과 공간은 트레이드 오프관계이다. 분할상환분석은 최악의 경우를 나눠주어 알고리즘의 시간복잡도를 계산하는 것이다.
자료형
파이썬의 자료형은 숫자, 시퀀스, 집합, 딕셔너리가 있다.
숫자는 불변객체이다.
가령
a = 123
b = a
a = 456
이라는 코드가 있다고 하자.
첫 줄 a = 123이 실행되면 123이 저장된 곳을 a라는 식별자가 참조하며, 123이 저장된 객체를 a가 참조한다.
두번째 줄 b = a가 실행되면 a가 참조하는 객체를 b라는 식별자가 참조하게 된다.
세번째 줄 a = 456이 실행되면 123이 저장되어 있는 객체를 수정하는 것이 아니라 새로운 객체를 생성하여 456을 저장하고 그 객체를 a라는 식별자가 참조한다.
이 처럼 파이썬에서 숫자 자료형은 수정이 불가능 하므로 새로운 객체를 생성하여 세번째 줄을 실행한다.
시퀀스
시퀀스는 수열이라는 뜻이며 순서가 존재한다는 의미이다.
시퀀스는 변경가능(mutable)과 변경불가능(immutable)로 나눌 수 있다.
대표적인 변경가능한 자료형으로는 list가 있다.
가령
a = [1, 2, 3, 4]
b = a
b[0] = 10
이라는 코드가 있다고 하자.
첫 줄 a = [1, 2, 3, 4]는 list객체를 a라는 식별자가 참조하며 리스트의 각 요소는 int형 객체를 참조한다.
두번째 줄 b = a에서 b라는 식별자는 a가 참조하고 있는 list를 똑같이 참조한다.
세번째 줄에서 식별자b를 통해 list객체의 요소값을 수정한다.
이때 같은 객체를 참조하고 있는 a를 통해 조회시 수정된 것이 반영된 객체가 조회된다.
is, ==
is는 값을 비교하고 ==은 id 즉 주소값을 비교하는 연산자이다.
리스트조회 및 조작시 시간복잡도
리스트의 첫번 째 요소 추출 pop(0) => O(n)으로 Deque를 사용하라한다.
len(a) = O(1)
a[i] = O(1)
a[i:j] = O(k)
elem in a = O(n)
a.count(elem) = O(n)
a.index(elem) = O(n)
a.append(elem) = O(1)
a.pop() = O(1)
a.pop(0) = O(n)(Deque사용하셈)
del a[i] = O(n)
a.sort() = O(nlogn)
min(a), max(a) = O(n)
a.reverse() = O(n)
리스트에서 존재하지 않는 index를 조회할 경우 indexError가 발생한다. 이를 try catch문으로 에러처리가 가능하다.
요소삭제방법에는 2가지가 있는 데
첫번째는 인덱스를 이용하여 삭제하는 방법이다
del a[index]
두번째는 값을 이용하여 삭제하는 방법이다.
a.remove(2) #리스트에서 2라는 값을 가진 요소를 삭제한다.
파이썬의 리스트는 객체에 대한 포인터 목록을 관리하는 형태이다.
이처럼 리스트의 첫번 째 요소는 6가 저장되어 있는 객체의 포인터를 두번째 요소는 3이 저장되어 있는 포인터의 주소를 관리한다.
따라서 c언어에서 처럼 연속된 메모리공간에 저장하는 것이 불가능하며 간단한 인덱스 조회시에도 모든 포인터주소에 찾아가서 타입을 확인해야 한다.
딕셔너리
딕셔너리는 key, value를 저장하는 자료형이다.
순서가 보장되는 것 같지만, 버전에 따라 다르므로 주의해야 한다.
collections.defaultdict, collections.Count등을 사용할 수 있다.
참고: 파이썬알고리즘인터뷰, 박상길
'python' 카테고리의 다른 글
| 알고리즘 문제풀이 : 문자열 조작 (0) | 2022.12.23 |
|---|
