알고리즘 실행 시간 계산 (시간 복잡 도)

서로 다른 알고리즘 함수 가 운행 하 는 시간 을 통 해 서로 다른 알고리즘 중 어느 것 이 더 우수한 지 비교 할 수 있 기 때문에 함수 운행 시간 을 계산 하 는 것 이 매우 기본 적 인 지식 이라는 것 을 안다.함수 운행 시간 을 계산 하 는 것 은 제 가 데이터 구조 와 알고리즘 절강대학 진 할머니 의 과정 에서 배 운 것 입 니 다. 다음은 구체 적 인 과정 을 말씀 드 리 겠 습 니 다.
\ # 시간 복잡 도 우선 시간 복잡 도 를 회상 해 보 자.컴퓨터 과학 에서 알고리즘 의 시간 복잡 도 는 함수 로 이 알고리즘 의 운행 시간 을 정량 적 으로 묘사 했다.이것 은 알고리즘 입력 값 을 대표 하 는 문자열 의 길이 에 관 한 함수 입 니 다.시간 복잡 도 는 항상 큰 O 기호 로 표현 하 는데 이 함수 의 낮은 단계 항목 과 첫 번 째 계 수 를 포함 하지 않 습 니 다.이런 방식 을 사용 할 때 시간 복잡 도 는 점 근 이 라 고 할 수 있 는데 입력 값 의 크기 가 무한 에 가 까 워 질 때의 상황 을 고찰 한다.
시간 복잡 도 단위
1
log n
n
n*log n
n^2
n^3
2^n
n!
\ # 다항식 을 푸 는 두 가지 방법의 운행 시간 을 계산 하 는 것 은 하나의 다항식 문 제 를 푸 는 것 을 예 로 들 어 함수 f1 () 과 함수 f2 () 두 가지 방법 으로 다항식 을 푸 는 것 입 니 다. 일부 함수 가 걸 리 는 시간 이 매우 작 기 때문에 수치 에서 누가 크 고 누가 작은 지 나타 내기 위해 1e7 번 중복 함수 의 코드 를 이용 하여 중복 횟수 를 나 누 어 함수 의 단일 운행 시간 을 얻 습 니 다.(반복 횟수 는 define MAXK 에서 수정 가능)
c. 구체 적 인 코드 구현

// 
#include
#include
#include
clock_t start,stop;
//clock_t clock()         
double duration;
//           ，     

#define MAXN 10 /*       ，      +1*/ 

#define MAXK 1e7/*            */

double f1(int n,double a[],double x)
{
	int i;
	double p=a[0];
	for(i=1;i<=n;i++)
	  p+=(a[i]*pow(x,i));
	return p;
}

double f2(int n,double a[],double x)
{
	int i;
	double p=a[n];
	for(i=1;i<=n;i++)
	  p=a[i-1]+x*p;
	return p;
}

void computationtime(double start,double stop,int i)
{
	duration = ((double)(stop-start))/CLK_TCK/MAXK;/*           */
	//      
	//               ，    duration  
	printf("ticks%d = %f
",i,(double)(stop - start));
	printf("duration%d = %6.2e
",i,duration);
}

int main()
{
	int i;
	double a[MAXN];/*      */ 
	for( i=0; i<MAXN; i++)a[i]=(double)i;
	
	//              clock()    
	start = clock();//    
	/*MyFunction();//         */ 
	for(i=0;i<MAXK;i++)
	  f1(MAXN-1,a,1.1);
	stop = clock();//    
	computationtime(start,stop,1);
	 
	start = clock();//    
	/*MyFunction();         */ 
	for(i=0;i<MAXK;i++)
	  f2(MAXN-1,a,1.1);
	stop = clock();//    
	computationtime(start,stop,2);
	
	return 0; 
} 
/*
clock():          clock()          。
       clock tick， “    ”。
   CLK_TCK：               
*/

이것 은 출력 결과 입 니 다. 두 알고리즘 사이 의 운행 시간 이 한 개의 수량 급 차이 가 나 는 것 을 볼 수 있 습 니 다. 두 번 째 알고리즘 이 더욱 빠 릅 니 다.

ticks1 = 7301.000000
duration1 = 7.30e-007
ticks2 = 741.000000
duration2 = 7.41e-008

자바 구체 코드 구현

static final int MAX = 100000;
static final String[] arr = new String[MAX];
 
public static void main(String[] args) throws Exception {

	//          
	long t1 = System.currentTimeMillis();
	//    
	
	//          
	long t2 = System.currentTimeMillis();
	//t2-t1       
}