Python 예제를 사용한 Big O 표기법 및 알고리즘 분석

개요

일반적으로 컴퓨터 프로그램을 사용하여 문제를 해결하는 방법에는 여러 가지가 있습니다. 예를 들어 배열의 항목을 정렬하는 방법에는 여러 가지가 있습니다. 병합 정렬, 버블 정렬, 삽입 정렬, 등등. 이러한 모든 알고리즘에는 고유한 장단점이 있으며 개발자의 임무는 모든 사용 사례에서 사용할 최상의 알고리즘을 선택할 수 있도록 가중치를 부여하는 것입니다. 즉, 문제에 대한 솔루션이 여러 개 있을 때 특정 문제를 해결하기 위해 어떤 알고리즘을 사용할 것인지가 주요 문제입니다.

알고리즘 분석 서로 다른 알고리즘의 복잡성을 분석하고 당면한 문제를 해결하기 위해 가장 효율적인 알고리즘을 찾는 것을 말합니다. 빅오 표기법 알고리즘의 복잡성을 설명하는 데 사용되는 통계적 척도입니다.

이 가이드에서는 먼저 알고리즘 분석에 대해 간략하게 검토한 다음 Big-O 표기법에 대해 자세히 살펴보겠습니다. Big-O 표기법을 사용하여 다양한 Python 함수를 사용하여 알고리즘 복잡성을 찾는 방법을 살펴보겠습니다.

알고리즘 분석이 중요한 이유는 무엇입니까?

알고리즘 분석이 왜 중요한지 이해하기 위해 간단한 예를 들어보겠습니다. 관리자가 두 명의 직원에게 사용자가 입력한 숫자의 계승을 계산하는 Python 알고리즘을 설계하는 작업을 제공한다고 가정합니다. 첫 번째 직원이 개발한 알고리즘은 다음과 같습니다.

def fact(n):
    product = 1
    for i in range(n):
        product = product * (i+1)
    return product

print(fact(5))

알고리즘은 단순히 정수를 인수로 사용합니다. 내부 fact() 함수라는 변수 product 로 초기화됩니다 1. 루프는 다음에서 실행됩니다. 1 에 n 각 반복 동안 값 product 루프에 의해 반복되는 숫자로 곱해지고 결과는 product 다시 변수. 루프가 실행된 후, product 변수에는 계승이 포함됩니다.

마찬가지로 두 번째 직원도 숫자의 계승을 계산하는 알고리즘을 개발했습니다. 두 번째 직원은 재귀 함수를 사용하여 숫자의 계승을 계산했습니다. n:

def fact2(n):
    if n == 0:
        return 1
    else:
        return n * fact2(n-1)

print(fact2(5))

관리자는 사용할 알고리즘을 결정해야 합니다. 그렇게 하기 위해 그들은 어떤 알고리즘이 더 빨리 실행되는지 선택하기로 결정했습니다. 그렇게 하는 한 가지 방법은 동일한 입력에서 코드를 실행하는 데 필요한 시간을 찾는 것입니다.

Jupyter 노트북에서 다음을 사용할 수 있습니다. %timeit 리터럴 다음에 함수를 호출하여 함수가 실행하는 데 걸리는 시간을 찾습니다.

%timeit fact(50)

이것은 우리에게 다음을 줄 것입니다:

9 µs ± 405 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

출력은 알고리즘이 9 마이크로 초 (플러스/마이너스 45나노초) 루프당.

마찬가지로 두 번째 접근 방식을 실행하는 데 걸리는 시간을 계산할 수 있습니다.

%timeit fact2(50)

결과는 다음과 같습니다.

15.7 µs ± 427 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

재귀를 포함하는 두 번째 알고리즘은 15 마이크로 초 (플러스/마이너스 427나노초).

실행 시간은 첫 번째 알고리즘이 재귀를 포함하는 두 번째 알고리즘에 비해 빠르다는 것을 보여줍니다. 큰 입력을 처리할 때 성능 차이가 더 커질 수 있습니다.

그러나 실행 시간은 하드웨어에 따라 달라지기 때문에 알고리즘의 복잡성을 측정하는 좋은 메트릭이 아닙니다. 알고리즘에 대한 보다 객관적인 복잡성 분석 메트릭이 필요합니다. 여기는 큰 O 표기법 게임에 온다.

Big-O 표기법을 사용한 알고리즘 분석

