Time Complexity   시간 복잡도

1. 시간 복잡도 (Time Complexity)

  ㅇ 알고리즘을 실행하는데 필요한 시간 척도

  ㅇ 시간 복잡도는, 알고리즘 효율성을 판단하는 중요 척도 (시간 복잡도, 공간 복잡도) 중 하나임
     - 입력 값의 개수에 따른 알고리즘 수행 예측 시간을 바탕으로,
     - 알고리즘의 상대적인 효율성을 평가하는 실행 시간 분석법


2. 시간 복잡도의 특징

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

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

  ㅇ 시간 복잡도의 분석 방법  :  점근적 (Asymptotic)
     - 입력 크기가 무한히 증가할 때, 알고리즘이 어떻게 작동하는가에 대해서 따질 때,
     - `점근적 분석 방법`을 씀
        . 상계/상한(최악,빅 오), 하계/하한(최선,빅 오메가), 평균(빅 세타)
     * 이들 모두를 `점근적 표기법` 이라고 총칭하기도 함 
     
  ㅇ 시간 복잡도의 분석 종류  :  (아래 3.항 참조)
     - (최악의 경우)  =>  big-O (빅 오 표기법)  :  O() => `최악, 이정도는 보장` (점근적 상한선)
        . (aymptotic upper bound)
     - (최선의 경우)  =>  big-Omega (빅 오메가 표기법)  :  Ω() => `최고 수준` (점근적 하한선)
        . (aymptotic lower bound)
     - (평균의 경우)  =>  big-Theta (빅 세타 표기법)  :  Θ() => `대략` (점근적 치밀 경계)
        . (aymptotic tight bound)

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


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

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

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

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


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

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


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

  ※ 시간 복잡도가, 입력 크기의 함수적 관계식으로 표현되면서, 
     - 이때 함수의 증가율을 특징지울 수 있는 여러 부류들이 아래와 같음

  ※ ☞ 시간복잡도 표기 예 참조
     - 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(n logn) < O(n2) < O(n3) < O(2n) < O(n!) < O(∞)