[알고리즘] - 시간복잡도

Reference

다음을 참조하여 작성하였습니다.🙇🏻‍♂️

• 알고리즘위키
• what are algorithms
• visualgo
• yena님

---

알고리즘

알고리즘의 성능을 측정하는 5가지 기준이라고 한다.

1. 입력 : 외부에서 제공되는 자료가 0개 이상 존재한다.
2. 출력 : 적어도 2개 이상의 서로 다른 결과를 내어야 한다. 즉 모든 입력에 하나의 출력- 이 나오면 안 된다.
3. 명확성 : 수행 과정은 명확하고 모호하지 않은 명령어로 구성되어야 한다.
4. 유한성 : 유한 번의 명령어를 수행 후 유한 시간 내에 종료한다.
5. 효율성 : 모든 과정은 명백하게 실행 가능(검증 가능)한 것이어야 한다

시간 복잡도

문제를 해결하는데 걸리는 시간과 입력의 함수 관계 프로그램을 작성할 때에 입력의 크기에 따라서 프로그램이 계산하는 횟수가 크게 달라진다. 입력된 자료의 양과 알고리즘 실행에 걸리는 시간 사이에는 어느 정도의 관계가 있다. 이것을 알고리즘의 시간 복잡도라 한다.

• 메모리 공간을 얼마나 차지하느냐를 계산하는 공간 복잡도라는 개념도 있지만, 저장 기술의 발달로 인해 현재는 시간 복잡도를 우선 고려하는 경우가 많다고 한다.

시간 복잡도를 나타낼 때에는 Big O 표기법을 이용한다.
예를 들어서, 1부터 n까지의 합을 구한다고 할 때, 다음과 같은 두 가지 방법이 있다.

// 방법 1 
int n, res = 0;
for (int i = 1; i <= n;, i++) {
    res += i;
}
System.out.println(res);
// 방법 2
int n, res = 0;
res = n*(n+1)/2;
System.out.println(res);

코드를 살펴보면

• 방법1 : for를 이용해 n번의 연산을 하기 때문에 O(n) 의 시간 복잡도를 가진다.
• 방법2 : n의 크기와 상관 없이 1번의 연산을 하기 때문에 O(1) 의 시간 복잡도를 가진다.

시간 복잡도	설명
O(1)	상수 형태(n의 값에 상관없이 일정한 양의 계산만 함)
O(logn)	로그 형태
O(n)	선형
O(nlogn)	선형로그 형태
O(n2),O(n3),⋯	다차 형태
O(2n)	지수 형태
O(n!)	팩토리얼 형태

맨 위에서부터 시간 복잡도가 낮고 빠르고,
아래로 갈 수록 시간 복잡도가 높고 느려진다.
제한된 시간 안에 올바르게 output을 출력하려면 시간 복잡도를 낮춰야 할 것임을 알 수 있다.