Big-O 빅오 표기법

알고리즘의 시간 복잡도를 표기하기 위해 Big-O 표기법을 사용하여 이를 정리하고자 합니다.

 

clock by fahmionline from the Noun Project

#O(1) : constant time

• 입력 데이터의 크기와 관계 없이 일정한 시간

#O(n) : linear time

• 입력 데이터의 크기와 비례해 시간

    ex) for문 1개

#O(n^2) : quadratic time

• 입력 데이터의 크기의 제곱에 비례해 시간

   ex) for문 2개

 

#O(nm) : quadratic time

• O(n^2)에서 m이 n보다 작으면 보다 더 적은 시간이 걸리지만

  m이 n보다 같어나 큰 순간 같거나 많은 시간

#O(n^3) : polymomial or cubic time

• 입력 데이터의 크기의 세제곱에 비례해 시간

     ex) for문 3개

 

#O(2^n) : exponential time

• 함수를 호출할 때 마다 다른 함수를 호출합니다.

  지수적으로 증가하므로 복잡도가 높고 시간이 지수적으로 증가합니다.

 

#O(log n) 

• 처리가 될 때마다 검색할 데이터 양이 뚝뚝 나가 떨어집니다.

  입력 데이터 양이 많아져도 증가하는 정도의 차이가 적어 복잡도가 낮습니다.

 

#O(sqrt(n))

• 입력 데이터의 크기의 루트에 비례해 시간

 

유튜브 엔지니어대한민국 님의 채널에 영상에서 더욱 깔끔한 학습을 할 수 있으며 이를 참고 후 정리하여 제작되었음을 알립니다.

https://www.youtube.com/watch?v=6Iq5iMCVsXA