L01 - Algorithm Analysis

 

국민대학교에서 "쉽게 배우는 알고리즘" 교재를 이용한
 박하명 교수님의 강의 교안을 이용하여 수업 내용을 정리하였습니다

 

Algorithm Analysis

 

알고리즘 : 어떤 문제(Problem)를 해결하기 위한 절차나 방법을 공식화한 형태로 표현한 것

 

=> 여기서 문제란 입력(Input)과 출력(Output)의 관계

 

정렬 문제를 예시로 봤을 때

Input : 정렬되지 않은 숫자들의 목록
Output : 오름차순으로 정렬된 숫자들의 목록

 

한 문제는 다양한 알고리즘으로 해결할 수 있음

 

 

Problem : n을 n번 더한 값은?

 

어떤 알고리즘을 선택할까?

 

 

누가봐도 3번을 채택할텐데

 

가장 효율적이고 쓰기 좋은 알고리즘을 선택해야하고 이것은 곧 효율성과 용이성이 좋다는 의미

 

(알고리즘에서는 효율성을 주로 신경씀)

 

그럼 알고리즘의 효율성은 어떻게 측정할까?

 

 

효율적인 알고리즘이란 한정된 자원으로 문제를 해결하는 것임

 

=> 자원(Resource)에는 시간, 공간 등이 있음

(여기서 공간은 메모리 공간을 의미)

 

 

효율성 측정 방법

 

 

효율성 측정 방법에는 실제로 돌려보고 측정하는 실험적(Empirical) 방법과 기본 연산 수를 세는 이론적(Theoretical) 방법이 있음

 

 

실험적 방법

 

• time() 을 이용해 알고리즘 시작 전, 후 시간의 차를 이용하여 시간을 측정
  
  
• 실행 중간마다 memory_info()를 호출하여 메모리 공간을 측정
  
  
• 직관적이라는 장점이 있음
  
  
• 기기, OS, 언어, 구현방법 등 환경에 따라 가변적이라는 단점이 있음
  
  
• 입력 크기에 따른 성능의 경향성 파악이 어려움 (다양한 입력 크기에 대해 실험을 해야 성능의 변화를 체계적으로 분석 가능)
  
  => 입력 크기별로 전부 실행해봐야 알 수 있음

 

이론적 방법

 

복잡도 분석(Complexity Analysis)

 

• 시간 복잡도 (Time Complexity) : 기본 연산의 수 
  (n개의 입력일 때 기본 연산을 n 만큼 사용하는지 n^2 만큼 사용하는지를 나타냄)
• 공간 복잡도 (Space Complexity) : 메모리 사용량 
  (사용하는 변수의 양이라고 생각하면 됨)
  
  

기본 연산이란?

사칙연산 (+, -, *, /) , 대입연산 (=), 비교연산(<, <=, ..) 등등

 

 

대개, 복잡도는 입력 데이터의 크기 n에 의해 결정됨

• T(n) : 입력 n에 대한 시간 복잡도 함수
• S(n) : 입력 n에 대한 공간 복잡도 함수

 

Best, Worst and Average Cases

 

입력 크기가 같아도 입력에 따라 복잡도가 다를 수 있음!

 

=> 경우를 나눠서 분석하자

 

• Best case : 가장 적은 자원을 사용하는 경우
  
  
• Average case : 평균적으로 자원을 사용하는 경우
  (일반적인 경우의 성능)
  
  
• Worst case : 가장 많은 자원을 사용하는 경우
  (성능 보장에 활용 : 어떤 경우라도 이보다는 좋음)

 

Best case를 고려할 일이 있을까..?

 

입력을 best case에 비슷하게 맞출 경우 best case가 중요할 수 있음!

 

예시

 

n개의 숫자를 담은 배열 nums에서 주어진 값 q를 찾는 알고리즘

 

 

Best case : T(n) = 1

=> q가 nums의 가장 앞에 있는 경우 

 

Worst case : T(n) = n

 

=> q가 nums의 가장 마지막에 있거나, 아예 없는 경우

 

Average case : T(n) = (n+1)/2

 

=> 값이 존재한다고 가정했을 때 모든 가능한 경우의 기댓값

 

 

Average case를 구할 때 각 위치에서 q가 발견될 확률은 1/n 이고 

 

