알고리즘 수업 - 알고리즘의 수행 시간 4

알고리즘 수업 - 알고리즘의 수행 시간 4

문제

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

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Algorithm_4 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        long n = Long.parseLong(br.readLine());

        System.out.println((n * (n - 1)) / 2);
        System.out.println(2);

        br.close();

    }
}

• n이 7이라고 가정할 때 첫 번째 for 문은 1부터 6까지 반복함.
• 두 번째 for 문에서는 i가 1일 경우 j는 2부터 7까지 6번,
• 2일 경우 j는 3부터 7까지 5번

....이런식으로 1부터 n-1까지의 합이 됨.

가우스의 덧셈 공식을 활용하여 알고리즘을 해결할 수 있음 1부터 n-1 까지의 합은

(n * (n-1)) / 2

• 또, 시간복잡도는 O(n^2) 최고 차수는 2임