알고리즘 분석 방법

* 본문은 <핵심 개념과 실전 문제로 마스터하는 필수 알고리즘 with 파이썬>(박선주, 영진닷컴)의 1-2장을 읽고 필요한 부분 일부를 메모한 내용에 패스트캠퍼스 강의 내용을 보충한 글입니다.

 

 

1. O표기법 안에 들어가는 N은 처리해야 할 데이터의 양.

- O(log_2 n): 처리할 데이터 양 증가할수록 실행 시간도 약간씩 증가. 그러나 증가폭이 완만하단 것 알지? 일반적으로 효율이 좋은 검색 알고리즘의 성능이 이에 해당.

- O(N): 데이터 양&실행시간 비례

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

- O(N^2): 2의 n승까지 있는데 이하 생략.

 

⭐️여기서! 반복문이 1개면 O(n), 2개면 O(n^2),... 등인 걸 알고있을텐데,

variable = 1
     for num in range(3):
         for index in range(n):
              print(index)

이런건 어떻게 될까?!----> 맨 첫줄이 1, 그 아래줄부터는 range(3)이라는 반복문 겉부분이 n번 실행(반대로 생각해도 됨)되기 때문에 3n 따라서 실제론 O(3n+1)--->O(n)이 된다. 만약 계수가 3보다 훨씬 압도적으로 엄청나게 큰 수더라도 무시할 수 있는 근거는? n이 무한이면 그 상수의 크기도 별 의미가 없을 정도가 되기 때문.

 

 

2. 알고리즘의 성능을 좌우하는 요소는 주로 제어문(반복문). 그 외 연산자를 이용한 단순 연산은 별로.

- 반복문은 최대 반복 횟수로 계산한다.(맨 아래 첨부할 링크에서 나온 sample3 문제에 적용 가능)

- if/else문은 성능 영향 없.

- 재귀 호출은 풀어서 계산한다. 꼬리 재귀가 아닌 보통 재귀 함수로 짠 팩토리얼 문제의 경우, 결국엔 1부터 N까지의 곱셈 연산을 하게 된다. 재귀 호출을 N번 반복하게 되면서 O(N^N)이 된다고 하는데...

 

 

3. 알고리즘 최적화

현실적으로 성능을 비교하려는 모든 알고리즘을 구현해서 직접 실행시켜 보는 것도 어려울 뿐더러, 각각의 알고리즘이 실행되는 시간을 계속 체크하는 것도 힘들다. 결국 깩괁거으로 어던 알고리즘이 다른 알고리즘에 비해 성능이 뛰어나다는 것을 증명하기 위한 가장 빠르고 정확한 방법은 수학적 모델링이다.

최적화를 하는 방법은 최악의 성능을 더 좋도록 수정하는 것이다. 이러면 전체적인 성능 향상이 있을 수 있다.

 

아래 알고리즘은 책에서는 부분 수열의 합을 구하는 알고리즘이라고 했는데, ... 테스트 케이스가 없어 이 알고리즘만으로 그것의 정확한 의도가 반영되었는지는 잘 모르겠지만, O(N^3)에 해당하는 알고리즘을 O(N^2)로 최적화한 예라고 할 수 있다.

 

def before(n):
    for i in range(n):
        for j in range(n):
            sum = 0
            for k in range(i,j+1):
                sum += data[k]
            if sum > max:
                max = sum
    
    return max


def after(n):
    for i in range(n):
        sum = 0
        for j in range(i,n+1):
            sum += data[j]
            if sum > max:
                max = sum
    
    return max

if 문을 통해 max와 sum의 크기를 비교하는 문장이 어느 블록에 있는지, for 루프의 범위가 어디까지인지가 핵심이다.

 

강의 들으면서 또 하나! 앞으로 단순한 숫자합 구하는 문제는 내장 함수 중 sum 있으면 이걸 사용하고, 없으면 수열합 공식 사용해도 ㅇㅋ

 

 

기타 다른 내용은 아래 링크에 매우 잘 나와있다. 아래 링크는 검색을 통해 찾은 블로그 포스트.

https://whitepaek.tistory.com/21