공간 복잡성 | 코드 성능 측정: DSA 002

나는 시간복잡도에 대해 썼다. 증가하는 입력 크기와 관련하여 코드를 측정하는 방법입니다.

시간 복잡도는 기본적으로 입력 크기와 실행 시간 간의 관계입니다.

그것에 대해 생각

분명히 휴대 전화에 앱이 있습니다. 데이터를 로드하는 데 시간이 덜 걸리고 공간을 적게 차지하는 것을 선호할 가능성이 큽니다. 시간을 측정하는 데 사용되는 요소는 시간 복잡도와 관련이 있습니다. 그러나 공간은 어떻습니까? 코드가 사용하는 공간을 어떻게 측정합니까?

공간 복잡성

시스템에서 사용되는 입력 크기와 메모리 간의 관계입니다.

코드를 최적화하려면 시간과 공간이 더 적게 소요되어야 합니다. 따라서 여기에서 공간 복잡성이 발생합니다. 이것이 코드가 차지하는 공간을 측정하는 방법이기 때문입니다.

공간 복잡도 계산

코드에서 사용하는 공간은 사용되는 변수의 수에 따라 다릅니다. 변수가 많을수록 더 많은 공간이 사용됩니다.

코드에서 소비하는 메모리 양은 할당된 변수 수에 정비례합니다.

sum = 0
i = 0
while (i < 24):
    sum += i
    i += 1
print(sum)

여기에 i 및 sum 메모리에 할당하는 2개의 변수가 있습니다. 이제 sum 값이 증가하더라도 해당 변수에서 사용하는 메모리는 동일합니다. 따라서 이 코드의 공간 복잡도는 O(1)이 됩니다.

이제 배열의 예를 들어 보겠습니다. 기본적으로 요소 목록을 저장하는 데이터 구조입니다. 나중에 배열에 대해 자세히 이야기하겠습니다.

def create_array(n):
    a = []
    for i in range(n):
        a.append(i)
    return a

이 함수에서는 정수n를 입력으로 사용합니다. 그런 다음 배열을 만듭니다. 루프를 사용하여 0에서 n-1까지의 숫자를 배열에 저장합니다. 그런 다음 반환합니다. 따라서 기본적으로 우리가 하는 일은 일련의 숫자를 생성하고 배열에 저장하는 것입니다. 여기에서 입력 크기가 증가함에 따라 코드에서 사용하는 공간도 증가합니다. 따라서 이 코드의 공간 복잡도는 O(n)입니다.

여기에서 크기를 확인할 수 있습니다.


sys.getsizeof() 파이썬에서 특정 함수, 클래스, 변수 등의 크기를 제공합니다.

당신이 이해하지 못했다면 댓글 섹션에서 자유롭게 비판할 수 있기를 바랍니다. 당신의 소중한 시간을 낭비했다면 비난해도 괜찮습니다. 또한 의심스러운 점이 있으면 댓글 섹션에 자유롭게 올려주세요.