Python 알고리즘_계산복잡도

계산 복잡도 : 어떤 알고리즘이 문제를 풀기 위해 해야 하는 계산이 얼마나 복잡한지 나타낸 정도

 

  계산 복잡도를 표현하는 방법에는 여러 가지가 있는데, 그 중 대문자 O 표기법을 가장 많이 사용한다(대문자 O표기법은 '빅 오'표기법이라고도 부른다).

  대문자 O 표기법의 정확한 정의와 설명은 일단 생략하고, 예제 프로그램의 계산 복잡도를 대문자 O로 표기하는 방법부터 설명해보자.

# algorithm_1
def sum_num(n):
    result = 0
    for i in range(n + 1):
        result += i
    return result

# algorithm_2
def sum_num2(n):
    return (n + 1) * (n / 2)

  첫 번째 알고리즘은 입력 크기 n에 대해 사칙 연산(덧셈)을 n번 해야 한다. 이때 이 알고리즘의 계산 복잡도를 O(n)이라고 표현한다. 필요한 계산 횟수가 입력 크기에 '정비례'할 때는 O(n)이라고 표현한다.

  입력 크기 n에 따라 덧셈을 두 번씩 하는 알고리즘이 있다면 어떻게 표현할까? 얼핏 생각하면 O(2n)으로 표현할 것 같지만 O(n)으로 표현한다. 대문자 O 표기법은 알고리즘에서 필요한 계산 횟수를 정확한 숫자로 표현하는 것이 아니라 입력 크기와의 관계로 표현하기 때문이다.

  예를 들어 n이 10에서 20으로 '2배'가 될 때 2n 역시 20에서 40으로 '2배'가 된다. 이처럼 필요한 계산 횟수가 입력 크기 n과 '정비례'하면 모두 O(n)으로 표기한다. 

  두 번째 알고리즘은 입력 크기 n과 무관하게 사칙연산을 세 번해야 한다. 이때 알고리즘의 계산 복잡도는 O(1)로 표현한다. 앞에서 O(2n)을 O(n)으로 표현하는 것과 같은 원리다. 입력 크기 n과 필요한 계산의 횟수가 무관하다면, 즉 입력 크기가 커져도 계산 시간이 더 늘어나지 않는다면 모두 O(1)로 표기한다.

  대문자 O 표기법은 알고리즘의 대략적인 성능을 표시하는 방법이다. 따라서 굉장히 세밀한 계산 횟수나 소요 시간을 표현한다기보다 입력 크기 n과 필요한 계산 횟수와의 '관계'에 더 주목하는 표현이다.

  어떤 문제를 푸는 알고리즘이 두 개 있는데 하나는 O(n)이고 다른 하나는 O(1)이라면 어떤 것을 골라야 할까? 문제에 주어지는 평균 입력 크기나 각 알고리즘의 실제 계산 방식 등에 따라 차이는 있지만, 입력 크기가 큰 문제를 풀 때는 보통 O(1)인 알고리즘이 훨씬 더 빠르다.

  알고리즘의 계산 복잡도는 시간 복잡도(time complexity)와 공간 복잡도(space complexity)로 나눌 수 있다. 이름에서 알 수 있듯이 시간 복잡도는 어떤 알고리즘을 수행하는 데 얼마나 많은 공간(메모리/기억 장소)이 필요한지 분석한 것이다. 앞에서 사칙연산 횟수로 계산 복잡도를 생각해 보았는데 이것은 시간 복잡도에 해당한다. 어떤 알고리즘을 수행하는 데 필요한 사칙연산의 횟수가 많아지면 결국 알고리즘 전체를 수행하는 시간이 늘어나기 때문이다. 

 

 

참고자료 : 모두의 알고리즘 with 파이썬

https://search.shopping.naver.com/book/catalog/32436282485?cat_id=50010921&frm=PBOKPRO&query=%EB%AA%A8%EB%91%90%EC%9D%98+%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98+with+%ED%8C%8C%EC%9D%B4%EC%8D%AC&NaPm=ct%3Dlacipvnk%7Cci%3D07dc1cd229a35bb4f5401115c49e5040366955d8%7Ctr%3Dboknx%7Csn%3D95694%7Chk%3D716b99dadd7b432f9c31cc9001f96d448b2746c7 

모두의 알고리즘 with 파이썬 : 네이버 도서