Big-O 표기법은 알고리즘에 대한 입력과 알고리즘을 실행하는 데 필요한 단계 간의 관계를 나타냅니다. 여는 괄호와 닫는 괄호가 뒤에 오는 큰 "O"로 표시됩니다. 괄호 안에는 입력과 알고리즘이 취한 단계 간의 관계가 "n"을 사용하여 표시됩니다.

핵심 테이크어웨이는 – Big-O는 관심이 없습니다. 특별한 다음과 같은 알고리즘을 실행하는 인스턴스 fact(50), 하지만 오히려, 얼마나 잘 규모 증가하는 입력이 주어집니다. 이것은 구체적인 인스턴스에 대한 구체적인 시간보다 평가를 위한 훨씬 더 나은 지표입니다!

예를 들어 선형 관계 알고리즘이 실행을 완료하기 위해 취한 단계와 입력 사이에 사용된 Big-O 표기법은 다음과 같습니다. O (N). 마찬가지로 Big-O 표기법은 이차 함수 is XNUMX(n²).

직관을 구축하려면:

• O (N): 에 n=1, 1단계가 수행됩니다. ~에 n=10, 10단계를 수행합니다.
• XNUMX(n²): 에 n=1, 1단계가 수행됩니다. ~에 n=10, 100단계를 수행합니다.

At n=1, 이 둘은 같은 성능을 낼 것입니다! 이것이 입력과 해당 입력을 처리하는 단계 수 사이의 관계를 관찰하는 것이 일부 구체적인 입력으로 함수를 평가하는 것보다 더 나은 또 다른 이유입니다.

다음은 가장 일반적인 Big-O 기능 중 일부입니다.

성함	빅 오
상수	O (c)
선의	O (N)
이차	XNUMX(n²)
입방체	오(n³)
지수의	오(2ⁿ)
대수	O (로그 (n))
로그 선형	O(nlog(n))

이러한 기능을 시각화하고 비교할 수 있습니다.

일반적으로 말해서 선형보다 더 나쁜 것은 나쁜 복잡성(즉, 비효율적)으로 간주되며 가능하면 피해야 합니다. 선형 복잡성은 괜찮고 일반적으로 필요악입니다. 로그가 좋습니다. 상수는 놀랍습니다!

Big-O가 계산되는 방법에 대한 아이디어를 얻기 위해 상수, 선형 및 XNUMX차 복잡성의 몇 가지 예를 살펴보겠습니다.

일정한 복잡성 – 오(C)

알고리즘 실행을 완료하는 데 필요한 단계가 입력 수에 관계없이 일정하게 유지되면 알고리즘의 복잡성이 일정하다고 합니다. 일정한 복잡성은 다음과 같이 표시됩니다. O (c) 어디에 c 임의의 상수일 수 있습니다.

목록에서 첫 번째 항목의 제곱을 찾은 다음 화면에 인쇄하는 간단한 알고리즘을 Python으로 작성해 보겠습니다.

def constant_algo(items):
    result = items[0] * items[0]
    print(result)

constant_algo([4, 5, 6, 8])

위의 스크립트에서, 입력 크기에 관계없이, 또는 입력 목록의 항목 수 items, 알고리즘은 2단계만 수행합니다.

1. 첫 번째 요소의 제곱 찾기
2. 화면에 결과를 인쇄합니다.

따라서 복잡성은 일정하게 유지됩니다.

다양한 크기의 선을 그리면 items X축에 걸음 수를 입력하고 Y축에 걸음 수를 입력하면 직선이 됩니다. 이를 시각화하는 데 도움이 되는 짧은 스크립트를 만들어 보겠습니다. 입력 수에 관계없이 실행된 단계 수는 동일하게 유지됩니다.

steps = []
def constant(n):
    return 1
    
for i in range(1, 100):
    steps.append(constant(i))
plt.plot(steps)

선형 복잡성 – O (N)

알고리즘 실행을 완료하는 데 필요한 단계가 입력 수에 따라 선형적으로 증가하거나 감소하는 경우 알고리즘의 복잡성을 선형이라고 합니다. 선형 복잡도는 다음과 같이 표시됩니다. O (N).

이 예에서 목록의 모든 항목을 콘솔에 표시하는 간단한 프로그램을 작성해 보겠습니다.

def linear_algo(items):
    for item in items:
        print(item)

linear_algo([4, 5, 6, 8])

의 복잡성 linear_algo() for 루프의 반복 횟수가 다음과 같을 것이기 때문에 위의 예에서 함수는 선형입니다. 입력의 크기와 동일 items 정렬. 예를 들어 4개의 항목이 있는 경우 items 목록에서 for 루프는 4번 실행됩니다.

