[C++] 백준 11단계 - 24265번 문제 (알고리즘의 수행 시간 4)

문제설명

 

소스코드

#include <iostream>
using namespace std;
int main()
{
    unsigned long long n;
    cin >> n;
    cout << (n * (n-1) ) / 2 << endl << 2 <<endl;
}

 

풀이

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;
}

• 수행 횟수는 1부터 n-1까지의 수를 모두 더한 것과 같다.
• 시간복잡도는 O(N²)이다.
• 즉, 수행 횟수는 n * (n-1) )/ 2이고, 최고차항의 차수는 2이다.

가우스 덧셈
a 에서  b까지의 숫자를 더한 합을 구하려면
처음 숫자와, 마지막 숫자를 더한 합 = ( a + b )
더할 숫자의 개수 총합의 1/2 = ( b - a + 1) * 1/2
= ( a + b ) *  ( b - a + 1) * 1/2 

 

2023.01.15 - [자료구조 & 알고리즘] - 알고리즘 시간 복잡도, 공간 복잡도(Time Complexity, Space Complexity) + Big-O

알고리즘 시간 복잡도, 공간 복잡도(Time Complexity, Space Complexity) + Big-O