복잡성 (초급 질문)

Question

이 문장의 복잡성은 얼마나됩니까?

for(int k = 1; k < n; k++) 
    for(int i = 0; i < n-k; i++){ 
     //O(1) operation here 
    } 

설명 감사합니다.

Answer 1

먼저 외부 루프를 수행하면 n-1 번 작업이 수행됩니다. 두 번째로 진행하십시오. n-2 번 ... 모든 것을 추가하면 (n)*(n-1)/2 작업으로 끝납니다.

합계를 보려면 1에서 (n-1), 다음으로 (n-1)에서 1로 작성하고 각 용어를 하나씩 추가하십시오.

1 2 3 ... n-3 n-2 n-1 
n-1 n-2 n-3 ... 3 2 1 
--------------------------- 
    n n n  n n n 

so 2 * sum = (n-1) * n.

복잡성면에서 약 n²입니다.