시간복잡도(time complexity)를 알차게 설명합니다! 빅 오(Big O)를 포함해서 점근적 표기법을 다양한 예제와 함께 설명하니까요 들러보세요~ :)

https://youtu.be/tTFoClBZutw

시간 복잡도 : 함수의 실행 시간을 표현하는 것

점근적 분석을 통해 실행 시간을 단순하게 표현하며, 이 때 점근적 표기법으로 표현한다.

  

• 점근적 표기법 : 빅 오메가(lower bound)  / 빅 오(upper bound) / 빅 세타(tight bound)
  • lower bound(하한선) : 함수 실행 시간은 아무리 빨라도 ~ 시간 이상이다.
  • upper bound(상한선) : 함수 실행 시간은 아무리 오래 걸려도 ~ 시간 이하이다.
  • tight bound : 상한선과 하한선이 같을 때
• case 분류 : best(최단 시간 실행) / worst(최장 시간 실행) / average(일반적인 실행)

시간 복잡도의 속도 비교 : O(1) < O(logN) < O(N) < O(NlogN) < O(N²) < O(2ⁿ) < O(N!)

일반적으로 upper bound만 알아도 충분하기 때문에 빅 오 표기법을 많이 사용한다.