1. Algorithms : Efficiency, Analysis, And Order

1.1 Problem Description

-Problem

: May contain variables that are assigned specific values in the statement of the problem description

-Prarmeters 

: 방금 말한 변수를 parameter라고 한다. 예를 들어 search를 하려면 S, n , x의 3개의 parameter가 필요

-Instance 

: parameters 가 specified되면 우리는 Instance라고 부른다. 예를 들어 S = [1,2], n = 6, x = 8 

1.2 Algorithm Description

-Natural languages

-programming languages

-Pseudo-code

: java,c랑 비슷하지만 같지는 않음 코드를 간단하게 나타낸다고 생각하면된다. 

이제 부터 작성하는 모든 코드는 Pseudo-code이다.

ex) low <= x <= high이렇게 써도 되고 x와 y의 값을 바꿀때는 exchange x and y라고 하면 된다.

1.3 Sequential Search

쉽게 말해서 첫번째 부터 일일이 같나 계산하는 알고리즘이다.

Worst Case n번 계산하기 때문에 별로 좋은 Search 알고리즘이 아니다.

1.4 Binary Search

쉽게 말해서 반을 쪼개고 정렬이 되있으니 중앙값이 더 작으면 오른쪽 크면 왼쪽으로 가는 것을 반복한다.

S는 미리 Sort가 되있어야만 가능하다.

Worst Case Log(n) + 1이 나오기 때문에 꽤 좋다고 할 수 있다.

두 Search 알고리즘을 비교해 보자

1.5 Fibonacci Sequence

1st Version (Recursive)

그냥 원하는 숫자를 더하기 위해 중복된 것도 다 계산하는 것이다 매우 비효율적이다

Worst Case와 Best Case 모두 2의 2분의 n승이다 

시간이 너무 오래걸리는데 재귀식말고 다른 방법을 알아보자

위 그림에서 보면 fib(3)을 두번이나 구하는 모습이다. 매우 비효율적

*Counting the number of calls needed in fib(n)

Theroem 1.1 T(n) > 2 **n/2

2nd Version (Iterative)

Iterative 버전이 Recursive 버전 보다 더 빠르다는 것을 알수있다. 왜그럴까? 어떻게 해서 빨라졌을까?

--> Iterative버젼은 배열에 f(1)부터 차근차근 저장을 한다. 그래서 중복된 값을 계산하지 않아서 빨라짐

Time Complexity : T(n) = n + 1

두 알고리즘을 비교해 보자

1.6 Analysis of Algorithms

Every-case analysis

Worst-case analysis 

Average-case analysis

Best-case analysis

결론

Analysis of Correctness

알고리즘의 효율을 따지기 이전에 우선 알고리즘이 맞아야한다!!