알고리즘 스터디0. 시간복잡도와 빅오(Big O)

Data Science/coding pratice

희스레저 2022. 10. 13. 15:53

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

각 라인을 수행하기 위해 필요한 스텝 수는 상수(constant)라고 가정

T(N) = c1 + c2*(N+1) + c3*N + 1

= (c2+c3)*N + c1 + c2 + 1

= a*N + b

N이 작을 때의 실행시간은 의미가 없다.

N이 무한대로 갈 때 N이 커질수록 덜 중요한 것은 제거(b 제거)

최고차항만이 의미를 갖게되며(여기서는 N) 최고차항의 계수(a) 또한 의미가 없다.(a 제거) → N만 남음

(Big) theta N = N → 점근적 분석에 따른 점근적 표기법

또한 시간복잡도는 함수의 실행시간을 점근적 분석을 통해 점근적 표기법으로 표현한다.

시간복잡도는 하한선과 상한선을 기준으로 설명할 수 있는데,

하한선(lower bound): 아무리 빨라도 상수시간 이상은 걸린다.

상한선(upper bound): 아무리 오래걸려도 N에 비례하는 정도를 넘어서지는 않는다.(정도 이하이다)

이를 점근적 표기법으로 표현하면,

다음과 같다. 보통 Big O notation으로 표기를 많이 한다.

tight bound인 theta N을 통해 상한선과 하한선을 한 번에 알 수 있다.

worst case의 경우 theta N이므로 lower bound와 upper bound 모두 input size N에 비례한 형태를 띠는 것을 알 수 있음

그럼 Average case의 경우에는?

절반 정도에서 내가 찾고자 하는 숫자를 찾았다면?

그럼 어떤 notation을 쓰는가? → Big O notation을 사용한다.

확실한 upper bound만 사용하는 것

위 그림처럼 best일때 Ω 만 사용하고 worst일때 O를 사용하고 avg일때 Θ를 사용하는 것이 아니라,

각각 표기법을 모두 사용할 수 있다.

이 영상에서는 avg일때 오히려 O를 사용한다

정렬이 된 데이터를 저장한 배열을 input으로 받는다. 거기서 target을 찾거나 찾아서 위치를 반환하는 검색(findPosition 함수가 존재)

1) Worst case: 찾는게 없을 때

처음부터 찾아보지 않는다. 이미 정렬이 되어 있으므로 가운데에서 시작하여 찾으려는 값과 비교함.

없는 쪽을 버리고 다시 가운데를 선택하는 과정을 반복함

→ 매번 실행할 때 마다 사이즈가 1/2씩 줄어든다. 몇 번만에 사이즈가 1이 되는가?

1/2으로 나누는 횟수를 K라고 했을 때, 1/2로 K번 나누면 사이즈가 1이 된다.(처음 input size는 N)

이것을 점근적 표기법으로 표현하면,

(Big)theta (logN)이 된다.

Θ(logN)

2) Best case: 한 번에 찾았을 때

Θ(1)

3) Binary search의 시간복잡도는?

lower bound: Ω(1)

upper bound: O(logN)

average는 Big O notation을 사용해서 O(logN)