Tempo polinomial e tempo exponencial

Question 1

Alguém poderia explicar a diferença entre algoritmos de tempo polinomial, tempo não polinomial e tempo exponencial?

Por exemplo, se um algoritmo leva tempo O (n ^ 2), então em qual categoria ele está?

Question 2

Veja isso .

Exponencial é pior do que polinomial.

O (n ^ 2) cai na categoria quadrática, que é um tipo de polinômio (o caso especial do expoente sendo igual a 2) e melhor que exponencial.

Exponencial é muito pior do que polinomial. Veja como as funções crescem

n    = 10    |     100   |      1000

n^2  = 100   |   10000   |   1000000 

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

k ^ 1000 é excepcionalmente grande, a menos que k seja menor do que algo como 1.1. Tipo, algo como cada partícula no universo teria que fazer 100 bilhões de bilhões de bilhões de operações por segundo por trilhões de bilhões de bilhões de anos para fazer isso.

Eu não calculei isso, mas É TÃO GRANDE.

Question 3

Abaixo estão algumas funções comuns do Big-O durante a análise de algoritmos.

O ( 1 ) - tempo constante
O ( log (n) ) - tempo logarítmico
O ( (log (n)) ^c ) - tempo polilogarítmico
O ( n ) - tempo linear
O ( n ² ) - tempo quadrático
O ( n ^c ) - tempo polinomial
O ( c ⁿ ) - tempo exponencial
O ( n! ) - tempo fatorial

(n = tamanho da entrada, c = alguma constante)

Aqui está o gráfico do modelo que representa a complexidade Big-O de algumas funções

Felicidades :-)

créditos do gráfico http://bigocheatsheet.com/

Question 4

O (n ^ 2) é o tempo polinomial. O polinômio é f (n) = n ^ 2. Por outro lado, O (2 ^ n) é o tempo exponencial, onde a função exponencial implícita é f (n) = 2 ^ n. A diferença é se a função de n coloca n na base de uma exponenciação ou no próprio expoente.

Qualquer função de crescimento exponencial crescerá significativamente mais rápido (longo prazo) do que qualquer função polinomial, então a distinção é relevante para a eficiência de um algoritmo, especialmente para grandes valores de n.

Question 5

Tempo polinomial.

Um polinômio é uma soma de termos que parecem Constant * x^k Exponencial e significa algo comoConstant * k^x

(em ambos os casos, k é uma constante e x é uma variável).

O tempo de execução de algoritmos exponenciais cresce muito mais rápido do que os polinomiais.

Question 6

Exponencial (você tem uma função exponencial se MINIMAL ONE EXPONENT for dependente de um parâmetro):

Por exemplo, f (x) = constante ^ x

Polinomial (você tem uma função polinomial se NENHUM EXPONENTE depende de alguns parâmetros de função):

Por exemplo, f (x) = x ^ constante

Question 7

tempo polinomial O (n) ^ k significa que o número de operações é proporcional à potência k do tamanho da entrada

tempo exponencial O (k) ^ n significa que o número de operações é proporcional ao expoente do tamanho da entrada

Question 8

o (n sequre) é a complexidade de tempo polinimal enquanto o (2 ^ n) é a complexidade de tempo exponencial se p = np no melhor caso, no pior caso p = np não é igual porque o tamanho de entrada n cresce tanto ou o tamanho de entrada aumenta tanto por mais tempo está indo para o pior caso e tratando assim a taxa de crescimento de complexidade aumenta e depende do tamanho n da entrada quando a entrada é pequena é polinimal quando o tamanho da entrada é grande e grande então p = np diferente significa que a taxa de crescimento depende do tamanho da entrada "N " otimização, sat, clique e conjunto independente também se encontram em exponencial para polinimal.

Answer 1

Alguém poderia explicar a diferença entre algoritmos de tempo polinomial, tempo não polinomial e tempo exponencial?

Por exemplo, se um algoritmo leva tempo O (n ^ 2), então em qual categoria ele está?

Answer 2

87

Veja isso .

Exponencial é pior do que polinomial.

O (n ^ 2) cai na categoria quadrática, que é um tipo de polinômio (o caso especial do expoente sendo igual a 2) e melhor que exponencial.

Exponencial é muito pior do que polinomial. Veja como as funções crescem

n    = 10    |     100   |      1000

n^2  = 100   |   10000   |   1000000 

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

k ^ 1000 é excepcionalmente grande, a menos que k seja menor do que algo como 1.1. Tipo, algo como cada partícula no universo teria que fazer 100 bilhões de bilhões de bilhões de operações por segundo por trilhões de bilhões de bilhões de anos para fazer isso.

Eu não calculei isso, mas É TÃO GRANDE.

hvgotcodes
fonte

29

Eu gostei de todas as suas ilusões.

Josephine

7

k ^ 1000 é excepcionalmente grande se k for apreciavelmente maior do que 1. Se k = 1 é menos impressionante, e se k = 1,00069387 ..., é 2.

Josephine

2

Que tal n! vs k ^ n. Eu sei por 2 ^ n (mais comum), n! será mais caro, mas eu acredito que para um k ^ n geral onde k> 2, n! será menos caro.

Saad

1

Estou feliz que você não disse "bilhões e bilhões". :-)

