1주차 (개념)

∙ 시간복잡도 

입력크기에 대해 어떠한 알고리즘이 실행되는데 걸리는 시간이며 주요로직의 반복횟수를 중점으로 측정

 

∙ 빅오표기법

복잡도에 가장 영향을 많이 끼치는 항의 상수인자를 빼고 나머지 항을 없애서 복잡도를 나타내는 표기법

 

// 시간 복잡도는 2분의1 의 n제곱 - n 이다.
// 빅오표기법으로는 n의 제곱이다.

#include <iostream>

using namespace std;

int n;
int main()
{
    cin >> n;
    int a = 0;
    for (int i = 0; i < n; i++){
        for (int j = 0; j < i; j++){
            a += i + j;
        }
    }
    cout << a << '\n';
}

 

∙ 공간복잡도

입력크기에 대해 어떠한 알고리즘이 실행되는데 필요한 메모리 공간의 양

- 최대 범위 : 대부분은 문제의 최대 범위를 기반으로 배열을 미리 만듬 -> N의 최대 범위가 1000000이면, int a[1000000]; 으로 선언

 

∙ 누적합 

요소들의 누적된 합의 의미로 어떠한 배열을 기반으로 앞에서 부터 요소들의 누적된 합을 저장해 새로이 배열을 만들어서 이를 활용