728x90

알고리즘의 분석 : 시간 복잡도

- 알고리즘의 자원(resource)  사용량을 분석 , cf)자원: 실행시간, 메모리, 저장장치, 통신, 등
- 실행시간의 분석에 대해서 다룸
  • 시간복잡도(time complexity)

- 연산의 실행 횟수를 카운트(실행시간 은 실행환경에 따라 달라짐)
- 연산 실행 횟수는 입력 데이터의 크기에 관한 함수로 표현
- 데이터의 크기가 같더라도 실제 데이터에 따라서 달라짐 
   ex) worst-case analysis vs average-case anaysis :최악의경우 시간복잡도, 평균 시간복잡도 
  • 점근적(Asymptotic) 분석

-  Θ-, Ο-: n→∞일때 수행시간이 증가하는 growth rate로 시간복잡도로 표현

- 상대적으로 간단하고 실행환경에 비의존적이여서 가장 광범위하게 사용

  1. 상수 시간 복잡도 - 시간복잡도 : O(1) 

     ex) n개 데이터 배열 n/2 번째 데이터 반환
  2. 선형 시간 복잡도 - 시간복잡도 : O(n)

    ex) n개 데이터 저장된 배열 sum
  3. 순차 탐색 최악의 경우 - 최악의 경우 시간복잡도 : O(n)

    ex) n개 데이터 저장된 배열 target 있는지 검색

    2차식(Quadratic) : - 최악의 경우 시간복잡도 : O(n^2)

    ex) n개 데이터 저장된 배열 X, n개 데이터 저장된 배열 Y, X[i]=Y[j]의 경우 n(n-1)/2
  • 점근적(Asymptotic) 표기법

-  알고리즘 포함된 연산들의 실행 횟수를 표기하는 하나의 기법, 최고차 항 차수만으로 표시

-  가장 자주 실행되는 연산, 문장의 실행횟수를 고려

  1. Ο-표기 :: upper bound를 표현 

     ex) f(n) = 32n^2 + 17n^2 -32 , f(n) <= cg(n)
  2. Ω-표기 :: lower bound를 표현 : 오메가

    ex)  f(n) = 32n^2 + 17n^2 -32 , f(n) >= cg(n)
  3. Θ-표기 :: upper bound & lower bound를 표현 :세타

    ex) f(n) = 32n^2 + 17n^2 -32 , 0 <= c2g(n) <= f(n) <= c2g(n)
   Big-O 

 O(1)

O(log n) 

O(n) 

O(n log n) 

O(n^2) 

O(n^3) 

O(2^n) 

O(n!) 

 Constant

 Logarithmic

 Linear

 Log Linear

 Quadratic

 Cubic

 Exponential

 Factorial

  • 다항시간(polynomial-time) 알고리즘

다항식일 때 사용. 

'For Real > 알고리즘' 카테고리의 다른 글

Backjoon1000_DrEngineer  (0) 2018.11.23

+ Recent posts