Python Algorithms Interview ch4.BigO

• 개요
• Big $O$
  • 정의
  • 점근적(Asymptotic) 실행 시간
    • 개념
    • 방법
    • 종류
      • O(1): 해시 테이블의 조회/삽입
      • O($\log{n}$): 이진탐색
      • O(n): 정렬되지 않은 리스트의 최소/최대값
      • O($n \times \log{n}$): 병합정렬, Timmsort
      • O($n^{2}$): 버블정렬
      • O($2^{n}$): 피보나치 재귀 계산
      • O(n!): 외판원 문제 brute force 풀이
  • 공간 복잡도
• 상한과 최악
  • 상한
  • 빅오 표기법과 최악
• 분할 상환 분석(Amortized Analysis)
  • Amortized Analysis?
  • 동적 배열
  • 증명
    • n-th 요소 삽입 시 삽입 비용
    • 배열의 확장은 ${log_2{n}}$보다 클 수 없다
    • n 개의 삽입에 대한 총 비용 한계
• 참고

개요

• 점근적 실행 시간(Asymptotic Running Time) 표기 시 가장 널리 쓰이는 수작헉 표기법 중 하나
• 언제 사용?
  • 입력값이 커질 때 시간 복잡도와 공간 복잡도가 어떻게 증가하는지 분류하는 데 사용
  • 알고리즘 효율성 분석에 활용
• 상한과 최악에 대한 개념 혼동 및 분할 상환 분석에 대한 정리

Big $O$

정의

• 입력값이 무한대로 향할 때
• 함수의 상한을 설명하는
• 수학적 표기 방법

점근적(Asymptotic) 실행 시간

개념

• 접근적 실행 시간
  • = 시간 복잡도(Time Complexity)
  • = 계산 복잡도(Computational Complexity): 어떤 알고리즘을 수행하는 데 걸리는 시간을 설명
• 입력값이 무한대를 향할 때, 함수의 실행 시간의 추이 의미
  • 왜 무한대를 향할 때가 의미 있을까?
  • 입력값이 작으면 알고리즘이 복잡해도 컴퓨터 연산이 빨라 금방 끝난다
  • 입력값이 크면 알고리즘의 효율성에 따라 수행 시간이 크게 차이날 수 있다
  • 차이가 없으면 신경쓰지 않고, 차이가 나는 것에 신경을 쓰는 것

방법

• 최고차항만 표기하며 상수항은 무시

4n^2 + 3n + 4 -> 4n^2 -> n^2 -> O(n^2)

종류

O(1): 해시 테이블의 조회/삽입

• 약속된 규칙에 따라 정해진 메모리 위치를 찾아가므로, 실행 시간이 항상 일정
• 대부분 가장 좋지만, 상수가 너무 크면 일정한 시간이 의미 없다

O($\log{n}$): 이진탐색

• 매우 큰 입력값에도 크게 영향을 받지 않는 편이다
• 로그 밑이 2거나 10이거나 차이가 있을까? 없다고 한다
• 간단하게, 밑 역시 고정된 값으로 보고 밑이 2가 됐든 10이 됐든 알고리즘의 시간 복잡도를 비교하는 데는 영향이 없다

O(n): 정렬되지 않은 리스트의 최소/최대값

• 선형 시간 알고리즘(Linear time algorithms)
• 말 그대로 일직선의 배열이 있으면 순차적으로 읽어 나가는 알고리즘
• 따라서 입력값만큼 실행 시간에 영향을 받는다

O($n \times \log{n}$): 병합정렬, Timmsort

• 분할한다는 점에서 O(log n)인 동시에 적어도 모든 수에 대해 한 번 이상은 비교하므로 n이 곱해진다
• 따라서 비교 기반의 정렬 알고리즘은 아무리 좋아도 O(n log n)보다 빠를 수 없다
• 단, 입력값이 최선인 경우 O(n)이 되는 Timsort 알고리즘도 있다

O($n^{2}$): 버블정렬

• n번 반복문을 두 번 돌린다고 보면 이해하기 쉽다. $n^{3}$은 3중 반복문이 된다.
• 같은 자료 구조의 선형 탐색을 여러번 하는 것은 당연히 비효율적이다

O($2^{n}$): 피보나치 재귀 계산

• 메모이제이션 같은 방법을 사용하지 않을 경우 같은 계산이 중첩적으로 이뤄진다

O(n!): 외판원 문제 brute force 풀이

• 최단 경로를 찾는 외판원 문제(TSP, Travelling Salesman Problem)을 brute force 방식으로 풀이하는 경우

공간 복잡도

• 빅오는 공간 복잡도를 표현한느 데에도 널리 쓰인다
• 알고리즘은 보통 시간과 공간이 트레이드 오프(Space-Time Tradeoff)되는 관계
  • 실행 시간 빠름 -> 공간 많이 사용
  • 공간 적게 사용 -> 실행 시간 느림

상한과 최악

상한

• $O$는 실행 시간의 상한을 의미
• $\Theta$는 실행 시간의 평균을 의미
• $\Omega$는 실행 시간의 하한을 의미

빅오 표기법과 최악

