다항식 시간 및 지수 시간

다항식 시간 및 지수 시간

---

누군가 다항식 시간, 비 다항식 시간 및 지수 시간 알고리즘의 차이점을 설명 할 수 있습니까?

예를 들어, 알고리즘이 O (n ^ 2) 시간이 걸린다면 어떤 범주에 속합니까?

---

이것을 확인하십시오 .

지수는 다항식보다 나쁩니다.

O (n ^ 2)는 다항식 (지수가 2와 같은 특수한 경우)의 유형이며 지수보다 나은 2 차 범주에 속합니다.

지수는 다항식보다 훨씬 나쁩니다. 기능이 어떻게 성장하는지보세요

n    = 10    |     100   |      1000

n^2  = 100   |   10000   |   1000000 

k^n  = k^10  |   k^100   |    k^1000

k가 1.1과 같은 것보다 작지 않으면 k ^ 1000은 매우 큽니다. 마찬가지로, 우주의 모든 입자와 같은 것은이를 수행하기 위해 수조 수십억 년 동안 초당 1,000 억억 작업을 수행해야합니다.

나는 그것을 계산하지 않았지만 그것은 크다.

---

다음은 알고리즘을 분석하는 동안 몇 가지 일반적인 Big-O 함수입니다.

• O ( 1 )-일정한 시간
• O ( log (n) )-로그 시간
• O ( (log (n)) ^c )-다대수 시간
• O ( n )-선형 시간
• O ( n ² )-2 차 시간
• O ( n ^c )-다항식 시간
• O ( c ⁿ )-지수 시간
• O ( n! )-계승 시간

(n = 입력 크기, c = 일부 상수)

다음은 일부 기능의 Big-O 복잡성을 나타내는 모델 그래프입니다.

건배 :-)

그래프 크레딧 http://bigocheatsheet.com/

---

O(n^2) is polynomial time. The polynomial is f(n) = n^2. On the other hand, O(2^n) is exponential time, where the exponential function implied is f(n) = 2^n. The difference is whether the function of n places n in the base of an exponentiation, or in the exponent itself.

Any exponential growth function will grow significantly faster (long term) than any polynomial function, so the distinction is relevant to the efficiency of an algorithm, especially for large values of n.

---

Polynomial time.

A polynomial is a sum of terms that look like Constant * x^k Exponential means something like Constant * k^x

(in both cases, k is a constant and x is a variable).

The execution time of exponential algorithms grows much faster than that of polynomial ones.

---

Exponential (You have an exponential function if MINIMAL ONE EXPONENT is dependent on a parameter):

• E.g. f(x) = constant ^ x

Polynomial (You have a polynomial function if NO EXPONENT is dependent on some function parameters):

• E.g. f(x) = x ^ constant

---

polynomial time O(n)^k means Number of operations are proportional to power k of the size of input

exponential time O(k)^n means Number of operations are proportional to the exponent of the size of input

---

o (n sequre)는 polynimal 시간 복잡도이고 o (2 ^ n)은 p = np이면 best case이고, 최악의 경우 p = np는 입력 크기 n이 너무 길어 지거나 입력 크기가 증가 할 때 같지 않기 때문에 지수 시간 복잡도입니다. 더 이상 최악의 경우로 이동하고 처리하므로 복잡성 증가 속도가 증가하고 입력이 작을 때 입력의 n 크기에 의존합니다 입력 크기가 크고 클 때 다항식이므로 p = np가 같지 않음은 증가 속도가 입력의 크기에 의존 함을 의미합니다 "N ". 최적화, sat, clique 및 independ 세트도 다 동물에 대한 지수에서 만났습니다.

참고 URL : https://stackoverflow.com/questions/4317414/polynomial-time-and-exponential-time