트리플 루프를위한 복잡도

for(I = 0; I < n; I++) 
for(j = I; j < n; j++) 
    for(k = I; k < n; k++) 
    statement;

외부 루프는 n 번 실행됩니다. 두 번째 루프는 (n - I) 회 = n (n - 1)/2 회 실행됩니다. 세 번째 루프는 (n-1) 회 = n (n-1)/2 회 실행됩니다. 그래서 문은 (n (n-1)/2)^2 번 실행됩니다. 이것이 맞습니까?트리플 루프를위한 복잡도

출처

2013-12-20 Mustehssun Iqbal

이 조각은 "(n - I) 회 = n (n-1 회)/2 회"라는 잘못된 구문입니다. 수학적으로 올바른 방식으로 표현하려고 시도하십시오. 이것은 도움이 될 수 있습니다. – anatolyg

"(n (n-1)/2)^2 번 실행됩니다. 정확합니까?" 그것은 틀리게 본다. n ((n-1)/2)^2가 더 가깝습니다. 트리플 루프는 O (n^3)이기 때문에, – OmnipotentEntity

당신이 적합한 지 여부를 확인하기 위해 다음과 같이 셀 수 여부

int Cnt = 1; // initialization 
for(I = 0; I < n; I++) 
for(j = I; j < n; j++) 
    for(k = I; k < n; k++, Cnt++) 
    printf ("This is the %dth time\n", Cnt);

출처

2013-12-20 19:29:09

그것은 O (N^3)입니다 - n은에 간다

O(n^3+AnyConst*n^2+AnyOtherConst*n+ThirdConst)=O(n^3)

O 표기법은 점근 거동을 추정하기 때문에 따라서 무한대로 성장하는 구성 요소 만 빠르게 성장합니다.

출처

2013-12-20 19:35:27

트리플 루프를위한 복잡도

답변

관련 문제