Base Algorithm with Python #1

1     . O표기법

최악, 최선의 성능중 최악의 성능에 해당한다. 최악의 성능을 평가하는 이유는 적어도 일정 정도의 성능은 보장한다는 의미이다. O 표기법은 알고리즘의 성능을 평가하기 위해 처리해야할 데이터의 양에 대한 실행시간을 수학적으로 계산한 방법이다

 

O 표기법에는 다음과 같은 7가지의 방법이 존재한다.

1)    O(1) : 이와 같은 성능을 갖는 알고리즘은 처리해야 할 데이터의 양과는 상관없이 항상 일정한 실행시간을 갖는 알고리즘을 의미한다.

2)    O(log2N) : 이와 같은 성능을 갖는 알고리즘은 처리해야 할 데이터의 양이 증가할수록 실행 시간도 약간씩 증가하는 알고리즘을 의미한다. 실행 시간의 증가폭 자체가 logN의 그래프를 가지므로 급격하게 증가하지는 않는다. 일반적으로 효율이 좋은 검색 알고리즘의 성능이 이에 해당된다.

3)    O(N) : 이와 같은 성능을 갖는 알고리즘은 처리해야할 데이터의 양과 비례하여 실행시간도 증가하는 경우이다(ex : for문)

4)    O(NlogN) 처리해야할 데이터의 양에 비해 정비례보다 약간 더 증가하는 실행시간을 갖게된다. 일반적으로 효율이 좋은 정렬(sort)알고리즘의 성능이 이에 해당된다.

5)    O(N^2) : 이와 같은 알고리즘은 2중 반복문을 의미한다(중첩 for문)
이와 같은 알고리즘은 처리해야할 양이 증가하면 증가할수록 데이터의 제곱만큼의 실행시간이 소요되기 때문에 좋은 알고리즘은 아니다.

6)    O(N^3) : 이와 같은 알고리즘은 3중 반복문을 의미한다. 처리해야할 양이 세제곱만큼 증가한다(최악)

7)    O(2^n) : 이와 같은 알고리즘은 데이터의 증가에 따라 2의 n승만큼 실행 시간이 증가하는 알고리즘이다.(최악)

 해당 표를 좀더 자세히 말하자면 y축이 수행시간이 되고 x축은 데이터 수가 된다.

각각 활용되는곳이 어딘지 살펴보자

O(1) : 해시테이블

O(log n) : 이진탐색

O(n) : 순차탐색

O(nlogn) : 퀵, 합병 정렬

O(n^2) : 버블정렬, 삽입

O(n^3) : 행렬 곱셈

해시테이블(Hash Table)이란 기존의 값을 조금 더 빨리 접근하기 위해서 해시함수를 도입하여 만들어진 자료구조이다. 방식은 다음과 같이 하나의 입력값이 들어오면 해당 해시값을 통해 버킷(저장소라 생각해도됨)의 주소로 접근하는 방식이다.

 주의할점은 해시함수를 구하는 시간이 모든 데이터를 비교하는 데이터를 비교하는 시간보다 느리면 성능이 안좋다. 또한 해시함수의 충돌할 경우, (여기서 충돌이란 입력 데이터는 다르지만 해시값이 동일한 경우를 의미한다.) 값을 구분하기 위한 작업을 요하기 때문에 최악의 상황에 대한 시간복잡도는 O(1)에서 O(n)이 되는것이다. 하지만 요즘은 SHA-512, bcrypt등 충돌을 발견하기 어려운 함수로 이루어져 있어 O(n)으로 되는 시간복잡도까지는 안간다.

 

알고리즘의 성능을 좌우하는 요소는 제어문이다. 어떤 알고리즘의 성능이 좋은지 판단하기 위해서는 알고리즘 안에 있는 제어문의 구성과 개수를 살펴볼 필요가 있다. 그 이유는 제어문이 알고리즘의 분석 대상이 되기 떄문이다.

 

(깃허브에서 1번파일을 보고오자. https://github.com/J-Hoplin/Algorithm-with-Python)

 

2 . 알고리즘 최적화

최적화란 무엇일까? 최적화란 알고리즘을 최적화 한다는 의미와 동일하다. 알고리즘의 성능에서 가장 중요한 것은 시간인데 이 시간이 하루 이틀이 아닌 몇 달이 걸리는 것도 있으므로 직접 측정하는거보다 수학적 모델링을 통해 성능을 증명하는것이다.

최적화는 그렇다면 어떻게 하는 것일까? 최적화는 최악의 성능을 더 좋게 수정하면 되는것이다 예를 들면 시간 복잡도가 O(n^3) 인 알고리즘을 O(n^2) 인 알고리즘으로 바꾸는 등의 방법이 있다.

(깃허브에서 2번파일을 보고오자 https://github.com/J-Hoplin/Algorithm-with-Python)