Python을 사용하여 O(n)을 시각화합니다.

소개

컴퓨터 과학 및 프로그래밍 분야에서는 알고리즘의 효율성을 이해하는 것이 최적화되고 빠르게 수행되는 소프트웨어를 만드는 데 도움이 되므로 매우 중요합니다. 시간 복잡도는 입력 크기가 커짐에 따라 알고리즘의 실행 시간이 어떻게 변하는지 측정하기 때문에 이 맥락에서 중요한 개념입니다. 일반적으로 사용되는 시간 복잡도 클래스 O(n)은 입력 크기와 실행 시간 간의 선형 관계를 나타냅니다.

정의

컴퓨터 과학에서 알고리즘 복잡도는 알고리즘의 입력 크기를 기준으로 시간, 공간 활용도 등 필요한 리소스를 평가하는 것입니다. 또한 입력 크기를 고려할 때 알고리즘이 얼마나 빠르게 수행되는지에 대한 이해를 지원합니다. 알고리즘 복잡도를 설명하는 데 사용되는 주요 표기법은 Big O 표기법(O(n))입니다.

문법

으아악

0에서 'n-1'까지의 범위를 기반으로 특정 명령어 세트를 실행하고 각 반복마다 작업 또는 작업 세트를 수행하는 'for' 루프입니다. 여기서 'n'은 반복 횟수를 나타냅니다.

O(n) 시간 복잡도에서는 입력 크기 'n'이 증가함에 따라 실행 시간이 비례적으로 증가합니다. 'n'이 증가함에 따라 루프의 반복 횟수와 루프를 완료하는 데 필요한 시간이 비례적으로 증가합니다. 선형 시간 복잡도는 입력 크기와 실행 시간 사이에 직접적인 비례 관계를 나타냅니다.

입력 크기 'n'에 관계없이 모든 작업 또는 작업 시퀀스를 루프에서 실행할 수 있습니다. 여기서 주목해야 할 주요 측면은 루프가 'n' 반복을 실행하여 선형 시간 복잡도가 발생한다는 것입니다.

알고리즘

• 1단계: 변수 합계를 0

으로 초기화합니다.

• 2단계: 제공된 목록의 각 요소를 반복합니다

• 3단계: 요소를 현재 합계 값에 병합합니다.

• 4단계: 루프가 끝난 후 합계가 반환되어야 합니다.

• 5단계: 종료

방법

• 방법 1: 그리는 시간과 입력 크기의 관계

• 방법 2: 그리기 작업과 입력 크기의 관계

방법 1: 시간과 입력 크기 비교

예

으아악

출력

이 코드는 다양한 입력 크기에서 `algo_time()` 알고리즘의 실행 시간을 측정하는 데 사용됩니다. 테스트하려는 입력 크기와 해당 실행 시간을 이 목록에 저장합니다.

'for' 루프를 사용하여 다양한 입력 크기를 반복합니다. 이 경우 루프는 1000에서 11000에 가까워질 때까지 실행되며 매번 1000씩 증가합니다. 더 자세히 설명하기 위해 'n' 값을 1000에서 10000까지 1000씩 변경하여 알고리즘을 평가할 계획입니다.

루프 내에서 각 입력 크기에 대한 `algo_time()` 함수의 실행 시간을 측정합니다. 시간 추적을 시작하려면 함수를 호출하기 전에 `time.time()`을 사용하고 함수 실행이 완료되자마자 중지합니다. 그런 다음 'execution_time'이라는 변수에 기간을 저장합니다.

주어진 입력 크기('n')의 각 입력 값과 해당 실행 시간을 해당 목록('input_sizes' 및 'execution_times')에 추가합니다.

루프가 완료되면 플롯을 생성하는 데 필요한 데이터가 확보됩니다. 'plt.plot(input_sizes,execution_times)'는 우리가 수집한 데이터를 사용하여 기본 선 차트를 생성합니다. x축에는 다양한 입력 크기를 나타내는 'input_sizes' 값이 표시됩니다.

