의사 다항식 복잡 도

전편 의 표기 알고리즘 에서 이 O (K) 의 알고리즘 은 지수 급 복잡 도의 알고리즘 이 라 고 언급 했 는데 사실은 그 문제 자체 에 있어 K 는 고정 적 이 고 입력 이 아니 므 로 복잡 도 라 고 할 수 없다. O (K) 라 는 표현 이 있 는 이 유 는 K 를 입력 으로 하 는 것 이다. 이것 은 입력 의 각도 문 제 를 보 는 것 이 므 로 깊이 연구 할 필요 가 없다.더 간단 한 알고리즘 (python 코드, 입력 n 을 정수 로 설정) 을 고려 하 십시오.
 

def f(n): 
    i = 0 
    while i < n: 
        i += 1 

이 알고리즘 은 임의의 정수 입력 에서 모두 None 로 돌아 갑 니 다. 우리 가 주목 하 는 중점 은 시간 복잡 도 입 니 다. python 의 관련 체제 에 따라 할당 작업 은 포인터 수정 으로 상수 시간 이 완성 되 었 다 고 볼 수 있 습 니 다. 그래서 이 알고리즘 은 n 차 비교 연산 과 플러스 연산 을 실 행 했 습 니 다.
 
python 을 사용 하 는 이 유 는 python 의 정수 와 C 의 정수 유형 이 다 르 기 때문에 자릿수 를 제한 하지 않 습 니 다 (메모리 가 제한 되 어 있 기 때문에 실제 적 으로 제한 이 있 지만 충분 합 니 다). 즉, 정수 의 모든 연산 을 상수 시간 으로 볼 수 없습니다. 숫자 가 매우 클 수 있 고 내부 에 하나의 배열 로 저장 할 수 있 기 때 문 입 니 다.가장 간단 한 예 는 두 개의 숫자 a 와 b 를 더 하면 해 야 할 일 은 그 두 사람의 길이 와 관계 가 있 기 때문에 덧셈 시간 복잡 도 는 lga, lgb 선형 과 관련 이 있다.
 
그러나 이 예 에서 우 리 는 비교 와 가산 연산 이 모두 평균 상수 시간 이라는 것 을 증명 할 수 있다. 만약 에 두 개의 큰 수 를 비교 하면 길 이 를 먼저 보고 긴 것 이 분명 하 다. 만약 에 똑 같이 길 면 이동 한 후에 strcmp 와 유사 한 알고리즘 을 사용한다. 앞의 한 편의 토론 에 따 르 면 strcmp 의 평균 시간 복잡 도 는 O (1) 이다.다른 한편, 위 에서 덧셈 은 숫자의 자리수 선형 과 관련 이 있다 고 말 하지만 만약 에 덧셈 을 하면 연속 적 인 진위 가 발생 할 때 만 연산 시간 이 길이 와 관련 이 있 고 연속 적 인 덧셈 조작 은 매번 상수 시간 (알고리즘 서론 을 참고 한 평면 분석 1 장) 이다.
 
그래서 우 리 는 위의 이 알고리즘 의 복잡 도 는Θ(n) 이 결론 은 틀 리 지 않 았 다. 그러나 이 알고리즘 은 지수 급 복잡 도 이다. 그 이 유 는 입력 규모 가 n 선형 과 관련 된 것 이 아니 라 한 알고리즘 의 입력 규모 에 대해 명확 하고 간단 한 정의 가 있 는데 바로 입력 의 길이 이다.
 