• $O$는 실행 시간의 상한을 적당히 정확하게 표현하는 방법일 뿐이다
• 즉, 표기법 != 최선/평균/최악의 케이스
• 최악의 경우가 있을 때, 상한은 아무리 늦게 실행되어도 그 안에는 된다는 것
• 가령 퀵 정렬이 ‘최선의 경우 n^100’라고 해도, 반드시 그 시간 안에 수행되므로 틀린 말은 아니지만, 의미가 없다

분할 상환 분석(Amortized Analysis)

Amortized Analysis?

• Amortization은 경제 용어로 감가/상각 중에서 상각이라고도 하며, 할부 상환이라고도 한다
• 복잡도 계산 시, 알고리즘 전체가 아닌 최악의 경우만 살피는 경우 지나치게 비관적이라는 이유로 등장
• 대표적인 예로 동적 배열(dynamic array)
  • 배열은 보통 시작 주소 값 + 인덱스 위치를 찾아가므로 아이템 삽입 시간은 O(1)이다
  • 하지만 초기 배열에 할당된 메모리 공간이 부족해서 더블링되는 것을 보고 O(n) 시간 복잡도라고 하면 억울할 것이다
  • 그래서 이 더블링과 같은 최악의 경우를 여러 번에 걸쳐 골고루 나눠주는 형태로 시간 복잡도를 계산

동적 배열

• 크기가 N인 배열에서 N+1번째 요소 삽입 시, 배열의 크기를 두 배로 늘리는 것
• 가령 아래와 같이 크기가 4인 배열이 있을 경우, 다섯번째 인덱스에 요소를 추가할 경우 더블링이 이뤄진다

동작: 삽입  삽입    삽입    삽입        삽입 <- 더블링
비용: 1     1       1       1       |   5
값:   10    21      12      63      |   34

단계		예제
1	n 개의 삽입 작업에 대해 n*Θ(1) = n	4
2	기존 요소들을 이동 시키는 사이즈 더블링 작업에 Θ(n)	4
3	총 n + 1 개의 요소 삽입 작업	5
4	((Θ(1) * n) + Θ(n)) / (n + 1) = Θ(1)	(4 + 4) / 5 = 1.6

증명

n-th 요소 삽입 시 삽입 비용

• A가 요소 삽입 후 공간이 남아 있다면 O(1)
• 그렇지 않다면 O(n).
  • A 확장하는 데 소요되는 시간
  • 확장 시간은 최대 cn(c > 0)이라 가정
    • c: 비용
    • n: 요소 개수

배열의 확장은 ${log_2{n}}$보다 클 수 없다

• 처음 사이즈가 2라고 한다면 \(\\2 \to 4 \\\) \(4 \to 8 \\\) \(8 \to 16 \\\) \(\dots \\\) \(2^{i} \to 2^{i+1} \\\)
• n이 입력된 후, 더블링이 되므로 A 배열의 크기는 최대 2n이 된다 \(\\ 2^{i+1} \le 2n \\\) \({\log_2 2^{i+1}} \le {log_2 2n} \\\) \({i} \le {log_2 n} \\\) 따라서 ${\log_2{n}}$보다 큰 배열 확장은 없다

n 개의 삽입에 대한 총 비용 한계

\[\sum\limits_{i=1}^n O(1) + \sum\limits_{i=1}^{\log_2 n} {c}\cdot{2^i} = O(n)\]

• 첫번째 파트(삽입)는 각 삽입에 대한 필수적인 상수 소요 시간
• 두번째 파트(복사)는 앞서 이미 확장에 소요했던 총 비용
• 따라서 첫번째 파트는 다음과 같이 계산되고 \(\\ O(1 + 1 + 1 + 1 + \dots) = O(n) \\\)
• 두번째 파트는 다음과 같이 계산된다 \(\\n = 2 \to {c}\cdot{2^{1}} \\\) \(n = 3 \to {c}\cdot{2^{1}} \\\) \(n = 4 \to {c}\cdot{2^{1}} + {c}\cdot{2^{2}} \\\) \(n = 5 \to {c}\cdot{2^{1}} + {c}\cdot{2^{2}} \\\) \(n = 6 \to {c}\cdot{2^{1}} + {c}\cdot{2^{2}} \\\) \(n = 7 \to {c}\cdot{2^{1}} + {c}\cdot{2^{2}} \\\) \(n = 8 \to {c}\cdot{2^{1}} + {c}\cdot{2^{2}} + {c}\cdot{2^{3}} \\\) \(\dots \\\) \(O(1 + 1\cdot2^{1} + 1\cdot2^{2} + 1\cdot2^{log_2n} - 1)\) \(\\ = O(\frac{1 - 2^{log_2n + 1}}{1 - 2} - 1) \\\) \(= O(2\cdot2^{log_2n})\\\)
• 첫번째 파트와 두번째 파트를 합하면 \(= O(n + 2\cdot2^{log_2n}) \\\) \(= O(n) \\\)

참고

• https://medium.com/@yasufumy/data-structure-dynamic-array-3370cd7088ec
• https://stackoverflow.com/questions/28377546/more-appropriate-to-say-amortized-o1-vs-on-for-insertion-into-unsorted-dynam
• https://compsci.sites.tjhsst.edu/CS2C/U2/bigoh.html
• https://blog.naver.com/manonflame/220900695246
• https://www.cs.utexas.edu/~slaberge/docs/topics/amortized/dynamic_arrays/
• https://www3.cs.stonybrook.edu/~algorith/video-lectures/2007/lecture4.pdf