알고리즘 복잡도(complexity)
복잡도란
알고리즘의 성능을 나타내는 척도
크게 시간 복잡도, 공간 복잡도로 나눌 수 있다.
1.시간 복잡도
- 특정한 크기의 입력에 대해 알고리즘이 얼마나 오래 걸리는지를 의미한다.
- 알고리즘을 위해 필요한 연산의 횟수
- 복잡도를 표현하기 위해 빅오 표기법을 사용한다.
- 최악의 경우에 대한 연산 횟수가 가장 중요하다.
- N의 범위에 따라 시간 복잡도를 계산하고 사용할 수 있는 알고리즘을 선택하는 방법도 있다.
※ 빅오 표기법 (O, big-O)
빅오란 입력값이 무한대로 향할때 함수의 상한을 설명하는 수학적 표기 방법이다.
빅오는 점근적 실행 시간을 표기할 때 가장 널리 쓰이는 수학적 표기 방법이여, 여기서 점근적 실행 시간이란 간단하게 N이라는 입력값이 무한대로 커질때의 실행 시간의 추이를 의미한다.
따라서 충분히 큰 입력값에서의 알고리즘의 효율성에 따라 수행 시간이 크게 차이가 날 수 있다.
- 2^n을 포함하는 식은 n^100이든 n^10000이든 어떤 상수의 지수를 가지더라도 n의 크기가 무진장 커지면 2^n이 항상 더 커지게 되므로 다항 시간에 포함되지 않습니다. 후자는 특별히 지수 시간(exponential time)이라고 부릅니다.
2.공간 복잡도
특정한 크기의 입력에 대해 알고리즘이 얼마나 많은 메모리를 차지하는지를 의미한다.
알고리즘을 위해 필요한 메모리의 양
N, NP
결정문제 :
답이 YES 아니면 NO로 반환되는 문제를 결정 문제라고 한다.
P 문제 : 결정 문제들 중 쉽게 풀리는 것을 모아 놓은 집합이다. 어떤 결정 문제가 주어졌을 때, 다항식(Polynomial) 시간 이내에 그 문제의 답을 계산해낼 수 있는 알고리즘이 존재한다면, 그 문제는 P 문제에 해당된다.
NP 문제 : 형식적으로는, 문제를 푸는 각 단계에서 여러 가지의 가능성을 동시에 고려할 수 있는 비결정적 알고리즘(non-deterministic algorithm)으로, 다항시간 내에 문제를 해결할 수 있는 문제라고 정의한다.
밀레니엄 문제 N-NP
- 모든 P는 NP에 속한다 그러면 반대로 NP는 P에 속하는가 ?? 즉, 검산을 해보기 전 쉬운문제는 풀기도 쉬울까??
NP라는 어려운 문제가 있는데 쉬운 문제로 풀 수 있는 열쇠로 P라는 쉬운문제가 된다. '🔑이런 열쇠가 존재 하는가?'
열쇠가 존재한다는 것이 증명이 되면 찾고 노력하는 것이 의미있는 작업이 되지만 반대로 존 재하지 않다는 것이 증명되면 찾을 필요가 없다.
N-NP에 대한 이해를 쉽게!!
https://www.youtube.com/watch?v=QkSW24mUxN8
현재 많은 학자들은 P와 NP가 다르다고 생각합니다. 하지만 그 누구도 이를 엄밀히 증명하지는 못한 상황입니다.
출처: https://gazelle-and-cs.tistory.com/64
출처: 나무위키!
도시를 순회하는 외판원
각 변에 가중치가 주어진 완전 그래프(weighted complete graph)에서 가장 작은 가중치를 가지는 해밀턴 순환을 구하라
+++ 해밀턴 경로란 ? 모든 꼭짓점을 한 번씩 지나는 경로
도시를 나열하는 방법으로는 (n-1)! BUT 수가 너무 크다 !
ex) 12! = 479,001,600(사억칠천....)
- DP 메모제이션 ( 중복 경로 제거 )
(16-1)!의 모든 경로를 조사하지 않고 중복된 경로를 제거하는 dp 메모제이션기법을 사용하면 된다. 동일한 하위 문제의 반복을 막아줌으로써 더 높은 효율로 연산이 이루어지게 해준다. 중복되는 경로의 조사를 제거해주는 것이다.
- 비트마스킹
비트마스킹을 사용하면 bit연산이기 때문에 다른 자료구조(boolean배열)을 사용하는 것보다 훨씬 빠르게 동작되고 코드도 간결해진다. 그리고 가장 큰 장점은 N이 16개인 경우 2^16가지의 경우를 16bit로 표현이 가능하다. (ex. 16개의 지점 중 1,3,4,5번 지점 방문 -> 0000 0000 0001 1101)
→ 정리하면 TSP(외판원 순회)는 최단 순환 경로를 탐색해야하는데 1) N! 의 중복 경로를 제거해주는 DP 메모제이션 기법을 사용한다. 그래도 2^N의 모든 경우의 수를 표현해야 하기 때문에 그만큼의 공간복잡도가 필요하다. 2) 메모리 사용량도 줄이고 성능 향상을 위해서 2^N의 경우의 수를 Nbit로 표현할 수 있는 비트마스킹으로 사용한다.
→ 최적화 접근 방식으로 DP 메모이제이션과 비트마스킹을 사용하여 해당 설명은 올라가야 할 계단의 수를 100 → 1로 줄여주는 설계 방법이라고 보면 된다.
출처 : https://loosie.tistory.com/272
백준 풀이내용 : https://loosie.tistory.com/271
정렬에 대한 재밌는 영상
https://www.youtube.com/watch?v=EdIKIf9mHk0&list=PLOmdoKois7_FK-ySGwHBkltzB11snW7KQ