• 첫 번째 위치에서 발견되면 1번 비교
• 두 번째 위치에서 발견되면 2번 비교
• …
• 마지막 위치에서 발견되면 n번 비교

이므로 시그마 1~n 까지 계산하면 n(n+1) / 2 여서 해당 식이 나옴!

 

Asymptotic Analysis

 

Introduction to Asymptotic Analysis

 

알고리즘을 분석하려면 항상 기본 연산 수를 일일이 세야 할까?

 

정확한 연산 수를 세는 것 보다 입력 크기에 따라 연산 수가 변하는 경향을 파악하는 것이 중요함

 

=> 대략적으로 세는 것이 보편적 (점근적 분석법을 사용하자)

 

 

점근적 분석(Asymptotic Analysis)

 

입력 크기가 아주 클 때의 복잡도 분석이다

 

=> 무한대로 근접한다고 생각하면 분석이 간단해짐!

 

(n이 무한대로 근접함에 따라 함수가 변화하는 양상을 살펴보자는 뜻)

 

왜 입력 크기가 클 때를 분석할까?

입력 크기가 작을 땐 어차피 복잡도가 낮음 (전부 빨리 실행됨)

또한 우세항(Dominant Factor) 만 찾으면 되기 때문에 분석이 단순해짐
=> 상수 계수(Constant Coefficient) 도 무시 가능

 

여러 항으로 구성된 T(n)의 복잡도 분석 예시

 

 

 

정말 입력 n이 커짐에 따라 상수 계수를 무시할 수 있을까?

 

Algorithm A : T(n) = 2^n

Algorithm B : T(n) = n^10

 

라고 할 때 

 

n이 커지면 결국 Algorithm B가 빠르다는 것을 알 수 있음

 

Algorithm B 의 T(n)에 상수 1000을 붙여 T(n) = 1000 x n^10 으로 만든다고 하더라도

 

n이 커지면 결국 Algorithm B가 빠르다는 것을 알 수 있음

 

=> 상수는 무시할 수 있다!

 

복잡도 함수의 서열은 어떻게 될까?

 

 

 

이런 느낌이다

 

 

Big-O, Big-Omega, Big-Theta

 

점근적 표기법(Asymptotic Notations)는 우리가 앞서 다뤘던 점근적 분석(우세항만 보고, 상수 계수는 무시하고 ...)을 수학적으로 명확하게 정의하기 위한 표기법이다!

 

• Big-O Notation
  

 

 

=> n이 아주 클 때 c · f(n) 보다 값이 작은 함수의 집합을 의미함

 

=> f(n)이 상한 (upper bound)

 

 

T(n)이 O(f(n)) 에 속하는지 증명하려면?

 

T(n) <= c · f(n) for all n >= n0 를 만족하는 c와 n0을 찾으면 됨!

 

=> T(n)은 입력값이 아무리 증가하더라도 상한인 f(n)과 비슷한 양상으로 증가하는 형태를 띠게 됨

 

T(n) = 4n - 4 ∈ O(n), O(n^2), O(n^3) ... 임

=> 가장 tight한 bound를 찾는 것이 중요함!

성능 평가에 중요한 영향을 미치지 않는 계수, 상수항 굳이 신경 쓰지 X

2n + 1 ∈ O(1/2n)

O(n) = O(2n) = O(n +2)

 

• Big-Omega Notation

 

 

=> n이 아주 클 때 c · f(n) 보다 값이 큰 함수의 집합 

 

=> f(n)이 하한 (lower bound)

 

T(n)이 Ω(f(n)) 에 속하는지 증명하려면?

 

T(n) >= c · f(n) for all n >= n0 를 만족하는 c와 n0을 찾으면 됨!

 

=> T(n)은 입력값이 아무리 증가하더라도 하한인 f(n)과 비슷한 양상으로 증가하는 형태를 띠게 됨

 

 

• Big-Theta Notation

 

 

 

=> 상한과 하한이 모두 f(n)인 함수 집합

 

T(n)이 Θ(f(n))에 속하는지 증명하려면?

 

T(n)이 O(f(n)) 과 Ω(f(n)) 모두에 속하는지 증명하면 됨!

 

 

Simplifying Rules