[코드트리] 시간복잡도의 정의

SW중심대학 사업단에서 CodeTree와 함께 실시한 코딩테스트 대비 캠프에 참여하여 공부한 내용을 정리하였습니다.

 

 

프로그램의 효율성을 확인하려면? 먼저 연산이 몇 번 진행되었는지 계산하는 방법이 있습니다.

그러나 연산 횟수를 세는 것은 많은 시간이 걸리고, 코드가 복잡해진다면 매우 어려워집니다.

 

그래서 연산의 횟수를 점근적 표기법을 통해 추상적으로 표현한 것이 바로 시간복잡도 입니다.

 

set a = 5
if a != 10
  print('hello')

 

print 같은 메서드를 O(1)이라고 가정한다면, 대입도 O(1)이고 print도 O(1)이니 if a != 10 만 정확하게 알면 될 것 입니다.

그러나 결국 단순히 두 값을 비교하는 연산을 수행하기 때문에, 결과적으로 조건문도 O(1)의 시간복잡도를 보여주게 됩니다.

따라서 위 코드의 시간복잡도는 O(1)이라고 할 수 있을 것 입니다.

 

보통 for loop을 1억번 도는 데 걸리는 시간이 1초 정도 됩니다.

따라서 이를 이용한다면 제한시간이 1초인 경우,

내가 쓴 코드가 N의 범위에 따라 제한 시간을 충족시키는 알고리즘인지 빠르게 파악할 수 있습니다.

 

세 구분 기호에 대해 배웠는데, 실제로 우리는 O만 사용합니다. 왜 그럴까요?

 

점근 표기법에는 O, Ω, θ 이라는 세가지 표기법이 있습니다. 만약 시간복잡도 측정 과정에서 θ 을 사용한다면 매우 정확하겠지만, 현실적으로 특정 코드의 시간복잡도를 완벽하게 알기 힘든 경우도 있으므로, 사용을 피하는 편입니다. 또한, Ω 을 사용하게 된다면 오래 걸리는 코드의 시간복잡도를 너무 낮게 표현할 수 있는 위험이 있으므로, 사용하지 않습니다.

 

출처 코드트리