면책 조항:나는 현재 학생에서 데이터 과학 bootcamp,그리고 우리는 하지 않으로 받은 알고리즘은 아직입니다. 이것은 내 자신의 시간에 대한 몇 가지 연구를하면서 우연히 발견 한 것입니다. 흥미로운 주제라고 생각했습니다. 확실히 프로가 아니거나 아직 알고리즘 경험이 전혀 없습니다. 바라건대 나는 곧있을 것이다.
단지 나의 기본적인 이해에서,나는이 용어들이 모두 알고리즘에 대한 Big-o 표기법을 다루고 있다고 믿는다. 바라건대,나는 이것을 매우 이해할 수있는 방식으로 다룰 수있다.,
간단한 요약,Big-O 의 측정이 어떻게 빨리 알고리즘 실행 또는 문제가 해결(주는것은 상한이 얼마나 오래 실행 시간).
P,NP,NP-Hard 및 NP-Complete 는 모든 문제가 해당되거나 분류되는 클래스입니다.
P(다항식)문제가
P 문제를 참조하여 문제의 알고리즘을 다항식 시간을 해결하기 위해,또는 어디 Big-O 은 다항식으로(즉,O(1),O(n),O(n2),etc.). 이것들은 해결하기가’쉬운’것으로 간주 될 문제이므로 일반적으로 엄청난 실행 시간이 없습니다.,
NP(비결정 다항식)문제가
NP 문제가 좀 더 열심히 나를 위해 이해하지만 제 생각에 이것은 그들이 있습니다. NP 문제를 해결하는 측면에서 런타임은 다항식이 아닙니다. 그것은 O(n!)또는 훨씬 더 큰 것. 그러나이 클래스의 문제는 특정 솔루션을 제공 할 수 있으며 솔루션을 검사하면 다항식 런타임을 갖게됩니다. 이것을 조금 더 잘 이해하는 데 도움이 된 예는 스도쿠 게임이었습니다.,
를 해결하기 위해 이 전체 퍼즐,알고리즘을 각각 확인 3×3 매트릭스를 볼 수있는 숫자가 없는,다음 각각의 행에는,다음 각 열,그리고 다음 없는지 확인하십시오의 반복이 어떤 자리에서 0-9. 누락 된 자릿수가 각 행,열 및 행렬에서 일치하지 않기 때문에 더 복잡해집니다(즉,왼쪽 위 행렬은 4 자리 누락,오른쪽 위 행렬은 8 자리 누락). 이 문제를 해결하면 다항식 런타임이 없습니다., 그러나,당신을 먹이 퍼즐과 함께 가능한 해결책,그것은 많은 보다 적게 복잡한 확인이 있는 경우에 반복 행,열 및 행렬. 이것은 다항식 런타임을 갖는 간단한 검사입니다.
본질적으로,NP 클래스에 문제가 있지 않는 다항식-실행를 해결하기 위해 시간,하지만 다항식-실행 시간을 확인하는 솔루션(해결하기 어려운,쉽게 확인어).
감소
예제를 사용하는 것 외에는 실제로 설명 할 수 없으므로 A 와 B 의 두 가지 문제가 있으며 문제 B 가 P 클래스 문제라는 것을 알고 있습니다., 문제 A 가 감소되거나 문제 B 로 변환 될 수 있으며이 감소에 다항식 시간이 걸리면 A 는 또한 P 클래스 문제라고 말할 수 있습니다(A 는 b 로 환원 가능).
이 개념은 문제의 다른 두 클래스에 대해 이해하는 것이 중요합니다.
NP-Hard Problems
문제를 NP-Hard 로 분류하면 문제를 해결하기위한 알고리즘을 변환하여 모든 NP 문제를 해결할 수 있습니다. 그런 다음 우리는이 문제가 적어도 NP 문제만큼 어렵다고 말할 수 있지만 훨씬 더 어렵거나 복잡 할 수 있습니다.,
NP-Complete Problems
NP-Complete problems 는 NP 와 NP-Hard 클래스 모두에 사는 문제입니다. 이것은 NP-Complete 문제가 다항식 시간에서 검증 될 수 있고 모든 NP 문제가 다항식 시간에서이 문제로 축소 될 수 있음을 의미합니다.
아래는 다른 클래스 공간의 벤 다이어그램입니다.,
희망이 삭제할 수 있는 것이 주제입니다. 분명히,나는 매우 제한된 지식을 가지고있다. 나는 단지 이것이 이야기하기에 흥미 롭다고 생각했고,높은 수준에서도 이것은 꽤 혼란스러운 것처럼 보입니다.