알고리즘 2주차 월요일 강의

알고리즘

 

 

Growth of Functions

 

 

function이 어떻게 자라는가. Time complexity에 관한 것을 배우는 과이다. 물론 더불어서 Space complexity도 분석하게 된다. 알고리즘이 어떤 문제를 푸는데 걸리는 시간이 있는데 어떤 order(차원)에서 적용이 되는지를, 효율성을 간단하게 보여주는 것이다. Input size N이 무한대로 갔을 때 A, B 알고리즘 어느 것이 더 오래걸리는 지를 범주화하자는 것이다. 물론 어떤 INput이 들어가는지에 따라서 차이가 있겠지만 어떤 급인지를 간단하게 보여주는 테크닉이 되겠다.

 

 

Growth of Function

N = 2일 때 N = 3일 때 이런 자세한 것을 다루지 않고 무한대로 갔을 때 어떻게 되는지에 대한 수학적 수식을 이용해서 어느 급에 있는지를 확인하고자 한다. Focus on what’s importatnt by abstracting away low-order term, 3승과 2승이 있으면 상수와 2승을 모두 제외하고 비교를 하겠다는 것이다. 

 

 

Notation

수학 기호로 5가지가 존재한다. Little Oh, Little Omega는 거의 다루지 않을 것. Theta, BigOh를 주로 다루게 될 것이다. n이 무한대로 갔을 때 cg(n)과 거의 동급에 있다고 하면 Theta가 된다. cg(n)보다 작거나 같으면 BigOh라고 표현을 하고 Upper Bound라고 얘기를 한다. f(n)은 결코 cg(n)을 넘을 수 없는 경우 이렇게 표현을 한다. 반대의 경우 Omega는 f(n) 이 cg(n) 보다 크거나 같은 경우이고 lower bound라고 얘기를 한다.

 

 

O-notation

BigOh의 수학적인 표현을 볼 수 있다. 어떤 특정 지점을 지나면 f(n)은 cg(n) 보다 항상 작은 지점이 존재한다. 그 조건을 만족시키는 n0 지점이 존재하고 constant c 가 존재하면 그곳을 O(g(n)) 이라고 할 수 있다. 

 

 

Lower bound

 

 

Exact bound

두 가지 조건을 모두 만족하는 경우이다. Upper bound와 lower bound를 둘 다 만족을 할 때를 말한다. 상수를 제외하고 나머지 제일 high order의 term을 만들어 놓으면 세타가 된다. 

 

 

Theorem and Rule

두 개의 조건을 만족하면 Theta라고 할 수 있다. 때로는 비교하기 어려울 때가 존재하는데 그럴 때 로피탈의 원리를 사용하면 된다. 분자와 분모를 둘 다 미분을 하게 되는 것이다. 

 

Small o notation

상수 c와 equals sign이 없다는 것이 차이점이다. 세타가 빠진 부분이 equal이 빠진 부분이 된다. n^3은 BigOh n^3은 맞는 말이다. 하지만 n^3은 세타 n^3이므로 small Oh가 될 수 없다.

 

 

Little omega

자기 자신에 대한 세타 값이 제외되어야 하므로 n이 small Oh n이 될 수 없다.

 

 

가장 간단한 형식으로 표현을 해야 한다. Time Complexity를 적으라고 하면 세타인지 빅오인지 표시를 꼭 해야 한다. Low order term은 제거를 해서 간단하게 표현해야 한다.(*****)

 

 

Proposition

세타의 성질을 얘기하고 있다. f와 g가 세타 관계에 있다고 하면 f와 g는 동일한 order에 있다고 할 수 있다.

 

 

 

 

기본적으로 n으로 시간 복잡도를 설명한다,. Upper bound와 lower bound, 세타에 대한 정리. As tight as possible, 가능한한 세타라는 표현을 사용하는 것이 좋고, 그렇기 어렵다면 BigOh를 통해서 표현을 해야 한다. 가능한 한 세타를 붙이고, 앞에 붙는 표현 방식을 반드시 붙여야 한다.

 

Optimality of algorithm

