시간복잡도

알고리즘을 위해 필요한 연산 횟수
파이썬 프로그램은 2000만 번~1억 번의 연산을 1초의 수행시간으로 예측

외워! 1초 = 2000만 번!!

시간복잡도 유형

Big-Omega(Ω(n))

최선(best case)일 때의 연산 횟수를 나타낸 표기법

Big-Theta(θ(n))

보통(average case)일 때의 연산 횟수를 나타낸 표기법

Big-O(O(n))

최악(worst case)일 때의 연산 횟수를 나타낸 표기법
👉🏻 우리는 얘만 생각하면 돼!!

Big-O 시간복잡도 순서

O(1) < O(log n) < O(n) < O(nlog n) < O(n^2) < O(n^3) < O2^n) < O(n!)
상수 함수 < 로그 함수 < 선형 함수 < 다항 함수 < 지수 함수 < 재귀 함수

Big-O 표기법별 대표 알고리즘

• O(1): Operation push and pop on Stack
• O(log n): Binary Tree
• O(n): for loop
• O(nlog n): Quick Sort, Merge Sort, Heap Sort
• O(n^2): Double for loop, Insert Sort, Bubble Sort, Selection Sort
• O(2^n): Fibonacci Sequence

알고리즘 설계

제한 시간이 1초일 때,

• n ≤ 500 👉🏻 O(n^3)
• n ≤ 2,000 👉🏻 O(n^2)
• n ≤ 100,000 👉🏻 O(n logn)
• n ≤ 10,000,000 👉🏻 O(logn)

백준에서 올바른 로직으로 풀었으나 python3로는 시간초과가 날때가 있다
그럴때에는 pypy3로 제출해보자!

공간복잡도

알고리즘을 위해 필요한 메모리의 양

int a[1000] 👉🏻 4KB
int a[1000000] 👉🏻 4MB
int a[2000][2000] 👉🏻 16MB

알고리즘 설계

알고리즘 문제에서 보통 메모리 사용량을 128~512MB 정도로 제한
👉🏻 일반적인 경우 데이터의 개수가 1000만 단위가 넘어가지 않도록 하자!

Reference

🔗 https://xodud2972.tistory.com/60
🔗 https://bangu4.tistory.com/202