알고리즘의 복잡도 (Complexity of Algorithm)

해당 블로그의 내용은 학교에서 배운 내용을 개인적으로 정리한 내용이므로, 잘못된 부분이 있을 수도 있습니다. 

시간복잡도 분석

입력 크기에 따라 단위연산이 몇 번 수행되는지 결정되는 절차

• 표현 척도
  • 단위 연산
    • 비교
    • 할당
  • 입력 크기
    • 배열의 크기, 리스트의 길이 등

분석 방법의 종류

모든 경우 분석

입력 크기에만 종속

입력 값과는 무관하게 분석 결과가 항상 일정

최악의 경우 분석

입력크기와 입력값 모두에 종속

단위연산이 수행되는 횟수가 최대치인 경우 선택

평균의 경우 분석

모든 입력에 대해서 단위연산이 수행되는 평균

최선의 경우 분석

단위연산이 수행되는 횟수가 최소치인 경우 선택

 

어떤 분석이 가장 정확한가?

정답은 없다. (그때그때 다르다)

실제로는 그래도 최악의 경우 분석을 많이 사용한다. 

 

부정확한 알고리즘이란?

어떤 입력에 대해서 멈추지 않거나,

또는 틀린 답을 출력하면서 멈추는 알고리즘

 

빅O 표기법

정의: 점근적 상한

g(n) ∈ O(n)

g(n)은 어떤 함수 n보다 궁극적으로 좋다(기울기가 낮다)

 

Ω(오메가) 표기법

 정의: 점근적 하한

g(n) ∈ Ω(n)

g(n)은 어떤 함수 n보다 궁극적으로 나쁘다(기울기가 높다)

(g(n)함수는 아무리 빨라도 어떤 함수n보다 더 빠를 수는 없다)

 

Θ(세타) 표기법

 정의: 점근적 상한과 하한의 교집합

 

스몰o 표기법

정의: 작은o

빅O는 실수 c>0 중에서 하나만 성립해도 되지만,

스몰o는 모든 실수 c>0에 대해서 성립해야 한다

따라서 g(n) ∈ O(n) 일 경우에 g(n)이 어떤 함수 n보다 훨씬 좋다 라는 의미

 

복잡도 표시 기법과 분석기법과는 상관이 없다!!!

빅O가 최악 분석이고, 오메가 분석이 최선 분석이란 말이 아니다!!

 

도사 정리 (The Master Theorem)

재귀 관계씩으로 표현한 알고리즘의 동작 시간을 점근적으로 계산하여 간단하게 계산하는 방법으로, 재귀 알고리즘의 시간 복잡도를 결정해주는 블랙박스 툴이다.

재귀 알고리즘의 점화식(recurrence)으로부터 시간 복잡도를 결정하며, 표준 점화식으로만 가능하다.

f(n)이 점근적으로 양이라는 말은 충분히 큰 n에 대해 f(n)이 양이라는 의미이다.