시간 복잡도(2)

안녕하세요! 지난 시간에 시간 복잡도에 대해 공부했는데요, 예를 좀 더 살펴보겠습니다!

여러 시간 복잡도 중 많이 쓰는 것들만 정리하려합니다.

 

O(1) : 인풋의 크기가 소요시간에 영향이 없는 것입니다. (반복문이 없으면 대게 O(1) 일 가능성이 큽니다!)

(ex. a = [1, 2, 3] / b = [1, 2, 3, 4, .... 10000] 이라고 할 때, print(a[0]) 과 print(b[0]) 의 시간 복잡도는 동일하게 O(1))

 

O(n) : 반복문이 있으며 인풋의 크기와 비례하여 반복 횟수가 증가하는 Case!

ex. 위와 같이 n개의 리스트의 요소를 처음부터 끝까지 출력하는 경우가 있습니다.

여기서 리스트의 크기를 줄여도 시간 복잡도는 O(n)인 점 주의해주세요! [앞의 상수는 제외한다! 기억하시죠!?]

 

O(n²), O(n³) : 요 두 녀석은 어떻게 될까요? 위에 O(n)에서 힌트를 찾을 수 있습니다!

바로 반복문 안에 반복문이 있는 인셉션같은 구조가 됩니다!

이렇게 위와 같이 반복문이 많아지면 시간 복잡도가 올라가기 때문에 되도록 지양하여야 합니다!

 

O(lgN) : 입력이 증가하면 Log를 따라 반복횟수가 증가하는 시간 복잡도 입니다! (여기서 Log의 밑은 2 입니다@)

아래 예제에서 보듯이 2의 배수로 반복횟수가 나타납니다

(위의 코드는 1024 , 512, 256, 128, 64, 32, 16, 8, 4, 2가 출력되면서 총 10번 반복! 

 아래 코드는 1, 2, 4, 8, 16, 32, 64, 128, 256, 512가 출력되면서 동일하게 10번!)

두개 다 10번인데 이건 입력값 및 조건의 종료 지점이 2의 n제곱이기에 조건문이 n번 반복 됩니다.

O(lgN)은 아직 이해를 완벽하게 하지 못해서 혹시 자세히 아시는 분은 알려주시면 감사드리겠습니다!!!

 

O(NlgN) : O(N)과 O(lgN)이 중첩된 경우입니다!