내가 짠 함수/알고리즘의 성능을 파악하기 위해서 주로 사용되는 개념

실행 시간(runnning time): 함수/알고리즘 수행에 필요한 스텝(step) 수

각 라인을 수행하기 위해 필요한 스텝 수는 상수라고 가정하자
N이 작을땐 실행 시간이 의미 없다.
N -> ∞ 일 때 실행 시간이 궁금하다.

N -> ∞ 일 때

• N이 커질수록 덜 중요한 것은 제거
• 최고차항만 의미 있다
• 최고차항의 계수는 의미 없다

점근적 분석(Asymptotic analysis)
임의의 함수가 N -> ∞ 일 때 어떤 함수 형태에 근접해지는지 분석

시간 복잡도

• 함수의 실행 시간을 표현하는 것
  -주로 점근적 분석을 통해 실행 시간을 단순하게 표현
  -이때 점근적 표기법으로 표현함

점근적 표기법

Ω (오메가)

하한선(lower bound)
함수 실행 시간은 아무리 빨라도 ~ 이상입니다

O (오)

상한선(upper bound)
함수 실행 시간은 아무리 느려도 ~ 에 비례하는 정도 이하입니다

Θ (세타)

하한선 & 상한선 (tight bound)

실행 시간 case 분류

best(최단) / worst(최장) / average(일반적)

시간 복잡도 시간 비교

O(1) < O(logN) < O(N) < O(N*logN) < O(N²) < O(2^N) < O(N!)

왜 빅오 표기법을 많이 쓸까?

1) 일반적으로 upper bound (최악의 경우)만 알아도 충분하기 때문에
2) 다른 bound를 계산하기 귀찮아서
3) 괜히 tight bound로 말했다가 태클 받기 실어서
4) 주위에서 다들 그렇게 쓰니까
5) 점근적 표기법의 개념을 잘 모르니까
6) 키보드에 Ω 와 Θ 가 없기 때문에