알고리즘의 실행 시간 효율성을 측정하는 방법은 무엇입니까?

기계 성능을 무시한다는 원칙하에 알고리즘의 실행 시간을 측정하기 위해 알고리즘 시간 복잡도를 사용합니다.
1. 시간 빈도
알고리즘을 실행하는 데 걸리는 시간은 이론적으로 계산할 수 없습니다. 컴퓨터에서 테스트를 실행해야만 알 수 있습니다. 그러나 모든 알고리즘을 컴퓨터에서 테스트하는 것은 불가능하고 불필요합니다. 어떤 알고리즘이 더 많은 시간이 걸리고 어떤 알고리즘이 더 적은 시간이 걸리는지만 알면 됩니다. 그리고 알고리즘에 걸리는 시간은 알고리즘의 명령문 실행 횟수에 비례합니다. 더 많은 명령문이 실행되는 알고리즘은 더 많은 시간이 걸립니다. 알고리즘의 명령문 실행 횟수를 명령문 빈도 또는 시간 빈도라고 합니다. 이를 T(n)으로 표시합니다.
2. 시간 복잡도
방금 언급한 시간 주파수에서 n을 문제의 규모라고 합니다. n이 계속 변하면 시간 주파수 T(n)도 계속 변합니다. 하지만 때로는 변화할 때 어떤 패턴이 나타나는지 알고 싶을 때가 있습니다. 이를 위해 시간복잡도라는 개념을 소개한다.

일반적으로 알고리즘의 기본 연산이 반복되는 횟수는 문제 크기 n의 함수이며, 특정 보조 함수 f(n)이 있는 경우 n이 무한대에 가까워지면 T(n)/f(n)의 극한값은 0이 아닌 상수인 경우 f(n)은 T(n)과 동일한 크기 차수의 함수라고 합니다. T(n)=O(f(n))으로 표시되는 O(f(n))은 알고리즘의 점근적 시간 복잡도, 줄여서 시간 복잡도라고 합니다.

다양한 알고리즘에서 알고리즘의 명령문 실행 횟수가 일정할 경우 시간 복잡도는 O(1)입니다. 또한 시간 빈도가 다른 경우 시간 복잡도는 T( n )=n^2+3n+4 및 T(n)=4n^2+2n+1 은 서로 다른 주파수를 갖지만 시간 복잡도는 동일하며 둘 다 O(n^2)입니다.
크기가 오름차순으로 정렬된 일반적인 시간 복잡도는 다음과 같습니다.
상수 차수 O(1), 로그 차수 O(log2n)(밑이 2인 n의 로그, 아래와 같음), 선형 차수 O(n),
선형 로그 차수 O(nlog2n), 제곱차 O(n^2), 3차 차수 O(n^3),...,
k차수 O(n^k), 지수 차수 O(2^n). 문제 크기 n이 계속 증가함에 따라 위의 시간 복잡도는 계속 증가하고 알고리즘의 실행 효율성은 낮아지게 됩니다.
알고리즘의 시간 성능 분석
(1) 알고리즘이 소비한 시간 및 명령문 빈도

알고리즘이 소비한 시간 = 알고리즘 내 각 명령문의 실행 시간의 합

각 명령문의 실행 시간 = 명령문의 실행 횟수 명령문(즉, 빈도수) × 명령문을 한 번 실행하는 데 필요한 시간 알고리즘이 프로그램으로 변환된 후 각 명령문을 한 번 실행하는 데 필요한 시간은 기계의 명령 성능, 속도 및 생성된 코드의 품질에 따라 다릅니다. 요인을 결정하는 것은 어렵습니다.

기계의 소프트웨어 및 하드웨어 시스템과 독립적으로 알고리즘의 시간 소비를 분석하려면 각 명령문을 한 번 실행하는 데 필요한 시간을 단위 시간으로 가정하고, 알고리즘의 시간 소비는 알고리즘의 모든 명령문의 빈도라고 가정합니다. 그리고.
두 n차 제곱 행렬의 곱 C=A×B를 구하는 알고리즘은 다음과 같습니다.

　　# define n 100 // n 可根据需要定义,这里假定为100
　　void MatrixMultiply(int A[a]，int B [n][n]，int C[n][n])
　　{ //右边列为各语句的频度
　　int i ,j ,k;
　　 for(i=0; i<n;j++) n+1
　　 for (j=0;j<n;j++) { n(n+1)
　　 C[i][j]=0; n
　　 for (k=0; k<n; k++) nn(n+1)
　　 C[i][j]=C[i][j]+A[i][k]*B[k][j];n
　　}
　　}

이 알고리즘에 포함된 모든 문의 빈도의 합(즉, 알고리즘의 시간 소모) )은 다음과 같습니다.

T(n) =nn(n+1) (1.1)

