알고리즘 복잡도 분석

알고리즘의 Asymptoric behavior이라는 것은, N이 증가했을 때 그 알고리즘이 실행되는 데에 얼마나 더 오랜 시간이 필요하게 되느냐? 예를 들어서 N에서 5N으로 입력의 수가 5배 증가했을 때에 복잡도가 10배 증가할 수도 있고, 복잡도가 25배 증가할 수도 있을 것이다. 이런 식으로 입력의 수가 크게 증가했을 경우 복잡도가 어떻게 변하는 지를 판단하는 것이다.

 

Binary search는 세타 of (lg n)의 복잡도를 가진다. 이런 복잡도를 가진 알고리즘이라면, n의 사이즈를 2배 증가시켜도 전체적인 search 횟수는 1 증가할 뿐이다. 예를 들어 binary search에서 검색할 대상의 길이를 2배 증가시키더라도 첫번째 search만 거치면 2배로 늘리기 전의 데이터의 개수가 남으므로 복잡도가 1 증가할 뿐이다.

 

Machine Instructions 

우리가 가진 프로세서들은 한정된 개수의 연산을 할수 있고, 이 정해진 연산들을 Instruction이라고 한다.

이 Instruction set은 프로세서의 종류마다 다르다.

compile하는 과정에서 어떤 프로그램을 compile할 때 특정 프로세서에서 동작할 것이라고 타겟을 정해둔다. 

하나의 instruction은 정해진 시간안에 동작한다. 이것은 CPU의 cycle 개수로 나타난다.

 

보통의 instruction들은 constant time안에 작동된다고 가정한다. 

memory allocation and deallocation들은 더하기 빼기와 같은 간단한 연산에 비하면 100배 느리다. 하지만 이것도 constant time이 걸린다고 가정한다.

constant time의 복잡도는 theta of 1 이라고 한다.

@ = theta라고 가정, @(1) + @(n) + @(1) = @(n+2) = @(n) 이다.

Dominant term만 관심을 가진다. 

오른쪽으로 갈수록 Dominant

Control Statements

일반적으로 loop의 조건을 판단하는 것의 복잡도는 constant라고 가정한다.

if 내부에 있는 operation은 실행될지 안될지 잘 판단하기 어렵다.

최악의 경우를 가정해서 분석할 수도 있고, 평균적으로 판단할 수도 있다.

반복문 안에 반복문이 있을 경우, 두 반복문의 복잡도를 곱해서 전체 복잡도를 판단한다.

 

if else 보다는 switch case문을 쓰는게 좋다. (컴파일 시에 미리 최적화가 되어 있기 때문.)

 

Serial Statements 

random list가 있을 때, 특정 값이 있는 지 보는 경우.

최댓값을 찾는 문제는 전체 list를 다 확인해야하기 때문에 복잡도가 높다. -> 이런 경우 Theta를 쓴다.

반면, 특정 값을 찾는 문제는 최악의 경우 모든 list를 확인해야하지만, 운이 좋아서 초반에 찾으면 일찍 끝난다.

그래서 big-O statement를 쓴다.

 

Functions

반복되는 operation을 함수로 만들어서 사용한다.

함수 호출 시에 복잡도는? 최신 프로세서들은 함수 호출도 constant time이라고 한다.

일반적으로 최소 1의 복잡도이기 때문에 Omega(1)으로 표현.

일반적으로 함수 하나의 복잡도는 함수 T(n)으로 나타낸다.