x축의 입력 수와 y축의 단계 수를 사용하여 선형 복잡도 알고리즘에 대한 플롯을 빠르게 생성해 보겠습니다.

steps = []
def linear(n):
    return n
    
for i in range(1, 100):
    steps.append(linear(i))
    
plt.plot(steps)
plt.xlabel('Inputs')
plt.ylabel('Steps')

결과는 다음과 같습니다.

주목해야 할 중요한 점은 입력이 크면 상수가 가치를 잃는 경향이 있다는 것입니다. 이것이 우리가 일반적으로 Big-O 표기법에서 상수를 제거하는 이유이며 O(2n)과 같은 표현식은 일반적으로 O(n)으로 단축됩니다. O(2n)과 O(n)은 모두 선형입니다. 선형 관계가 중요한 것이지 구체적인 값이 아닙니다. 예를 들어 수정해보자 linear_algo():

def linear_algo(items):
    for item in items:
        print(item)

    for item in items:
        print(item)

linear_algo([4, 5, 6, 8])

입력을 반복하는 두 개의 for 루프가 있습니다. items 목록. 따라서 알고리즘의 복잡성은 O (2n)그러나 입력 목록의 무한 항목의 경우 무한대의 두 배는 여전히 무한대와 같습니다. 우리는 상수를 무시할 수 있습니다 2 (궁극적으로 중요하지 않기 때문에) 알고리즘의 복잡성은 그대로 유지됩니다. O (N).

X축에 입력을 표시하고 Y축에 단계 수를 표시하여 이 새로운 알고리즘을 시각화해 보겠습니다.

steps = []
def linear(n):
    return 2*n
    
for i in range(1, 100):
    steps.append(linear(i))
    
plt.plot(steps)
plt.xlabel('Inputs')
plt.ylabel('Steps')

위의 스크립트에서 분명히 알 수 있습니다. y=2n그러나 출력은 선형이며 다음과 같습니다.

XNUMX차 복잡성 – XNUMX(n²)

알고리즘을 실행하는 데 필요한 단계가 입력 항목 수의 XNUMX차 함수인 경우 알고리즘의 복잡성을 XNUMX차라고 합니다. XNUMX차 복잡도는 다음과 같이 표시됩니다. XNUMX(n²):

def quadratic_algo(items):
    for item in items:
        for item2 in items:
            print(item, ' ' ,item2)

quadratic_algo([4, 5, 6, 8])

입력 목록의 모든 항목을 반복하는 외부 루프와 입력 목록의 모든 항목을 다시 반복하는 중첩된 내부 루프가 있습니다. 수행된 총 단계 수는 n*n이며, 여기서 n은 입력 배열의 항목 수입니다.

다음 그래프는 XNUMX차 복잡성이 있는 알고리즘의 단계에 대한 입력 수를 표시합니다.

로그 복잡도 – O (로그온)

일부 알고리즘은 다음과 같은 대수 복잡도를 달성합니다. 이진 검색. 이진 검색은 다음을 확인하여 배열의 요소를 검색합니다. 중간 배열의 요소가 아닌 부분을 잘라냅니다. 나머지 절반에 대해 이 작업을 다시 수행하고 요소를 찾을 때까지 동일한 단계를 계속합니다. 각 단계에서는 반쪽 배열의 요소 수.

이를 위해서는 배열을 정렬해야 하며 데이터에 대한 가정을 해야 합니다(예: 정렬됨).

들어오는 데이터에 대해 가정할 수 있으면 알고리즘의 복잡성을 줄이는 단계를 수행할 수 있습니다. 로그 복잡도는 고도로 확장된 입력에서도 우수한 성능을 달성하므로 바람직합니다.

복잡한 기능의 복잡성을 찾으십니까?

이전 예에서 우리는 입력에 대해 상당히 간단한 함수를 가지고 있었습니다. 하지만 입력에서 (여러) 다른 함수를 호출하는 함수의 BigO를 어떻게 계산합니까?

한 번 보자:

def complex_algo(items):

    for i in range(5):
        print("Python is awesome")

    for item in items:
        print(item)

    for item in items:
        print(item)

    print("Big O")
    print("Big O")
    print("Big O")

complex_algo([4, 5, 6, 8])