분석: 명령문 (1)의 루프 제어 변수 i는 n으로 증가해야 하며 i=n이 될 때까지 테스트는 종료되지 않습니다. 확립된. 따라서 주파수는 n+1입니다. 그러나 루프 본문은 n번만 실행될 수 있습니다. 명령문 (2)는 명령문 (1)의 루프 본문에 있는 명령문으로서 n 번 실행되어야 하지만 명령문 (2) 자체는 n+1 번 실행되어야 하므로 명령문 (2)의 빈도는 n( n+1). 같은 방식으로 문장 (3), (4), (5)의 빈도는 각각 n, nn(n+1), n입니다.

MatrixMultiply 알고리즘의 시간 소모 T(n)은 행렬 차수 n3의 함수입니다.

(2) 문제 규모와 알고리즘 시간 복잡도
문제를 해결하기 위한 알고리즘의 입력량을 문제의 크기(Size)라고 하며 일반적으로 정수로 표시합니다.

매트릭스 제품 문제의 규모는 매트릭스의 순서입니다.

그래프 이론 문제의 크기는 그래프의 꼭지점 또는 모서리의 수입니다.

알고리즘의 시간 복잡도(Time Complexity, 시간 복잡도라고도 함) T(n)는 알고리즘의 시간 소비이며 알고리즘으로 해결되는 문제의 크기 n에 대한 함수입니다. 문제 n의 크기가 무한대에 접근할 때 시간 복잡도 T(n)의 크기(차수) 차수를 알고리즘의 점근적 시간 복잡도라고 합니다.

MatrixMultidy 알고리즘의 시간 복잡도 T(n)은 방정식 (1.1)에 나와 있습니다. n이 무한대인 경우 T(n)~O(n3)이 분명합니다.

이는 n이 클 때를 보여줍니다. 충분, T n3에 대한 (n)의 비율은 0이 아닌 상수입니다. 즉, T(n)과 n3은 동일한 차수이거나 T(n)과 n3의 크기는 동일합니다. T(n)=O(n3)으로 표시되는 것은 MatrixMultiply 알고리즘의 점근적 시간 복잡도입니다.

(3) 점근적 시간 복잡도는 알고리즘의 시간 성능을 평가합니다.

알고리즘의 시간 성능을 평가하기 위해 주로 알고리즘의 시간 복잡도(즉, 알고리즘의 점근적 시간 복잡도)의 크기 차수를 사용합니다.
MatrixMultiply 알고리즘의 시간 복잡도는 일반적으로 T(n)=O(n3)이고, f(n)=n3은 알고리즘에서 문장 (5)의 빈도입니다. 다음으로, 알고리즘의 시간 복잡도를 찾는 방법을 설명하는 예를 제공하겠습니다.

i와 j의 내용을 교환합니다.

Temp=i;
i=j;
j=temp;

　　以上三条单个语句的频度均为1，该程序段的执行时间是一个与问题规模n无关的常数。算法的时间复杂度为常数阶，记作T(n)=O(1)。　　
注意：如果算法的执行时间不随着问题规模n的增加而增长，即使算法中有上千条语句，其执行时间也不过是一个较大的常数。此类算法的时间复杂度是O(1)。
变量计数之一：

　　 x=0;y=0;
　　 for(k-1;k<=n;k++)
　　 x++;
　　 for(i=1;i<=n;i++)
　　 for(j=1;j<=n;j++)
　　 y++;

一般情况下，对步进循环语句只需考虑循环体中语句的执行次数，忽略该语句中步长加1、终值判别、控制转移等成分。因此，以上程序段中频度最大的语句是(6)，其频度为f(n)=n2，所以该程序段的时间复杂度为T(n)=O(n2)。

当有若干个循环语句时，算法的时间复杂度是由嵌套层数最多的循环语句中最内层语句的频度f(n)决定的。

变量计数之二：

x=1;
for(i=1;i<=n;i++)
for(j=1;j<=i;j++)
for(k=1;k<=j;k++)
x++;

该程序段中频度最大的语句是(5)，内循环的执行次数虽然与问题规模n没有直接关系，但是却与外层循环的变量取值有关，而最外层循环的次数直接与n有关，因此可以从内层循环向外层分析语句(5)的执行次数：

则该程序段的时间复杂度为T(n)=O(n3/6+低次项)=O(n3)。

（4）算法的时间复杂度不仅仅依赖于问题的规模，还与输入实例的初始状态有关。

在数值A[0..n-1]中查找给定值K的算法大致如下：

i=n-1;
while(i>=0&&(A[i]!=k))
 i--;
return i;

此算法中的语句(3)的频度不仅与问题规模n有关，还与输入实例中A的各元素取值及K的取值有关:

①若A中没有与K相等的元素，则语句(3)的频度f(n)=n；

②若A的最后一个元素等于K,则语句(3)的频度f(n)是常数0。

위 내용은 알고리즘의 실행 시간 효율성을 측정하는 방법은 무엇입니까?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!