0
크기가 n 인 입력에 대한 다항식 단계 수를 완료하는 알고리즘 (예 : P(n)=2n^2+4n+3)이 있다고합시다. 이 알고리듬에 대한 점근 적 경계.Big-Theta 표기의 일반화가 맞습니까?
알고리즘의 Big-Theta 표기법이 다항식 인 P(n)의 차수에 따라 n 인 것은 사실입니까? 아니면 사실이 아닌 경우도 있습니까?
A
답변
1
다항식 시간 알고리즘의 복잡성은 O (N K), 0 < k ≤ ∞ 의해 제한된다. 모든 알고리즘이 다항식 시간 복잡성을 갖는 것은 아닙니다. 하위 다항식 복잡도를 갖는 많은 알고리즘이 있습니다. 예 O (K) (상수 복잡도) O (K √n) (K n 번째의 루트 1 ≤ k ≤ ∞) O (로그 n), O (로그 로그 N 포함) 등이 있습니다. 수퍼 다항식 시간 복잡도를 갖는 알고리즘도 있습니다. 이러한 복잡성의 예로는 O가 1 < k ≤ ∞, O (N K)이다 (N!) 등
이 세타 (N 로그()) 또는 세타 (2 고려하지 않는다^n) 또는 Theta (n!) 등 –
예, 다항식에 해당합니다. (물론 모든 함수가 다항식은 아닙니다.) 정의로부터 증명하는 것은 좋은 연습입니다. – Nemo