출처
📚 쉽게 배우는 자료구조 with 파이썬
📚 Do it! 자료구조와 함께 배우는 알고리즘 입문 : 파이썬 편
1주차: 기본 알고리즘의 정의, Big-O 표기법, 시간 복잡도, 공간 복잡도
알고리즘과 자료구조
알고리즘
: 어떤 문제를 해결하기 위해 정해놓은 일련의 절차
특히 올바른 알고리즘이란 - '어떠한 경우에도 실행 결과가 똑같이 나오는 것'
👉🏻 순서도 기호
- 데이터: 기억 장치를 지정하지 않은 데이터 그 자체
- 처리: 정보의 값, 형, 위치 정의하는 연산 또는 연산 집합의 실행, 흐름의 방향 결정 등 여러 종류의 처리기능
- 미리 정의한 처리: 서브루틴이나 모듈 등 다른곳에서 이미 정의한 처리
- 판단: 하나의 입구와 하나 이상의 출력을 선택하는 판단기능. 예상되는 처리 결과(예, 아니오 등)는 경로 선상에 표기
- 루프범위: 루프의 시작과 종료를 나타냄. 시작기호 또는 종료기호에 선처리, 후처리 조건을 나타내고 중간에 처리부분을 감싼다.
- 선: 제어의 흐름을 나타냄. 명확한 방향을 표현할 때 화살표 사용
- 단말: 프로그램의 시작과 종료. 외부에서 들어오는 흐름이나 나가는 흐름을 나타냄
자료구조
: 데이터 단위와 데이터 자체 사이의 물리적 또는 논리적 관계. 즉, 데이터가 모여 있는 구조.
자료구조에 대해 공부하면 컴퓨터 안에 있는 많은 데이터를 효율적으로 처리하는 데에 도움이 된다
👉🏻 대입식 in python: 변수에 값을 직접 대입하거나 변경하는 것이 아니라 참조 객체의 식별 변호를 저장하거나 변경함
따라서 C, JAVA 등에서 '='는 연산자로서 사용 가능하지만, Python에서는 연산자로서 사용하지 못함
👉🏻 뮤터블 자료형, 이뮤터블 자료형 in python
- 뮤터블 자료형: 리스트, 딕셔너리, 집합 등이 있으며 값을 변경할 수 있음
- 이뮤터블 자료형: 수, 문자열, 튜플 등이 있으며 값을 변경할 수 없음
👉🏻 등가성, 동일성 in python: python에서 '=='는 등가성, 즉 값이 같음을 나타냄. 반면 'is'는 값과 식별번호까지 같은지를 나타냄
a = [1, 2, 3, 4, 5] b = a c = [1, 2, 3, 4, 5] print(a is b) #True print(a is c) #False
모듈 객체 -> 다음에 더 자세히 공부
얕은 복사: 복사 후 값 변경하면 복사된 원소값까지 변경됨
깊은 복사: 구성원소뿐 아니라 구성원소의 원소까지 복사. 즉 각각 다른 값을 가짐
복잡도
점근적 분석: 어떤 알고리즘에 큰 입력 데이터를 적용할 때, 알고리즘의 제한동작과 성능을 설명하기 위한 방법
- 시간 복잡도: 특정한 크기의 데이터셋에 대해, 어떤 알고리즘을 적용하기 위해 걸리는 시간
- 공간 복잡도: 특정한 크기의 데이터셋에 대해, 어떤 알고리즘을 적용하기 위해 차지하는 메모리의 크기
복잡도의 표현
O - 표기
주로 최악의 경우의 복잡도를 표현한다.
O(n^2)은 최고차항의 차수가 2를 넘지 않는 모든 함수의 집합.
보통 n^2+3n , 5n^2+7n+1 이런 최고차항이 2차인 함수를 말한다.
2차 이하의 함수의 집합이라고 했으니, 3n+1, 5logn+8n 등도 포함될 수 있고, 이 함수들이 O(n^100)에 포함되기도 한다.
그러나 이는 정보 가치가 전혀 없는 표현으로, 이처럼 점근적으로 복잡도를 표현할 때는 정보 손실이 덜한 쪽으로 표현하는 것이 맞다.
Ω - 표기
주로 최상의 경우의 복잡도를 표현한다.
Ω(오메가) 표기는 O 표기와 정반대로, Ω(n^2)라고 썼을 경우, 최고차항의 차수가 2차를 초과하는 모든 함수의 집합이다.
그렇다면 모든 알고리즘을 Ω(1)이라고 둘 수는 있다. 하지만 앞서 설명한 대로, 항상 정보 손실이 덜한 쪽으로 표현해야 한다.
Θ - 표기
주로 평균 경우의 복잡도를 표현한다.
Θ(n^2)는 최고차항의 차수가 정확히 n^2인 함수의 집합을 뜻한다.
집합 표기를 대신하는 '='
어떤 알고리즘의 수행시간은 보통 T(n)으로 표기하는데, 이 알고리즘이 n^2에 비례하는 시간이 든다면 원칙적으로 T(n) ∈ O(n^2) 로 표현해야 한다. 그러나 편리함을 위해 보통 T(n) = O(n^2) 와 같이 표현한다.
시간 복잡도와 공간 복잡도
시간 복잡도
보통 빅오표현법을 사용해 시간복잡도를 표현한다. N은 대입되는 데이터셋의 크기.
Big-O 표기법으로 표현
lst = [1, 2, 3, 4, 5]
sum = 0
for i in lst:
sum += i위와 같은 일차항 식의 경우, 연산 횟수는 N에 비례하다. 즉, 빅오표기법으로 표현한 위 코드의 시간 복잡도는 O(N)이다.
a = 1
b = 3
print(a+b)이 경우, 어떤 값을 불러와도 결과는 상수이므로 연산 횟수는 1회이다. 이와 같은 상수 연산의 복잡도는 O(1)로 표현한다.
| 표기 | 유형 |
|---|---|
| O(1) | 상수 시간 |
| O(logN) | 로그 시간 |
| O(N) | 선형 시간 |
| O(NlogN) | 선형 로그 시간 |
| O(logN^2) | 이차 시간 |
| O(2^N) | 지수 시간 |
파이썬에 있는 time 라이브러리를 이용해 수행시간을 측정해 볼 수 있다. 알고리즘의 성능을 실제로 확인하기 위해 자주 이용하는 습관을 들이는 것이 좋음.
코딩 테스트에서 요구하는 시간은 1-5초이다. 데이터셋의 크기에 따라 시간 복잡도를 고려하여 적합한 코드를 짜야 한다.
관련 참고자료: invrtd-h. 님의 tistory 블로그
공간 복잡도
컴퓨터 메모리 용량이 좋아져서 과거에 비해 공간복잡도에는 그렇게 민감하지 않은 모양이다.
보통은 시간 복잡도와 공간 복잡도는 반비례하다.
프로그램에 필요한 공간을 크게 고정 공간, 가변 공간으로 나눌 수 있는데, 시간 복잡도를 고려한다면 고정 공간을 크게 사용하는 것이 좋다. 반대로 공간 복잡도를 고려한다면 가변공간을 사용하는 것이 효율적이다.
