[시간복잡도] 개념 정리

알고리즘이란?

• 컴퓨터 프로그램
• 특정 작업 (ex. 정렬)을 해결하는 개별 모듈로 구성된다.
• 문제를 해결하기 위한 절차나 방법, 더 정확한 정의로는 모든 입력값에 대해 튜링머신이 정지하게 하는 명령

표현 방법

• implementation
• 슈도 코드 (pseudo code)
• Natural Language(영어, 한국어)
• 알고리즘 이름, Input, Outpu, 방법이 나오도록 명시

용어 정리

• Correctness : 맞는 답을 찾아가는 과정
  • ex. n개의 도시가 있고 도시간의 거리가 포함되어 있을 때 모든 도시를 방문하고 다시 내 도시로 돌아왔을 때 이동한 거리가 최소가 되는 값을 구해라
    • 맞는 접근법을 찾아보자!
    • 가장 가까운 도시부터 접근해서 돌아오기
    • 모든 방법을 검사해서 최소값을 찾기
    • 이런식으로 맞는 답을 찾아간다.
• Effiency : 얼마나 효율적인가
• 복잡도 분석
  • Time complexity: 시간이 얼마나 걸리는가
  • Memory(space) complexity : 메모리를 얼마나 차지하는가

 

 

 

 

복잡도 측정하기

어떤 문제를 풀 때 사용되는 Step 수가 달라진다.

하나의 instance를 넣었을 때

• worst case running time : 가장 최악의 step에 의해
• best case running time : 가장 최소의 step에 의해
• average case running time : 평균적인 step에 의해 (분석하기가 까탈스럽다.)

간단한 표현

n이 커질수록 차수가 작은 항들은 무시된다.

 

사이즈가 어느정도 커지고 나면

logn, n, nlogn, n^2 , n^3, 2^n 순으로 시간이 많이 걸린다.

 

어떤 일반적인 룰을 가지게 됨을 볼 수 있다.

 

 

 

빅 오 표기법

• 주어진 함수에서 가장 빨리 증가하는 항만을 남긴 채 나머지를 다 버리는 표기법
  • 시간복잡도는 계산하기 힘들다는 문제점이 있음
  • 모호한 필요 명령어의 수, 복잡한 알고리즘에서의 명령 수 계산 등
  • 따라서 가장 깊이 중첩된 반복문의 개수만 고려했던 것처럼 전체 수행 시간에 큰 영향을 미치지 않는 상수 부분은 무시하고 반복문의 반복 수만 고려하게 되는 것
  • 대략적으로 함수의 상한 을 나타낸다.
  ex. $ N^2 + 100N + 1 = O(N^2) $ 라고 표기하는 시간 복잡도가 있을 때N이 엄청나게 커지면 $ N^2 $ 과 100N + 1 사이에는 그다지 큰 차이가 없게 됨
• 이 때 적절한 상수 C를 선택해서 $ N^2 $에 곱해주면 항상 $ N^2 $이 더 크다고 할 수 있음 (C와 N은 마음대로 결정할 수 있음)
• $ N^2 $ 은 100N + 1보다 작지만 이 중에서 가장 빨리 증가하는 항

• 빅 오 표기법의 경우 각 경우의 수행시간을 간단히 나타내는 표기법일 뿐, 특별히 최악의 수행 시간과 관련이 있는 것은 아님
  • 예를 들어 퀵 정렬의 최악의 수행 시간을 분석해 보면 최고차항이 $ N^2 $으로 시간복잡도는 $ O(N^2)$ 이다.
  • 그러나 평균 수행 시간을 계산해보면 최고차항이 NlogN 으로 평균 시간 복잡도는 최악의 경우와 달리 $ O(NlogN) $ 이다.

 

 

 

빅 오 표기법 이외에 다른 표기법도 있다.

• f(n) = Ω(g(n)) : f(n)의 하한이다.
• f(n) = Θ(g(n)) : n이 충분히 크다면 실행시간이 어떤 상수 $k_1$과 $k_2$에 대하여 최소 $n * k_1$ 이며 최대 $n *k_2$ 이 된다는 뜻이다.

순서대로 빅오, 빅세타, 빅오메가

 

 

 

 

참고

https://yurimkoo.github.io/algorithm/2020/05/09/time-complexity-2.html