[컴공] 시간복잡도 Big-O 표기법

2022 Jun 07 See all posts


[컴공] 시간복잡도 Big-O 표기법

오늘은 다시 한번 공부해볼겸... 쓸게 없으니 자료 구조의 기초중의 기초에 대하여 다루어보겠다.

시간복잡도

시간 복잡도라는게 존재하는 이유는 간단하다.. 프로그램의 효율성을 평가할때 일반적으로 7초 걸리니 빠르네! 효율적이다!
이러면 그 7초걸리던 프로그램이 콩순이 컴퓨터에선 500시간 걸려 실행될수도 있기 때문인것이다..
따라서 객관적인 프로그램의 효율성을 표기하기 위해 이런 개념이 존재한다고 할수 있다..

Big-O


[그림1]

Big-O 표기법 이란, 알고리즘의 점근적 상한을 나타내는 표기법이다.. 뭔 말이냐면 작성한 알고리즘이 최악의 상황으로 작동할때 [그림1]과 같이 증가 함수와 같은 방식으로 줫같이 작동함을 나타내는 것이다.. 또한 Big-O 표기법의 수학적정의는

n ≥ n0, f(n) ≤ cg(n), if exist c and n0 then f(n) = O(g(n))

인것이다..

성능 비교

위의 [그림1]에서 볼수 있듯이 O(1) < O(logn) < O(n) < O(nlogn) < O(n2) < O(2n) 즉 오른쪽으로 갈수록 효율성이 떨어진다..

Big-O 표기법 예제

  1. O(1) : 스택에서 Push, Pop
  2. O(log n) : 이진트리
  3. O(n) : for 문
  4. O(n log n) : 퀵 정렬(quick sort), 병합정렬(merge sort), 힙 정렬(heap Sort)
  5. O(n^2): 이중 for 문, 삽입정렬(insertion sort), 거품정렬(bubble sort), 선택정렬(selection sort)
  6. O(2^n) : 피보나치 수열

또한

이외에도 Big-Ω, Big-θ등이 더 있으나.. 사실 쓸일이 별로 없다.. 뭔가 나중에 쓸 소재가 떨어졌을때 그때 다시 소개하도록 하겠다.. 사실 Big-O만으로는 이산수학을 제외하고 설명할만한 부분은 이게 다인것이다.. Big-O를 가지고 더 광범위하게 설명하려면 알고리즘에 대해 알아야하기에 이글은 여기까지로 마치고 다음에 알고리즘들을 소개하며 Big-O이 어떻게 활용되는지 설명하겠다

감사하빈다.
gbana.its.me@gmail.com
github: jasnotz