'plt.xlabel()'과 'plt.ylabel()'은 최종적으로 각각 좌표축의 의미를 표시하는데 사용되며, 'plt.show()' 함수를 호출하면 그래프를 표현할 수 있습니다.

이 코드를 실행하면 입력 크기('n')가 증가함에 따라 실행 시간이 증가하는 것을 그래프로 시각화할 수 있습니다. 알고리즘의 시간복잡도를 O(n)이라고 가정하면, 그래프를 그릴 때 입력 크기와 실행 시간 사이에 거의 직선적인 상관관계가 있다고 근사할 수 있습니다.

방법 2: 그리기 작업과 입력 크기의 관계

예

으아악

출력

이 코드는 다양한 입력 크기에서 `algo_ops()` 알고리즘이 수행하는 작업 수를 분석하도록 설계되었습니다. `algo_ops()` 함수를 활용하면 0부터 주어진 입력 매개변수 'n'까지의 범위에 있는 모든 값의 합을 계산하는 동시에 각 계산 중에 수행되는 모든 작업을 추적하고 기록할 수 있습니다.

먼저 그래프와 같은 시각화를 생성할 수 있는 'matplotlib.pyplot' 모듈을 가져옵니다.

다음으로, 입력 숫자 'n'을 받아들이는 algo_ops() 함수를 정의합니다. 함수 내에서 두 개의 변수를 초기화합니다. 'ops'는 작업 횟수를 계산하고 'sum'은 숫자의 누적 합계를 저장합니다.

이 배열은 확인하려는 차원과 해당 실행 기간을 저장합니다.

반복 루프를 활용하는 한 가지 방법은 여러 입력 스케일을 반복하는 것입니다. 이 경우 루프 실행 범위는 1000~10000(11000 제외)입니다. 즉, 1000에서 10000 사이의 변수 'n'을 100씩 증가시켜 기술을 평가한다는 의미입니다.

루프에서는 모든 입력 크기에 대해 `algo_time()` 프로세스의 성능을 계산합니다. 프로시저를 호출하기 전에 `time.time()`을 사용하여 스톱워치를 시작하고 서브루틴 실행이 완료된 직후에 종료합니다. 다음으로, 'execution_기간'이라는 변수에 시간 간격을 저장합니다.

각 입력 크기에 대해 'input_sizes'라는 목록에 입력 값('n')을 포함합니다. 또한 'execution_times' 컬렉션에 해당 처리 시간을 추가합니다.

루프가 완료된 후 차트를 만드는 데 필요한 기본 데이터가 축적되었습니다. 'plt.plot(input_sizes,execution_times)' 구문은 수집된 데이터를 이용하여 기본 라인 차트를 생성합니다. 'input_sizes'의 값은 x축에 표시되며 다양한 입력 크기를 나타냅니다. 'execution_times' 값은 세로축에 표시되며 다양한 입력 크기로 `algo_time()` 함수를 실행하는 데 필요한 시간을 나타냅니다.

마지막으로 'plt.xlabel()', 'plt.ylabel()'을 통해 좌표계에 라벨을 붙여 각 축의 의미를 보여줍니다. 다음으로 'plt.show()' 함수를 실행하여 그래프를 렌더링합니다.

프로그램을 실행하면 입력('n')의 크기가 커질 때 처리 시간이 어떻게 증가하는지 그래프가 표시됩니다.

결론

요약하자면, Matplotlib을 사용하여 Python에서 시간 복잡성과 시각화를 마스터하는 것은 효율적이고 최적화된 소프트웨어 솔루션을 만들려는 모든 프로그래머에게 귀중한 기술입니다. 다양한 입력 규모에서 알고리즘이 어떻게 작동하는지 이해하면 복잡한 문제를 해결하고 적시에 효율적인 방식으로 결과를 제공하는 강력한 애플리케이션을 구축할 수 있습니다.

위 내용은 Python을 사용하여 O(n)을 시각화합니다.의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!