Inherent == 내제하고 있는, 각각의 문제는 원래부터 갖고 있는 복잡성이 있다는 것이다, 그 문제를 풀기 위해서 최소 필요한 량이 존재한다는 것이다. Sorting의 경우 n개의 숫자가 있고 작은 숫자부터 큰 숫자까지 정렬을 하는 것인데 Constant한 타임에 풀 수는 없을 것이다. Sorting이라는 문제를 풀려면 최소한 nlogn의 시간이 필요하다고 얘기를 한다. 어떤 문제를 풀때 최소 필요한 시간을 lower bound of problem이라고 한다, 그 문제를 푸는 것이 알고리즘이다. 문제를 푸는 시간은 최소 nlogn인데 이것보다 더 빨리 풀 수는 없다. 그래서 merge sort를 Optimal 하다고 표현을 할 수 있다. Mergesort 보다 더 빠른 알고리즘은 존재할 수 없다. Merge와 같은 order에 있는 알고리즘은 있을 수 있다. 대표적으로 Heap sort가 된다. 이의 시간 복잡도도 세타 nlogn이다. Problem의 lower bound와 알고리즘의 worst case 시간 복잡도가 매치되었을 떄 Optimal 하다는 것을 생각해보면 좋을 것.가장 빠른 알고리즘이라고 하더라도 Optimal 하다고 할 수 없다. 문제를 풀기 위해 가장 Lower bound가 Optimal 한 것이 되는 것이다.

 

 

Example

어떤 사람이 이 문제를 푸는데 최소한 n^2만큼 걸린다고 했다고 하자. N 이라고 하면 어느 알고리즘도 optimal 하지 않다. 

 

Asymptotic performance

세타 빅오로 표현하는 것은 어떤 알고리즘이 더 빠른 알고리즘인가를 판단하는 좋은 툴이 될 수 있다. 더 느린 알고리즘을 발견하더라도 그것을 무시해서는 안된다. 우리가 사용하는 대부분의 알고리즘의 INput 사이즈가 n0보다 작은 곳에 위치하다면 slower 한 알고리즘이 더 빠른 경우가 될 가능성이 있다. 

 

 

Practical Complexity

데이터 사이즈가 조금만 되어도 시간이 훨씬 올리는 것을 알 수 있다. 어느 순간에 지수함수의 시간 복잡도 알고리즘이 더 오래 걸리는 알고리즘이 되는 것을 확인할 수 있다. 

 

 

Hierarchy of Orders

빅오 f가 빅오 g의 진부분 집합이다라고 하면 빅오 f는 small order다 라고 얘기할 수 있다. 진부분 집합일 때!! Logn 과 스퀘어 n의 관계를 보기 위해서 로피탈의 정리를 사용하면 편리하다. 

 

 

Time complexity comparison

Input size가 많이 커지게 되면 , 컴퓨터가 좋지 않더라도 알고리즘이 더 좋다면 더 빨리 돌아갈 수 있다는 것이다. 빠른 하드웨어를 만드는 것도 중요하지만 빠른 소프트웨어를 만드는 것도 중요하다.

 

 

 

 

Divide and Conquer

다른 알고리즘도 리커런스 알고리즘으로 표현할 수 있다. 

 

 

리커런스

고등학교 때 점화식으로 배웠었다. function을 자기보다 작은 값을 가지고 있는 함수로 정의를 한다. T(n)을 n보다 작은 n/2으로 표현을 한다. 계속 줄어들다가 예를 들어 n 이 1 또는 0, 충분히 작은 값에 있을 때 Constant time이라고 한다.

문제가 작아지게 되면 Constant 로 풀 수 있고  그 값을 합치게 되면 된다. Floor와 ceiling으로 되어있으면 풀기 힘들다. Boundary condition또한 중요하다. 맨 끝으로 갔을 때 

 

 

리커런스 예시

n이 작아져서 표현이 된다.

 

 

푸는 방법

Recursion tree와 Master method를 주로 사용한다. 

 

 

Substitution method

추론 후 수학적 귀납법으로 추론하는 과정이다. 

 

 

예시자료

3가지 단계가 있는데 마지막 부분에서 다루도록 한다. mergesort의 방정식과 동일하다.

 

 

트리 방법

레벨 마다 cost를 더하는 방식으로 진행한다. 각각의 하나가 sub problem들을 다 더하다 보면 전체 cost가 나온다

 

 

트리 예시

트리를 완성시키고, 높이를 구해야 한다. 4의 n승 분의 1로 계속 줄어든다. Leaf 의 n 값을 통해서 height를 구할 수 있다. 

그 다음 항의 개수를 고려해봐야 한다. Leaf level의 전체 개수를 계산해봐야 한다. 

 

빅오와 빅오메가 조건을 만족하므로 세타라고 할 수 있다.

 

 

Iteration Method

 

 

 

 

 

Proof By Induction

N이 옳다고 가정하지 말고 n-1까지 옳다고 가정하는 것이 논리적으로 오류가 없다.