이 C 프로그램의 시간 복잡도를 결정하는 방법

Question

void mystery2 (int n) 
{ 
int i; 
for (i = 1; i <= n; i++) { 
    double x = i; 
    double delta = 1/(double)i; 
    while (x > 0) 
     x -= delta; 
    } 
return 0; 
} 

http://pages.cs.wisc.edu/~vernon/cs367/notes/3.COMPLEXITY.html#application과 같은 추적 테이블을 사용하고 추측하지 않고이 프로그램의 시간 복잡성을 결정하는 방법은 무엇입니까?

Answer 1

각 반복에 대해 처음에는 x=i이 있고 그 다음에 x은 매번 1/i만큼 감소합니다. 따라서 이것은 i/(1/i)==i^2 번 반복됩니다.

따라서 for(i=1;i<n;++i)의 반복마다 내부 부분은 O(i^2)의 복잡성을 갖습니다. i은 1에서 n으로 증가하므로 (1^2+2^2+3^2+...+n^2)을 추가하는 것과 같습니다. 대략 n^3/6입니다. 따라서 그것은 O(n^3)입니다.

---

Outer loop(for)   Inner Loop 
    I=1      1 
    I=2      4 
    I=3      9 
    ...      .. 
    I=N      N^2 
TOTAL_      ~N^3/6 

Answer 2

이 비교적 간단합니다 : 당신은 두 개의 중첩 루프의 각 실행 횟수를 결정해야하고, 함께 복잡성을 고려.

바깥 쪽 루프는 보통 for 루프입니다. n 번 실행합니다.

내부 루프는 조금 더주의가 필요합니다. 1/i을 0으로하거나 음수가 될 때까지 i에서 계속 감안합니다. 루프 while을 반복하여 을 빼는 것이 쉽습니다. x에서. x은 처음에 i으로 설정되었으므로 내부 루프에 걸린 총 시간은 i^2입니다.

따라서, x에 대한 합계는 x 제곱이고, 1과 n 사이입니다.

Wolfram Alpha tells us that the answer to this is n*(n+1)*(2n+1)/6

이 O(n^3)의 복잡도를 갖는다 n^3/3 + n^2/2 +n/6 다항식으로 확장된다.