시간복잡도(빅오표기법)을 왜 알아야할까?

시간복잡도(빅오표기법)을 왜 알아야할까?

개발을 할 때마다 매번 작성한 함수나 메서드의 시간 복잡도를 정확하게 계산하진 않는다. 실제 코드를 적을때는 함수 하나가 여러 파라미터를 받고 내부에서 또 다른 메서드를 호출하고 그 메서드가 또 다른 함수를 부르는 식으로 구조가 복잡해지는 경우가 많다. 이런 상황에서 일일이 모든 시간 복잡도를 구하는건 비효율적이고 현실적이지 않다.

 

그럼 시간복잡도는 신경 안 써도 될까?

시간복잡도에 대한 개념을 잘 알고 있다면 코드를 짤때 동작하는 코드를 넘어서 더 나은 코드를 고민할 수 있는 능력이 생긴다.

예를 들어 지금 작성하고 있는 코드에서 동작이 되긴하지만 더 최적화된 코드가 없을까?라는 질문을 스스로 할 수 있게 된다. 이는 꼭 O(n)과 O(n²)인지 계산하는게 중요한게 아니라 끊임없이 더 나은 시간 효율을 가진 구조나 알고리즘이 없는지 고민하는 자세를 의미한다.

 

그래서 결론은

시간 복잡도는 단순히 수치 계산보다는 성능 향상에 대한 기르기 위 도구로 생각하면 되겠다. 결국 좋은 개발자는 어떻게 하면 더 코드를 빠르게 잘 작동할 수 있을까 끊임없이 고민하는 개발자이기 때문이다. 

---

시간복잡도(Time Complexity)

입력 크기(n)이 커질 때 코드가 얼마나 많은 연산을 수행하는지를 나타내는 척도이다. 일반적으로 빅오(Big-O)표기법을 사용해 표현한다. 이를 통해 성능을 예측할 수 있다.

시간 제한과 입력 크기에 따른 복잡도 예측

C#을 기준으로 1초에 약 1억으로 가정한다. 당연히 언어마다 다소 차이가 존재한다. 그래서 문제마다 명시된 시간제한과 입력크기를 보고 허용 가능한 시간복잡도를 대략적으로 계산할 수 있다.

 

예시

백준 11053 가장 긴 증가하는 부분 수열의 경우

시간제한이 1초 입력은 1000이다. N이 1000일때 O(n²) 가능하므로 LIS를 사용할 수 있다고 유추해볼 수 있다.

 

자료구조와 알고리즘

그래서 시간복잡도를 줄이기위해 자료구조와 알고리즘 지식이 필요하다. 문제 상황마다 최적의 구조가 달리지기 때문에 다양한 자료구조와 알고리즘을 알아야 그때그때 최적의 선택이 가능해진다.