[알고리즘] 시간 복잡도 최대한 쉽게 이해하기

알고리즘을 처음 시작하는 코린이들을 위한 시간복잡도 이야기 🕰️

안녕하세요! 알고리즘에 갓 입문한 코린이 여러분!
오늘은 저와 같은 코린이 분들을 위해 시간복잡도를 조금이라도 쉽게 이해하실 수 있도록 최대한 간단히 이야기해 보려고 합니다. 참고로 저는 “Do it! 알고리즘 코딩테스트 with Java” 책을 기반으로 공부하고 있어요.

 

시간복잡도에서 핵심은 빅-O 표기법이기 때문에, 빅-O 표기법을 중심으로 살펴보겠습니다! 😊

 

시간복잡도, 그게 뭔데?

시간복잡도는 주어진 문제를 해결하기 위해 프로그램이 실행해야 하는 연산의 횟수를 의미해요. 수행 시간은 1억 번의 연산을 1초의 시간으로 간주하여 예측합니다.

 

하지만 처음 들으면 조금 추상적으로 느껴질 수 있어요. 그래서 더 쉽게 풀어볼게요! 😊

 

수행시간, 이렇게 생각해보세요!

예를 들어, 문제에서 시간 제한이 2초라고 한다면, 여러분의 프로그램은 2억 번 이하의 연산으로 문제를 해결해야 합니다.

 

빅-O 표기법이란?

최악일 때(worst case)의 연산 횟수를 나타낸 표기법입니다.

쉽게 말해, 입력 데이터가 엄청 커졌을 때, 가장 오래 걸리는 상황을 기준으로 알고리즘의 성능을 평가하는 도구입니다.

 

🤔 음.. 표로 보니까 더 이해하기 힘든 것 같은 기분은 저만 그런 걸까요?? 이해하기 쉽도록 문제 예시로 알아봅시다.

 

문제 예시로 이해하는 빅-O 표기법

✏️ N=100 일 때, 빅-O 표기법 정리 

N = 100 일때, O(log100) 의 값이 6 ~ 7 사이의 값이라는 것을 볼 수 있습니다.

• O(logn) = 6.64
• O(n) = 100
• O(nlogn) = 100 x 6.64 = 664
• O(n^2) = 10,000
• O(2^n) = 생략
• O(n!) = 생략

 

실전! 문제로 보는 시간 복잡도 (백준 2750번)

 

N = 1,000일 때 시간복잡도 분석 🕒

문제에서 시간제한은 1초이므로 1억 번 이하의 연산 횟수로 문제를 해결해야 합니다. 이를 기준으로 O(N²)와 O(2^n)을 비교해 봅시다.

 

1️⃣  O(N²) 계산  

1,000 x 1,000 = 1,000,000

1,000,000 < 1억 이므로 적합 알고리즘으로 볼 수 있습니다. ⭕

 

2️⃣  O(2^n) 계산

2^1,000의 값은 1억을 넘어서는 수준이 아니라, 실질적으로 계산이 불가능한 값입니다.

따라서 부적합한 알고리즘으로 볼 수 있습니다. ❌

 

결론! 빅-O, 이렇게 이해하면 쉽다! 🎉

빅-O는 복잡한 수학적 표기가 아니라, "얼마나 많은 연산을 해야 할까?"를 나타낸 척도라고 생각하면 됩니다.

이해가 조금 더 쉬워졌길 바라며 파이팅입니다! 😊