알고리즘 분석
알고리즘의 효율성 분석은 구현 전과 구현 후의 두 단계에서 수행할 수 있습니다.
선험적 분석 - 이것은 알고리즘의 이론적 분석으로 정의됩니다. 알고리즘의 효율성은 다음과 같은 다른 모든 요소를 가정하여 측정됩니다. 프로세서의 속도는 일정하며 구현에 영향을 미치지 않습니다.
사후 분석 - 이것은 알고리즘의 경험적 분석으로 정의됩니다. 선택한 알고리즘은 프로그래밍 언어를 사용하여 구현됩니다. 다음으로 선택한 알고리즘이 대상 컴퓨터 시스템에서 실행됩니다. 이 분석에서는 필요한 실행 시간 및 공간과 같은 실제 통계를 수집합니다.
알고리즘 분석은 관련된 다양한 작업의 실행 또는 실행 시간을 다룹니다. 연산의 실행 시간은 연산당 실행되는 컴퓨터 명령어의 수로 정의할 수 있습니다.
알고리즘 복잡성
X를 알고리즘으로 취급하고 N을 입력 데이터의 크기로 취급한다고 가정하면 알고리즘 X가 구현하는 시간과 공간이 X의 효율성을 결정하는 두 가지 주요 요소입니다.
Time Factor - 정렬 알고리즘에서 비교 등 주요 연산 횟수를 세어 시간을 계산하거나 측정합니다.
Space Factor - 공간은 알고리즘에 필요한 최대 메모리 공간을 계산하여 계산 또는 측정됩니다.
알고리즘 f(N)의 복잡성은 입력 데이터의 크기로서 N과 관련하여 알고리즘에 필요한 실행 시간 및/또는 저장 공간을 제공합니다.
공간 복잡성
알고리즘의 공간 복잡도는 알고리즘의 수명 주기에 필요한 메모리 공간의 양을 나타냅니다.
알고리즘에 필요한 공간은 다음 두 구성 요소의 합과 같습니다.
특정 데이터 및 변수(예:단순 변수 및 상수, 프로그램 크기 등)를 저장하는 데 필요한 공간으로 문제의 크기에 종속되지 않는 고정된 부분입니다.
변수 부분은 문제의 크기에 따라 크기가 완전히 달라지는 변수에 필요한 공간입니다. 예를 들어, 재귀 스택 공간, 동적 메모리 할당 등
임의의 알고리즘 p의 공간 복잡도 S(p)는 S(p) =A + Sp(I)입니다. 여기서 A는 고정 부분으로 처리되고 S(I)는 인스턴스 특성 I에 의존하는 알고리즘의 가변 부분으로 처리됩니다. . 다음은 개념을 설명하기 위한 간단한 예입니다.
알고리즘
SUM(P, Q) Step 1 - START Step 2 - R ← P + Q + 10 Step 3 - Stop
여기에 세 개의 변수 P, Q 및 R과 하나의 상수가 있습니다. 따라서 S(p) =1+3입니다. 이제 공간은 주어진 상수 유형 및 변수의 데이터 유형에 따라 달라지며 그에 따라 곱해집니다.
시간 복잡도
알고리즘의 시간 복잡도는 알고리즘이 완료될 때까지 실행하는 데 필요한 시간을 나타냅니다. 시간 요구 사항은 수치 함수 t(N)으로 표시하거나 정의할 수 있습니다. 여기서 t(N)은 각 단계에 일정한 시간이 걸린다면 단계 수로 측정할 수 있습니다.
예를 들어 두 개의 n비트 정수를 더하는 경우 N 단계를 수행합니다. 결과적으로, 총 계산 시간은 t(N) =c*n이며, 여기서 c는 2비트를 더하는 데 소요되는 시간입니다. 여기에서 t(N)은 입력 크기가 증가함에 따라 선형적으로 증가하는 것을 관찰합니다.