프롤로그 프로그램의 복잡성?

Question

프롤로그에서 문제는 역 추적을 사용하여 해결됩니다. 명령형 패러다임보다는 (C, PHP 또는 Python 에서처럼) 선언적 패러다임입니다. 이런 종류의 언어에서는 복잡성에 대해 생각해 볼 가치가 있습니까?

this question에있는 누군가가 지적한 것처럼 자연스러운 방식으로 문제가 O (N^2) 인 것 같습니다.

Answer 1

모든 언어에서 복잡성을 분석하는 것이 중요합니다. 프롤로그 또는 명령형 언어 여야합니다. 그러나 나는 당신에게 프롤로그 프로그램을 가속화하기위한 몇 가지 요령을 줄 수있다.

1. 언제나 프로그램을 꼬리 재귀 적으로 만들도록 노력하라. 이렇게하면 프로그램에 스택이 부족한 지 확인할 수 있습니다.
2. 추가 답변이 필요 없다는 것을 알고있는 프로그램에서 잘라 내기 및 실패를 사용해보십시오.
3. 누적기를 사용해보십시오.
4. CLPFD를 확인하면 검색 공간을 대폭 줄여 프로그램 속도를 향상시키는 데 도움이됩니다. 본질적으로 프로그램이 나쁜 선택을 제거하기 전에 프로그램에서 시간을 되돌리고 시간을 낭비 할 수 있습니다.
5. 항상 가장 좋은 결과 규칙을 작성하십시오. (이 문제는 실제로 문제에 달려 있지만 일반적으로 가장 좋은 경우가 우선입니다.)

Answer 2

다른 언어와 마찬가지로 Prolog 프로그램의 복잡성을 명확하게 분석 할 수 있습니다. 당신이 링크 한 그 특별한 문제는 O (n^2) 일 것입니다. 그러나 모든 프롤로그 프로그램이 이러한 복잡성을 가지고있는 것은 아닙니다. 예를 들어, Prolog에서 SAT 솔버를 쉽게 작성할 수 있으며 그 문제는 NP-Complete입니다.

Answer 3

전적으로 문제에 달려 있습니다.

내가 말할 수있는 한 숫자의 합계는 O (N)입니다.

유일한 동작은 추가 ("is")와 재귀 호출이며 둘 다 각각 값 1이어야합니다. 그것들은 모두 목록에서 한 항목에 대해 ~ 한 번 수행되므로 총 작업은 ~ 2N이어야합니다 (O (N)).