Tom Russell

@Saad n! sempre será mais caro do que k ^ n para uma constante k, assintoticamente. Você está certo, entretanto, em que este é o caso somente quando alcançamos um valor alto de n. Pela aproximação de Stirling, o tempo fatorial deve se tornar mais caro quando n = e * k, onde e = 2,71828 ..

inavda

Answer 3

29

Eu gostei de todas as suas ilusões.

Josephine

Answer 4

7

k ^ 1000 é excepcionalmente grande se k for apreciavelmente maior do que 1. Se k = 1 é menos impressionante, e se k = 1,00069387 ..., é 2.

Josephine

Answer 5

2

Que tal n! vs k ^ n. Eu sei por 2 ^ n (mais comum), n! será mais caro, mas eu acredito que para um k ^ n geral onde k> 2, n! será menos caro.

Saad

Answer 6

1

Estou feliz que você não disse "bilhões e bilhões". :-)

Tom Russell

Answer 7

@Saad n! sempre será mais caro do que k ^ n para uma constante k, assintoticamente. Você está certo, entretanto, em que este é o caso somente quando alcançamos um valor alto de n. Pela aproximação de Stirling, o tempo fatorial deve se tornar mais caro quando n = e * k, onde e = 2,71828 ..

inavda

Answer 8

140

Abaixo estão algumas funções comuns do Big-O durante a análise de algoritmos.

O ( 1 ) - tempo constante
O ( log (n) ) - tempo logarítmico
O ( (log (n)) ^c ) - tempo polilogarítmico
O ( n ) - tempo linear
O ( n ² ) - tempo quadrático
O ( n ^c ) - tempo polinomial
O ( c ⁿ ) - tempo exponencial
O ( n! ) - tempo fatorial

(n = tamanho da entrada, c = alguma constante)

Aqui está o gráfico do modelo que representa a complexidade Big-O de algumas funções

Felicidades :-)

créditos do gráfico http://bigocheatsheet.com/

Mohanraj Balasubramaniam
fonte

12

Mais um para menos palavras e mais clareza.

user3144836

1 = n ^ 0 então também polinomial

BigChief

Answer 9

12

Mais um para menos palavras e mais clareza.

user3144836

Answer 10

1 = n ^ 0 então também polinomial

BigChief

Answer 11

O (n ^ 2) é o tempo polinomial. O polinômio é f (n) = n ^ 2. Por outro lado, O (2 ^ n) é o tempo exponencial, onde a função exponencial implícita é f (n) = 2 ^ n. A diferença é se a função de n coloca n na base de uma exponenciação ou no próprio expoente.

Qualquer função de crescimento exponencial crescerá significativamente mais rápido (longo prazo) do que qualquer função polinomial, então a distinção é relevante para a eficiência de um algoritmo, especialmente para grandes valores de n.

Answer 12

Essa resposta tem um ar autoritário (bom), mas difere da resposta de @dheeran, acredito, em se a base no caso exponencial é necessariamente 2. Ou provavelmente eu não entendi e só preciso tirar o pó da minha álgebra.

Tom Russell,

Answer 13

Tempo polinomial.

Um polinômio é uma soma de termos que parecem Constant * x^k Exponencial e significa algo comoConstant * k^x

(em ambos os casos, k é uma constante e x é uma variável).

O tempo de execução de algoritmos exponenciais cresce muito mais rápido do que os polinomiais.

Answer 14

18

Exponencial (você tem uma função exponencial se MINIMAL ONE EXPONENT for dependente de um parâmetro):

Por exemplo, f (x) = constante ^ x

Polinomial (você tem uma função polinomial se NENHUM EXPONENTE depende de alguns parâmetros de função):

Por exemplo, f (x) = x ^ constante

Erhard Dinhobl
fonte

4

Não gosto se não sobrar nada da minha resposta original depois de editada por um usuário. Isso é algum tipo de "pesca semelhante"?

Erhard Dinhobl

2

Eu tenho que concordar. As mudanças são ridículas.

satya on rails

Answer 15

4

Não gosto se não sobrar nada da minha resposta original depois de editada por um usuário. Isso é algum tipo de "pesca semelhante"?

Erhard Dinhobl

Answer 16

2

Eu tenho que concordar. As mudanças são ridículas.

satya on rails

Answer 17

tempo polinomial O (n) ^ k significa que o número de operações é proporcional à potência k do tamanho da entrada

tempo exponencial O (k) ^ n significa que o número de operações é proporcional ao expoente do tamanho da entrada

Answer 18

o (n sequre) é a complexidade de tempo polinimal enquanto o (2 ^ n) é a complexidade de tempo exponencial se p = np no melhor caso, no pior caso p = np não é igual porque o tamanho de entrada n cresce tanto ou o tamanho de entrada aumenta tanto por mais tempo está indo para o pior caso e tratando assim a taxa de crescimento de complexidade aumenta e depende do tamanho n da entrada quando a entrada é pequena é polinimal quando o tamanho da entrada é grande e grande então p = np diferente significa que a taxa de crescimento depende do tamanho da entrada "N " otimização, sat, clique e conjunto independente também se encontram em exponencial para polinimal.

Tempo polinomial e tempo exponencial

Respostas: