큐브의 합계를 계산하기위한 프로그램에서 루프 불변성 찾기?

Question

트리플 파워 합계에서 불변량이 100 %인지 확실하지 않습니다.

참고 : n은 항상 음수가 아닌 값입니다.

의사 코드는 :

triplePower(n) 
    i=0 
    tot=0 
    while i <= n LI1 
     j = 0 
     while j < i LI2 
      k = 0 
      while k < i LI3 
       tot = tot + i 
       k++ 
      j++ 
     i++ 

나는 그 혼란을 알고 훨씬 쉬운 방법으로 수행 할 수 있지만, 이것은 내가 (주로 알고리즘 분석 연습) 할 것으로 예상하고있는 무슨이다.

나는 3 개의 루프 불변량을 생각해 내야한다. LI1, LI2 및 LI3.
나는 불변량이 tot = (i^2 (i + 1)^2)/4와 어떤 관계가 있다고 생각하고있다. (합계 큐브 0에서 i까지의 방정식)
나는 ' LI2 또는 LI3을 위해 무엇을해야 할지를 알고 있습니다. LI2의 루프는 i^3을 만들고 LI3은 i^2를 만듭니다. 그러나 루프 불변량으로 정의하는 방법을 완전히 모르겠습니다.

각각의 while 루프 본문에 3 개의 별도 총 변수가 있으면 invariant를 쉽게 정의 할 수 있습니까?

도움을 주셔서 감사합니다.

또한이 함수의 성장 순서는 다음과 같습니다. Θ (n^3)?

Answer 1

귀하의 알고리즘 (난 당신이 C 언어 구문에 익숙해 희망)과 같이 단순화 할 수있다

:

tot = 0; 
for (i = 0 ; i <= n ; i ++) 
    for (j = 0 ; j < i ; j ++) 
     for (k = 0 ; k < i ; k ++) 
      tot = tot + i; 

를 그리고, 당신은 시그마 표기법으로 번역 할 수 있습니다 :

Answer 2

점진적으로 합계를 계산하는 이와 같은 루프에 직면했을 때, 지금까지 계산 한 총합이 생각한 합계의 첫 번째 부분과 같은지 찾아 보는 것이 좋은 불변 조건입니다. 이 경우 첫 번째 n 개의 양의 완벽한 큐브의 합계를 계산하고 한 번에 하나씩 큐브를 추가하여 계산할 수 있습니다. 따라서 하나의 가능한 불변

TOT = 합 (j 제가 0에서 진행) ³

또한 J 있다는 것, i와 N의 관계는 무엇입니까? 음, 우리는 아마도 내가 ≤ n + 1을 가져야합니다. 왜 n + 1? 왜냐하면 마지막 반복에서, i = n 일 때, 우리는 여전히 어쨌든 i를 증가시키기 때문입니다. 이 두 불변량을 사용하면이 루프가 올바른 값을 계산한다는 것을 증명할 수 있습니다.

런타임의 경우 매우 쉽게 계산할 수 있습니다. 첫째, 각 반복마다 얼마나 많은 작업이 수행되고 있습니까? O (1)? 에)? O (n)? 그렇다면 루프 반복 횟수는 얼마나됩니까? O (1)? 에)? O (n)? 이 두 용어의 결과는 당신에게 답을 줄 것입니다.

희망이 도움이됩니다.