위의 스크립트에서 여러 작업이 수행되고 있습니다. 먼저 문자열이 다음을 사용하여 콘솔에 5번 인쇄됩니다. print 성명. 다음으로 입력 목록을 화면에 두 번 출력하고 마지막으로 콘솔에 다른 문자열을 세 번 출력합니다. 그러한 알고리즘의 복잡성을 찾으려면 알고리즘 코드를 부분으로 분해하고 개별 조각의 복잡성을 찾으려고 노력해야 합니다. 각 조각의 복잡성을 표시하십시오.

첫 번째 섹션에는 다음이 있습니다.

for i in range(5):
	print("Python is awesome")

이 부분의 복잡도는 O (5) 입력에 관계없이 이 코드 조각에서 XNUMX개의 일정한 단계가 수행되기 때문입니다.

다음으로:

for item in items:
	print(item)

우리는 위의 코드 조각의 복잡성이 O (N). 마찬가지로 다음 코드 조각의 복잡성도 O (N):

for item in items:
	print(item)

마지막으로 다음 코드에서는 문자열이 세 번 인쇄되므로 복잡성은 다음과 같습니다. O (3):

print("Big O")
print("Big O")
print("Big O")

전체 복잡성을 찾으려면 다음과 같은 개별 복잡성을 추가하기만 하면 됩니다.

O(5) + O(n) + O(n) + O(3)

위를 단순화하면 다음을 얻습니다.

O(8) + O(2n) = O(8+2n)

앞서 우리는 입력(이 경우 길이가 n인)이 극도로 커지면 상수가 무의미해집니다. 즉 무한대의 두 배 또는 절반이 여전히 무한대로 남아 있다고 말했습니다. 따라서 상수를 무시할 수 있습니다. 알고리즘의 최종 복잡성은 다음과 같습니다. O (N)!

최악의 경우와 최상의 경우의 복잡성

일반적으로 누군가가 알고리즘의 복잡성에 대해 질문하면 최악의 복잡성(Big-O)에 관심이 있습니다. 때로는 최상의 복잡성(Big-Omega)에도 관심이 있을 수 있습니다.

이들 간의 관계를 이해하기 위해 다른 코드를 살펴보겠습니다.

def search_algo(num, items):
    for item in items:
        if item == num:
            return True
        else:
            pass
nums = [2, 4, 6, 8, 10]

print(search_algo(2, nums))

위의 스크립트에는 숫자와 숫자 목록을 입력으로 받는 함수가 있습니다. 전달된 숫자가 숫자 목록에서 발견되면 true를 반환하고, 그렇지 않으면 반환합니다. None. 목록에서 2를 검색하면 첫 번째 비교에서 찾을 수 있습니다. 이것은 검색된 항목이 첫 번째 검색된 인덱스에서 발견된다는 점에서 알고리즘의 최상의 경우 복잡성입니다. 최상의 경우 복잡성, 이 경우 O (1). 반면에 10번을 검색하면 마지막으로 검색된 인덱스에서 찾을 수 있습니다. 알고리즘은 목록의 모든 항목을 검색해야 하므로 최악의 복잡성 된다 O (N).

최상의 및 최악의 복잡성 외에도 다음을 계산할 수 있습니다. 평균 복잡성 (Big-Theta) 알고리즘의 "임의의 입력이 주어지면 알고리즘의 예상 시간 복잡도는 얼마입니까?"

공간 복잡성

알고리즘 실행을 완료하는 데 필요한 단계 수를 계산하는 시간 복잡성 외에도 다음을 찾을 수 있습니다. 공간 복잡성 프로그램을 실행하는 동안 메모리에 할당해야 하는 공간의 양을 나타냅니다.

다음 예를 살펴보십시오.

def return_squares(n):
    square_list = []
    for num in n:
        square_list.append(num * num)

    return square_list

nums = [2, 4, 6, 8, 10]
print(return_squares(nums))

XNUMXD덴탈의 return_squares() 함수는 정수 목록을 허용하고 해당하는 사각형이 있는 목록을 반환합니다. 알고리즘은 입력 목록과 동일한 수의 항목에 대해 메모리를 할당해야 합니다. 따라서 알고리즘의 공간 복잡도는 O (N).

결론

Big-O 표기법은 알고리즘의 복잡성을 측정하는 데 사용되는 표준 메트릭입니다. 이 가이드에서는 Big-O 표기법이 무엇인지, 다양한 알고리즘의 복잡성을 측정하는 데 어떻게 사용할 수 있는지 연구했습니다. 또한 다양한 Python 예제를 사용하여 다양한 유형의 Big-O 함수를 연구했습니다. 마지막으로 공간복잡도와 함께 최악의 복잡도와 최선의 복잡도를 간략히 살펴보았다.