[알고리즘 문제 풀이]백준 24267번 알고리즘 수업

다음 의사코드의 수행 횟수와 시간 복잡도를 출력해야 한다.

MenOfPassion(A[], n) {
    sum <- 0;
    for i <- 1 to n - 2
        for j <- i + 1 to n - 1
            for k <- j + 1 to n
                sum <- sum + A[i] × A[j] × A[k]; # 코드1
    return sum;
}

 

이 의사코드의 수행 횟수는 다음과 같다.

$$\sum _{i=1}^{n-2}\sum _{j=i+1}^{n-1}\sum _{k=j+1}^n 1 = \sum _{i=1}^{n-2}\sum _{j=i+1}^{n-1}(n-j)\\ =\sum _{i=1}^{n-2}\frac{n^2+(-2i-1)n+i^2+i}{2}\\ =\frac{(n-2)(n-1)n}{6}$$

시간 복잡도는 $\mathcal{O}(n^3)$이다.