알고리즘 성장 순서 코드

온라인 과정에 참여 중이며 다음 질문에 답했습니다. 다음 코드 단편의 최악의 실행 시간이 N의 함수로 커지는 순서는? 알고리즘 성장 순서 코드

int sum = 0; 
for (int i = 1; i <= N*N; i++) 
    for (int j = 1; j <= i; j++) 
     for (int k = 1; k <= j; k++) 
      sum++;

가 나는 N^4의 순서입니다하지만이 대답은 잘못된 것 같다 생각했다. 설명해 주시겠습니까?

출처

2014-03-05 Ankit Kumar

내부 루프를 한 번 실행하면 sum이 정확히 j 번 증가합니다.

가운데 루프를 실행하면 내부 루프가 정확히 i 번이고 j의 값이 1과 i (포함 포함) 사이입니다. 따라서 sum 정확히 1+2+3+...i 번을 증가 시키며 이는 잘 알려진 "삼각 수"공식에 의해 i.(i+1)/2입니다.

외부 루프는 정확히 N^2 시간 1 및 M (포함) 사이에 i의 값을, (우리가 M로 나타 내기하자) 중간 루프를 호출합니다. 따라서 sum이 정확히 1+3+6+...M.(M+1)/2 번 증가합니다. 마찬가지로, 이것은 잘 알려지지 않은 "사면체 수"공식 (http://en.wikipedia.org/wiki/Tetrahedral_number)에 의해 M.(M+1).(M+2)/6입니다.

결국, sum의 최종 값은 N^2.(N^2+1).(N^2+2)/6입니다.

점근 관점에서 생각 내부 루프 O(j) 중간 온 (합계하여) O(i^2) 외측 (합계하여) 하나 O(M^3), 즉 O(N^6)이다.

또한 n^k의 합계가 O(N^(k+1)) (http://en.wikipedia.org/wiki/Faulhaber%27s_formula) 인 Faulhaber의 수식을 참조하십시오.

출처

2014-03-05 09:32:41

n = N^2이라고합시다. 그런 다음 루프는 k <= i <= j 때마다 실행됩니다. 약 n^3/6 번입니다. 따라서, 런타임은 O(n^3)= O(N^6)

설명 : 잠시 무시 k==i 또는 j==i 또는 j==k이 우리가 1 6 별개의 트리플에서 걸릴 경우 :이

(a1,a2,a3) 
(a1,a3,a2) 
(a2,a1,a3) 
(a2,a3,a1) 
(a3,a2,a1) 
(a3,a1,a2)

점수, n^3 세입니다. 6 명의 트리플 중 단 한 명만 주문에 복종합니다.

출처

2014-03-05 09:06:08

O(N^6)입니다. 모든 루프가 단지 N이라는 주문을 복잡성에 추가한다는 것은 사실이 아닙니다. 다음의 예를 고려하면 :

int sum = 0; 
for (int i = 1; i <= M; i++) 
    for (int j = 1; j <= i; j++) 
     for (int k = 1; k <= j; k++) 
      sum++;

당신은 그것을 쉽게하기 위해 O(M^3)이다 알아낼 수 있어야합니다, 그래서 당신은 M=N^2을 교체하는 경우, 당신은 대답을 얻을 것이다. 중요한 점은 모든 내부 루프는 O(N^2)이며이 경우는 O(N)이 아님을 알 수 있습니다.

출처

2014-03-05 09:07:51 unsym

주어진 내부 루프 (k)의 루프는 j에 비례하는 시간을 갖지만 j = 1에서 j = i까지 각각 하나씩 수행해야하며 그 합은 1 + 2 + ...입니다. + 나는 i^2처럼 자랍니다. 그래서 어떤 이 주어진다면 우리는 O (i^2)의 실행 시간을 가지고 있습니다. 물론 i = 1 ~ i = N^2를 처리해야합니다. i = 1에서 N^2까지의 i^2의 합계 happens to grow like N^6.

출처

2014-03-05 09:23:35

알고리즘 성장 순서 코드

답변

관련 문제