[자료구조] #1 알고리즘 분석(1)

• 알고리즘

 
알고리즘 : Input(입력)에서 Output(출력)으로 가는 논리적인 절차
 

• 알고리즘 표현 방식 

1. Natural language(자연어) : 일상적인 언어로 표현
2. Pseudo-code(슈도 코드) : 유사 코드(자연어와 프로그래밍 언어를 적절하게 섞는다.)
3. Programming language(C++)

• 알고리즘의 효율성

 
어떤 알고리즘이 가장 효율적일까?
: 빠르면서 가벼운 것이 가장 효율적이다!
 

그렇다면 가장 효율적인 것을 판단해내기 위한 방법은 무엇일까?

 
자원측정법 : Time(시간), Space(공간)

 
Empirical(정량적인 시간) : 실제로 재는 것을 의미한다.
- 장점 : 실질적인 수치를 가지고 비교가 가능하다.
- 단점 : 환경에 따라서 달라지며, 실제로 실험하지 않는 이상 모른다. 
 
Theoretical : 이론적인 측정을 의미한다.
- Time Complexity(시간복잡도) : 이 프로그램이 Basic Operations를 얼마나 수행하는지
- Space Complexity(공간복잡도) : 이 프로그램이 메모리 공간을 얼마나 차지하는지
 
이 시간(공간)복잡도를 수학적으로 분석하기 위해 함수화한다.
T(n) : n이라는 Input 데이터가 주어지면 T(n)이라는 Time Complexity를 계산한다.(S(n)도 마찬가지)
 

• Basic Operations

 
입력의 크기와 상관없이 즉각적으로 실행되는 연산들(사칙연산)

1. Add/Subtraction(덧셈/뺄셈) & Division/Multiplication(나누기/곱셈)
2. Assignment(대입연산자)
3. Comparison(비교연산자)

Basic Operations가 계산되는 방식

 

• Best, Average and Worst cases
 

- Best Case : 제일 적은 알고리즘을 사용하는 입력집합
  (최소 이정도 시간이 나올 것이다.)
- Worst Case : 시간이 제일 오래 걸리는 입력집합
- Average Case : 평균적인 시간을 가진다.(체감성능)

기본적으로 Worst Case를 기준으로 Complexity를 따지게 된다.
따라서 알고리즘을 설계하고자 한다면, Worst Case에 해당하는 Complexity를 줄이는 방향으로 가야 한다.
 

• Asymptotic analysis(점근적 분석)
 

Input Size가 너무 클때 알고리즘의 효율성을 분석하기 위해 점근적 분석법을 쓴다.
(우리가 컴퓨터를 사용하는 이유는 큰 데이터를 처리하기 위함이다.)
 
점근 : 무한대의 상태로 접근하거나 다가가는 것
Asymptotic behavior(점근적 행동) : 데이터나 함수가 특정한 조건에서 점점 더 극단적인 형태로 수렴하거나 변하는 것
 
T(n) = n² + n + 1일때 우리는 n²을 집중적으로 분석해야 하는데 이는 n²이 dominant factor(지배적 요소)이기 때문이다.
(보통의 경우에 다항식에서 차수가 가장 큰 항이 dominant factor가 된다.)