P 와 NP 세부 내용
·
IT기술 관련/A.I 인공지능
✅ P 클래스 (Polynomial time)● 의미:입력 크기에 대해 다항식 시간 안에 '해결 가능한 문제'즉, 문제를 효율적으로 풀 수 있는 알고리즘이 존재합니다.● 시간 복잡도 예시:O(n)O(n)O(n), O(n2)O(n^2)O(n2), O(n3)O(n^3)O(n3) 등: 입력 크기 nnn이 커져도 어느 정도 현실적인 시간 안에 끝남● 예시:문제설명정렬(Sorting)숫자 리스트를 오름차순 정렬 (예: 병합정렬, 퀵정렬 등 → O(nlogn)O(n \log n)O(nlogn))최대공약수(GCD)두 정수의 공통된 가장 큰 약수 구하기 (유클리드 알고리즘 → O(logn)O(\log n)O(logn))그래프에서 최단 거리 찾기다익스트라 알고리즘 → O(V2)O(V^2)O(V2) 또는 O(E+Vlo..