Time Complexity   시간 복잡도

(2020-06-19)

빅 오 표기법, 빅 세타 표기법

1. 시간 복잡도 (Time Complexity)시간 복잡도의 산정 기준  :  연산 수
     - 소요되는 기본 연산 수에 의거함
        . 주로, 알고리즘이 사용한 기본 연산의 수(명령 수,스텝 수)에 따름
        . 여기서, 주요 기본 연산으로는, 데이터의 비교,덧셈,곱셈,나눗셈 등이 있음

  ㅇ 시간 복잡도의 표현 방식  :  함수적
     - 기본 연산 수가 입력 크기(n : 입력의 개수)와 어떤 함수 관계가 있는가를 분석하고,
        . 여기서, 입력 크기의 例는,
           .. 정렬을 하려는 경우 : 정렬 대상이 되는 원소의 수 
           .. 계승 계산을 하는 경우 : 계승 계산을 하고자 하는 자연수
           .. 최단거리를 구하는 경우 : 노드의 수 및 간선의 수
     - 이를 함수식 처럼 표현 함

  ㅇ 시간 복잡도의 분석 방법  :  점근적
     - 입력 크기가 무한히 증가할 때, 알고리즘이 어떻게 작동하는가에 대해서 따지는,
     - `점근적 분석 방법`을 씀
     
  ㅇ 시간 복잡도의 분석 종류  :  (아래 2.항 참조)
     - (최악의 경우) => big-O (빅 오 표기법) : O() => `최악, 이정도는 보장` (점근적 상한선)
     - (최선의 경우) => big-Omega (빅 오메가 표기법) : Ω() => `최고 수준` (점근적 하한선)
     - (평균의 경우) => big-Theta (빅 세타 표기법) : Θ() => `대략`

  ㅇ 시간 복잡도의 계산 방식
     - 주로, 빅 오 표기법(점근적 상한선)에 준하여,
     - 전체 값 계산에 가장 큰 영향을 주는 항 만 고려함 (즉, 최악의 시나리오)
     - 즉, 근사적인 것을 구함 


2. 시간 복잡도의 분석 종류 

  ㅇ (최악의 경우)
     - big-O (빅 오 표기법) : O() => `기껏해야` 
        . 점근적 상한선
           .. (아무리 나빠도 시간이 이보다 덜 걸림, 최악의 시나리오)
        . 주로, 빅 오 표기법을 사용함

  ㅇ (최선의 경우)
     - big-Omega (빅 오메가 표기법) : Ω()=> `적어도`
        . 점근적 하한선
           .. (최소 이만한 시간이 걸림, 최선의 시나리오)

  ㅇ (평균의 경우)
     - big-Theta (빅 세타 표기법) : Θ() => `대략`
        . 빅 오,빅 오메가 표기법의 절충 (즉,교집합)


3. 시간 복잡도의 주요 계산 例

  ㅇ 가장 큰 차수 만 고려 : 例) n2 + n + 1 => O(n2)
  ㅇ 계수는 1 로 함 : 例) 3n => O(1n) => O(n)
  ㅇ 작은 차이는 무시 : 例) O(n-1) => O(n)
  ㅇ 규모가 큰 것 만 고려 : 例) O(2n + n2) => O(2n)


4. 시간 복잡도의 주요 표기 例)

  ※ ☞ 시간복잡도 표기 예 참조
     - O(c) 또는 O(1)  :  상수 시간 알고리즘 (constant time algorithm)
     - O(log n)  :  로그 시간 알고리즘 (logarithmic time algorithm)
     - O(n)  :  선형 시간(1차 시간) 알고리즘 (linear time algorithm)
     - O(n log n)  :  n 로그 시간 알고리즘 (nlogn time algorithm)
     - O(n2)  :  평방 시간(2차 시간) 알고리즘 (quadratic time algorithm)
     - O(n3)  :  3차 시간 알고리즘
     - O(2n)  :  지수 시간
     - O(n!)  :  계승 시간 (Factorial Time Algorithm)
     - O(∞) :  종료되지 않는 무한 루프

  ※ [참고] 시간복잡도 연산 크기 순서 例)
     - O(1) < O(log n) < O(n) < O(nlogn) < O(n2) < O(n3) < O(2n) < O(n!) < O(∞)


[알고리즘 효율성] 1. 알고리즘 효율성 2. 시간 복잡도 3. 시간 복잡도 표기 예
1146 : Table 'test.ip_nocount' doesn't exist
Warning: mysql_num_rows() expects parameter 1 to be resource, boolean given in C:\htdocs\manage\useful_functions.php on line 205

 
        최근수정     요약목록     참고문헌