중첩 루프의 복잡성 (반복 관계)

Question

Algorithm-1 (A:array[p..q] of integer) 
    sum, max: integer 
    sum = max = 0 
    for i = p to q 
     sum = 0 
     for j = i to q 
      sum = sum + A[j] 
      if sum > max then 
       max = sum 
    return max 

중첩 루프는 몇 번 실행됩니까?

첫 번째 for 루프의 복잡도는 O(n)이며 알고리즘의 전체 복잡도는 O(n^2)입니다. 그러나, 반복 관계를 통해이를 증명하기 위해서는 내부 루프의 정확한 실행 횟수가 필요합니다.

Answer 1

를 호출?

귀하의 경우 n = q-p+1이므로 (q-p+1)(q-p+2)/2이됩니다.

이 문제를 해결하기 위해 내가이 권한을 가지고 있다면 - (q^2-qp+2q-pq+p^2-2p+q-p+2)/2 = (q^2+p^2-2qp+3q-3p+2)/2이됩니다.

Answer 2

아마 당신이 찾고 있던 대답이 아닙니다. 사실, 내부 루프는 O (n)이고 전체 프로그램은 O (n^2) 복잡성을가집니다. 그냥 카운터를 던져서 내부 루프에서 증가시킵니다. 그게 당신에게 정확한 사형 집행 건수를 줄 것입니다. 당신이 정확한 숫자를 원하는 경우

Answer 3

, 내부 루프는이 n(n+1)/2 같다, 그냥 Sum(i = 1 -> n, i)하지 않을까요 (n + n-1+ ...1) = n(n+1)/2 ~= O(n^2) 여기 n = q-p

Answer 4

내부 루프는 Q-I + 1 번 실행의 갯수가

\ 합 {I = P}^{Q} (Q-I + 1) = \ 합 {K이다 = 1 실행 (n + 1)/2

여기서 n = q-p + 1이다.