따라서 입력 을 두 가지 로 나 눌 수 있다. 데이터 입력 과 수치 입력 은 2 진법 을 표현 형식 으로 한다 고 가정 하면 하나의 수치 N 에 있어 그의 입력 규 모 는 lgN 이다. 물론 base 가 2 이상 의 진법 을 사용 하면 입력 길이 가 짧 지만 점진 적 인 의미 에서 볼 때 똑 같 기 때문이다. x 와 y 가 모두 1 이상 일 때Θ(log(N,x))=Θ(log (N, y)) 이 므 로 바 이 너 리 로 문 제 를 설명 할 수 있 습 니 다.시간 복잡 도Θ(T (N)) 는 입력 규모 가 원래 의 k 배로 변 할 때 알고리즘 운행 시간 이 원래 의 T (k) 배 라 는 단계 로 증가 할 것 이 라 고 볼 수 있 습 니 다. 따라서 위의 알고리즘 에 있어 입력 규모 가 원래 의 k 배로 증가 하면 입력 한 수치 n 은 원래 의 k 제곱 이 되 기 때문에 n 은 수치 입력 이기 때 문 입 니 다.Θ(n) 입력 규모 N 의 표시 로 바 꾸 면Θ(2 ^ N) 은 지수 등급 의 복잡 도 입 니 다.
 
데이터 입력 에 대해 잘 이해 할 수 있 습 니 다. 모든 데이터 자체 의 수치 길 이 를 고려 하지 않 으 면 데이터 입력 의 규 모 는 바로 그 수량 입 니 다.
 
만약 에 하나의 알고리즘 이 수치 입력 이 있 고 그 시간 복잡 도 는 입력 수치 (입력 규모 가 아 닌) 의 다항식 이 라 고 할 수 있다 면 위의 토론 에 따라 실제 적 으로 지수 시간의 알고리즘 이 어야 한다. 그러나 이런 상황 은 데이터 입력 규모 의 지수 급 복잡 도와 약간 다 르 기 때문에 일반적으로 직관 적 으로 입력 수치 로 복잡 도 를 나타 내 는 습관 이 있다.이런 다항식 (수치의 다항식) 처럼 보이 지만 실제 대표 알고리즘 은 지수 급 (입력 규 모 를 지수 로 하 는) 의 복잡 도 를 위 다항식 복잡 도 라 고 부른다.
 
많은 알고리즘 은 위 다항식 의 복잡 도 를 가지 고 있다. 예 를 들 어 2 부터 시험 적 으로 제거 하 는 방식 으로 하나의 정수 N 이 소수 인지 아 닌 지 를 판단 하려 면 N ^ (1 / 2) 차 나눗셈 을 해 야 한다. 매번 나눗셈 의 시간 은 lgN 과 관련 이 있 고 얼핏 보면 이 다항식 도 높 지 않 지만 N 은 입력 모델 에 따라 빠르게 증가 하기 때문에 지수 시간의 알고리즘 으로 소 수 를 판단 하 는 것 이 매우 비효 율 적 이다.
 
P. S. 이미 여러 가지 시간 으로 소 수 를 판정 하 는 알고리즘 이 있다 고 들 었 습 니 다. 시간 복잡 도 는 O (lgN) ^ 6 에서 O (lgN) ^ 12) 입 니 다. 물론 여 기 는 N 이 입력 규모 의 선형 성장 에 따라 지수 급 으로 증가 하기 때문에 입력 규모 M = lgN 을 설정 하면 쉽게 이해 할 수 있 습 니 다.
 
동적 계획 을 이용 하여 0 - 1 가방 문 제 는 O (NW) 알고리즘 이 있 을 수 있 습 니 다. W 는 수치 입력 이기 때문에 이 알고리즘 은 위 다항식 시간 입 니 다.사실 계산 이론 에서 의 방법 을 통 해 0 - 1 가방 문 제 는 NPC 문제 임 을 증명 할 수 있다. 위 다항식 을 이해 하지 못 하면 왜 O (NW) 알고리즘 이 있 는 지 이해 하기 어렵다. NPC 의 것 이다.
 
의사 다항식 시간 복잡 도 알고리즘 이 존재 하 는 NPC 문 제 는 일반적으로 약 한 NPC 문제 라 고 부 르 는데, 반대로 강 한 NPC 문제 이 고, 약 한 NPC 문 제 는 P 에 더욱 가 까 운 것 같 아서 관련 문제 에 대한 연구 에서 사람들 에 게 더욱 큰 흥 미 를 끌 곤 한다.