(매일 BOJ) C++ 24264번 알고리즘 수업 - 알고리즘의 수행 시간 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;
}

 

이 문제의 MenOfPassion 함수에서는 1부터 N까지 i 의 값이 커지고 각 i 값에 대해 j가 1부터 N까지 값이 커지는 동작을 반복하고 있다. 따라서 N의 값에 따라 연산량이 N^2 만큼씩 커지는 것을 볼 수 있기에 이 함수의 시간복잡도는 O(N^2) 가 되어 첫째 줄 출력은 N^2, 둘째 줄 출력은 2가 된다.

 

시간복잡도에 대한 자세한 내용은 아래 글을 읽어보자

https://hanamon.kr/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-time-complexity-%EC%8B%9C%EA%B0%84-%EB%B3%B5%EC%9E%A1%EB%8F%84/

[알고리즘] Time Complexity (시간 복잡도) - 하나몬

작성코드

# include <bits/stdc++.h>
using namespace std;


int main(void){
    ios::sync_with_stdio(0); cin.tie(0);
    long long N;
    cin >> N;
    cout << N*N << '\n' << 2;
}