[알고리즘] 시간복잡도 구하기

처음 알고리즘 분류 글을 작성하게 되었습니다(두근)

작년(2022) 이맘때쯤 학교에서 학습했던 알고리즘의 시간복잡도에 관한 내용입니다.

 

코딩테스트가 익숙해지면서 효율성을 요구하는 문제들과 맞딱뜨리게 되었는데,

이때 알아야 할 기초 개념이 바로 시간복잡도입니다.

 

 

내가 짠 코드가 입력 대비 얼마큼의 시간이 필요한가를 계산하여

효율성을 판단하고, 비효율적이라면 어떤 부분을 수정할지 생각해 볼 수 있기 때문입니다.

 

 

목차

1. 정의 & 표기법

2. O(1)

2. O(N)

3. O(N²)

4. O(NlogN)

 

---

1. 정의 & 표기법

 

위키 백과에서 인용해 온 컴퓨터과학에서 시간복잡도의 정의

입력을 나타내는 문자열 길이의 함수로서 작동하는 알고리즘을 취해 시간을 정량화하는 것

다음은 시간복잡도의 3가지 표현법입니다.

최악의 실행시간 감소는 효율성을 향상시키므로 빅오 표현법 중심으로 설명하도록 하겠습니다.

시간복잡도	발음	설명	표기법 예시
Big-O	빅오	가장많이 사용되는 표현으로 최악 실행시간을 나타낸다	O(N)
Ω	오메가	최상 실행시간을 나타낸다	Ω(N)
Θ	세타	평균 실행시간을 나타낸다	Θ(N)

 

 

 

 

2. O(1)

a = 1
b = 2
print(a + b)

O(1)은 어떤 입력에도 항상 같은 시간을 갖는 경우를 말한다.

위 코드를 보면 a, b 변수에 대입연산 2회와 print 출력연산 1회, a+b 연산 1회로

총 4회 연산을 수행한다.

 

즉 O(4)로 표현될 수 있는데 상수 값은 제외하고 표현하므로 O(1)이 된다.

 

 

 

 

 

3. O(N)

sum = 0

for i in range(N):
	sum += 1

O(N)은 입력과 비례한 시간을 나타낸다.

sum = 0 대입연산 1회, for문 N회, sum += 1 N회로

 

O(2N +1)로 표현할 수 있는데

앞서 언급했듯이 상수 값은 제외하고 표현하므로

해당 코드는 O(N)의 시간복잡도를 가지고 있다.

 

 

 

sum = 0

for i in range(1, N+1, 2):
	for j in range(i):
    		sum += 1

위 코드를 보면 i가 1부터 i씩 커지며 N까지 반복한다. 즉 N==5라면

1, 2, 4를, 즉 logN번 수행하는 것이다.

해당 수행마다 j가 i회 수행되므로 1+2+4+8+...(N/4)+(N/2)+N=2N

 

i==1 일 때 1회

i==2 일 때 2회

i==4 일 때 4회

i==8 일 때 8회

...

 

모든 경우를 합치면 1+2+4+8+...(N/4)+(N/2)+N=2N (등차수열의 합) 이므로

상수를 제외한 O(N)의 시간복잡도를 갖고있다.

 

 

 

 

4. O(N²)

sum = 0

for i in range(N):
	for j in range(N):
    		sum += 1

2중 for문은 전형적인 O(N²) 시간복잡도 표현이다.

i가 N회, j가 i마다 N회 이므로 N+N+N+....+N=N² 이다.

sum도 j와 동일하게 수행되므로 상수로 처리된다.

 

 

sum = 0

for i in range(N):
	for j in range(i):
    		sum += 1

이와같은 코드는 시간복잡도가 어떻게 될까?

안쪽 for문이 i번만 수행하므로 O(N)보다 작을까?

그렇지 않다.

 

같은 맥락으로 sum 연산을 제외하고 생각해보면

i가 N회, i마다 j가 i회 반복하면 0+1+2+3+...+(N-1)=N*(N-1)/2이다.

 

 

i==0 일 때 0회

i==1 일 때 1회

i==2 일 때 2회

...

 

모든 연산을 계산했을 때 N*(N-1)/2 (등차수열)이라는 결과가 나온다.

 

 

 

 

 

 

5. O(NlogN)

O(logN)은 이진트리의 전형적 시간복잡도이다. 

이진트리의 시간복잡도 계산에 대해 잘 정리해 놓은 이 글을 참고하기 바란다.

 

 

sum = 0

for i in range(1, N+1, 2):
	for j in range(N):
    		sum += 1

위 코드를 보면 i가 1부터 i씩 커지며 N까지 반복한다. 즉 N==5라면

1, 2, 4를, 즉 logN번 수행하는 것이다.

해당 수행마다 j가 N회 수행되므로 N+N+N+...+N=N*logN

 

결국 시간 복잡도는 O(NlogN)이 된다.

 

 

 

 

 

---

REFERENCE

https://medium.com/humanscape-tech/%EC%BD%94%EB%93%9C%EC%9D%98-%EC%8B%9C%EA%B0%84-%EB%B3%B5%EC%9E%A1%EB%8F%84-%EA%B3%84%EC%82%B0%ED%95%98%EA%B8%B0-b67dd8625966

코드의 시간 복잡도 계산하기

https://ko.wikipedia.org/wiki/%EC%8B%9C%EA%B0%84_%EB%B3%B5%EC%9E%A1%EB%8F%84

시간 복잡도 - 위키백과, 우리 모두의 백과사전

https://xodud2972.tistory.com/60

Python 51 - 시간복잡도, 공간복잡도, 빅오표기법 ( 알고리즘 공부 )

https://neos518.tistory.com/145

logN의 시간 복잡도가 나오는 이유

https://mathbang.net/609#gsc.tab=0

등차수열의 합, 등차수열의 합 공식