[알고리즘 위한 한발짝 두발짝🐾] 빅오(Big-O)표기법

<본 블로그는 코딩문 codingmoon 님의 유튜브를 참고해서 공부하며 작성하였습니다 :-)>

=> 빅오(Big-O)표기법 쉽게 이해하기 [10분 정리]

 

🫧 빅오(Big-O)표기법

: 알고리즘의 성능을 나타내는 표기법

: 시간 / 공간 복잡도 예측시 사용

: N 값의 증가에 다른 처리 시간 또는 공간 계산

: 상수와 계수 제거하여 알고리즘의 복잡도를 단순화

: 인풋의 증가에 따른 연산 처리시간의 증가율

 

🫧 주요 시간복잡도

O(1) - Constant Time

: 인풋의 크기와 상관없이 항상 일정한 시간 소요

O(log n) - Logarithmic

: 로그시간, O(1) 다음으로 빠른 시간 복잡도

O(n) - Linear Time

: 선형 시간, 인풋의 증가 시 같은 비율로 증가

O(N^2) - Quadratic

: 2차 시간, 인풋의 증가 시 n의 제곱 비율로 증가

O(n!) - Factorial

: 팩토리얼 시간 복잡도, 가장 느린 속도 

 

인풋의 증가에 따른 연산 처리 시간의 증가율을 예측하는 척도
상수는 계산에서 제외
최고차항만 신경 쓰자!