[시간 복잡도] 알고리즘 복잡도 표현 방법

복잡도가 필요한 이유

하나의 문제를 푸는 다양한 방법이 있는데, 어떤 방법이 더 효율적인지 확인하기 위해 필요하다. 

 

 

알고리즘 복잡도 계산 항목

• 시간 복잡도 : 알고리즘 실행 속도
• 공간 복잡도 : 알고리즘이 사용하는 메모리 공간 사이즈
• 공간 복잡도는 요즘 거의 사용하지 않는다. 

 

 

Big O 표기법

• 최악의 실행 시간을 표기.
• 가장 많이 사용하는 표기 방법이다.
• 최악의 상황이여도 이 정도 성능은 보장한다는 의미이다. 
• 제일 큰 차원수만 표기한다. 

# O(1) : 무조건 상수만큼 실행
if n > 10:
           print(n)
      
# O(n)
variable = 1
for num in range(3):
  for index in range(n):
       print(index)
       
# O( 𝑛2 ) : 300𝑛2 + 1도 결국 𝑛2
variable = 1
for i in range(300):
  for num in range(n):
      for index in range(n):
           print(index)