패스트 캠퍼스 챌린지 9일차 - 자료구조 알고리즘 복잡도 표현 방법#2

목차

1. Big-O 표기법

1. Big-O 표기법

• 빅 오 표기법, Big-O 표기법 이라고도 부름
• O(입력)
  • 입력 n 에 따라 결정되는 시간 복잡도 함수
  • O(1), O(logn), O(n), O(nlogn), O(n2), O(2n), O(n!)등으로 표기함
  • 입력 n 의 크기에 따라 기하급수적으로 시간 복잡도가 늘어날 수 있음
    • O(1) < O(logn) < O(n) < O(nlogn) < O(n2) < O(2n) < O(n!)
      • 참고: log n 의 베이스는 2 - log2n
• 단순하게 입력 n에 따라, 몇번 실행이 되는지를 계산하면 됩니다.
• 표현식에 가장 큰 영향을 미치는 n 의 단위로 표기합니다.

 

 

O(n)

def sum_all(n):
	total=0
    for num in range(1,n+1):
    	total+=num
    return total

O(1)

def sum_all(n):
	return int(n*(n+1)/2)

https://bit.ly/37BpXiC