Complexidade de Agoritmos

[joao1245 0]

Olá pessoal, estou com uma grande dúvida em Complexidade de Algoritmos e gostaria de saber se alguém poderia me ajudar!! É URGENTE!!!!!

Estava estudando complexidade de algoritmos pelo livro Projeto de Algoritmos de Nivio Ziviane e fiquei em dúvida em uma afirmação em um dos exemplos do livro:

 

Suponha g(n) = n e f(n) = n^2. Sabemos pela definição acima que g(n) é O(n^2), pois para n >= 0, n <= n^2. Entretanto f(n) não é O(n). Suponha que existam

constantes c em tais que para todo n >= m, n^2 <= cn. Logo c >= n para qualquer n >= m, e não existe uma constante c que possa ser maior ou igual a n para

todo n.

 

Bom a dúvida é que não entendi porque g(n) é O(n), e f(n) não é O(n)?

Poderiam me explicar fazendo o favor de uma maneira que consiga entender, desde já agradeço pessoal!!!

[EuToComProblema! 1]

Li isso várias vezes e fica meio difícil entender sem o que tinha antes... Isso é só um exemplo...

 

Tipo f(x) = x + 2

 

f(10) = 12

f(2) = 4

 

 

acho que é mais ou menos essa idéia... deve ter coisa escrita acima que depois é explicado (ou complicado) de forma matemática...

 

Não quer tentar escrever o que tinha um pouco antes disso que postou?

[joao1245 0]

Li isso várias vezes e fica meio difícil entender sem o que tinha antes... Isso é só um exemplo...

 

Tipo f(x) = x + 2

 

f(10) = 12

f(2) = 4

 

 

acho que é mais ou menos essa idéia... deve ter coisa escrita acima que depois é explicado (ou complicado) de forma matemática...

 

Não quer tentar escrever o que tinha um pouco antes disso que postou?

 

Olá, antes do exemplo do livro, que citei acima, havia estes trechos:

 

Knuth (1968) sugeriu uma notação para dominação assintótica.

Para expressar que f(n) domina assintoticamente g(n) escrevemos g(n) = O(f(n)), onde se lê g(n) é da ordem no máximo f(n).

Por exemplo, quando dizemos que o tempo de execução T(n) de um programa é O(n^2), isto significa que existem constantes

c e m tais que, para valores de n maiores ou iguais a m, T(n) <= cn^2.

Definição Notação O: Uma função g(n) é O(f(n)) se existem duas constantes positivas c e m tais que g(n) <= c.f(n), para

n >= m.

 

Por favor ficarei muito grato se puder me ajudar!!!!!

 

Por favor pessoal, alguém me responda, por favor!!!! Tenho que sanar essa dúvida!!!!

[quitZAUMMM 18]

+ pelo q você escreveu g(n) não é O(n) e sim O(n^2)

de uma olhadinha soh na página 22

 

[]s