시간복잡도(time complexity)와 빅 오(Big O) 또는 빅 오메가(Big omega)를 포함한 점근적 표기법

시간복잡도(time complexity) 개념과 점근적 분석(Asymptotic analysis)

이 함수를 실행햇을 때 실행 시간이 어느 정도일지 표현해보고 싶다.
실행 시간(running time)이란 함수/알고리즘 수행에 필요한 스텝(step)수.
각 라인을 수행사기 위핸 필요한 스텝 수는 상수(constant)라고 가정하자.

=> 임의의 함수가 N이 무한대 일 때, 어떤 함수의 형태에 근접해지는 분석

시간복잡도란?
=> 함수의 실행 시간을 표현하는 것. 주로 점근적 분석을 통해 실행 시간을 단순하게 표현하며 이 때 점근적 표기법으로 표현함

점근적 표기법과 case별 분석

함수의 파라미터 데이터에 따라 실행 시간이 조금씩 다르다. (데이터가 앞에 있느냐, 뒤에 있느냐)

이진 탐색(Binary Search)의 시간복잡도 구하기

이거 수치해석 shooting method 아닌가?
매번 실행할 때마다 범위가 절반씩 줄어든다.

1. Worst Case

2. (...중략...) 케이스별 시간 복잡도

간단한 예제들의 시간복잡도 구하기

(1) 예제 1

(2) 예제 2

(3) 예제 3

대표적인 시간복잡도들의 속도 비교

우측으로 갈수록 성능이 안좋다. 느려진다.

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

1. 일반적으로 upper bound(상한선)만 알아도 충분하기 때문에
2. 다른 bound를 계산하기 귀찮아서
3. 괜히 tight bound로 말했다가 태클 받기 싫어서
4. 주위에서 다들 그렇게 쓰니까
5. 실은 점근적 표기법의 개념을 잘 모르고 씀.

재밌는 얘기로 마무리

사람들이 빅오를 많이 쓰는 이유는 키보드에 오메가와 세타가 없기 때문이다. 흠...