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

24264번 : 알고리즘 수업 - 알고리즘의 수행 시간 3

문제

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

• 기존 문제와 똑같다
• for문안에 for문이 존재함 즉 , 수행시간은 n^2 이고, 최고 차수는 2가 됨.

시간 복잡도 : O(n^2)

import java.util.Scanner;

public class Algorithm_3 {
    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        long n = sc.nextInt();

        System.out.println(n*n);
        System.out.println(2);

        sc.close();



    }
}

• 첫째 줄에 입력의 크기 첫째 줄에 입력의 크기 n(1 ≤ n ≤ 500,000)이 주어진다.
• 해당 크기는 n*n을 수행할 때, int를 사용하면 overflow가 발생할 수 있기 때문에 long을 사용함