Comparando ordens de grandeza

  versus  

O número de passos em uma busca sequencial de uma lista ordenada é  , e em uma busca binária é  . O que significa esta afirmação? Vamos aos fatos:

1) Definição: Sejam f(x) e g(x) funções positivas para x suficientemente grande. Dizemos que, f é no máximo da ordem de g para x suficientemente grande, se existe inteiro M >0, tal que

para estes x, isto é, a função f é envelopada pela função Mg.

2) A ordem de grandeza é importante na análise de um algoritmo computacional, onde o número de vezes de uma tarefa é executada depende do tamanho dos dados de entrada. Para entender melhor o efeito da ordem de graneza na análise de algoritmos, suponha dois algoritmos,  e  fazendo a mesma coisa, mas   é    e    é . Para processar dados de entrada de tamanho 100, n = 100,  processa em 0,01 segundos e  em 1 segundo e, essa diferença afeta sensivelmente o tempo de computação à medida que n vai ficando maior.

3) Conclusão: É importante colocar o algoritmo em funcionamento, procurar saber se existe um outro algoritmo que faça o mesmo efeito, com ordem de grandeza menor.

Problemas e soluções - 08

Questão (Poscomp-2011): O código Morse usa dois símbolos: ponto e traço horizontal. Se as palavras desse alfabeto tiverem de 1 a 4 letras, é correto afirmar que o código Morse permitirá escrever:

a) 8 palavras

b) 16 palavras

c) 30 palavras

d) 32 palavras

e) 256 palavras

Solução: Palavras com

1 caracter: 2

2 caracteres:

3 caracteres:

4 caracteres:

Total: 2+4+8+16=30, item c)

Lembrete: Palavra é uma cadeia de caracteres justapostos sobre um alfabeto.

Problemas e soluções - 07

Questão (Mantenedores): Um médico receita, a um paciente, antibiótico (injetável) que deve ser aplicado de 12 em 12 horas. A bula deste remédio informa que, 24 horas após a primeira dose, a concentração plasmática da substância ativa, reduz a 10 % da concentração máxima. Um matemático informa que esta concentração varia com o tempo de acordo com a função  para determinados valores das constantes a e b, onde b é o tempo em horas e f(x) a concentração após passar x horas. Dentro deste cenário, a fração da dose inicial ainda no organismo na ocasião da segunda dose é:
a) 31,5 %
b) 3,15 %
c) 0,315 %
d) 13,5 %
e) 51,3 %

Solução:
Concentração máxima: f(0) = b
Em um dia:

   e f(24) = 10% de b, logo

Queremos saber

 

Temos:



O que corresponde a 31,5 %, cuja resposta é o item a)

Lembrete:   x % de b é em valor numérico      

Problemas e soluções - 06

Questão (Mantenedores): Uma colônia de bactérias começa com uma e dobra seu número a cada uma hora. O número de bactérias desta colônia, após completar um dia é:

a)

b)

c)

d)

e) 224

Solução: Em um dia, o proceso de crescimento acontecerá 24 vezes. Assim, temos a sequência número de bactérias e os passos a cada hora dada por:

 1; 2; 4; 8; 16; 32; ...

isto é,

  ; ; ;   ; ; ...

logo, passado 24 horas, o tempo de sequência é , conduzindo a resposta c).

Problemas e soluções - 05

Questão (POSCOMP-2011):  Sejam A e B eventos arbitrários de um espaço amostral, em que  é o complementar de B. Nessas condições é correto afirmar:

a) P(A) >  P(B)
b) P(A) < P(B)
c) P(A) = P(B)
d)
e)

Solução:

Temos

logo      

resposta item e).

Lembrete: X e Y eventos tais que  Então .

Problemas e Soluções - 04

Questão (Mantenedores): Uma função recursiva é uma função definida por um conjunto finito de regras. A função de ACKERMANN definida pelas regras:

i) A(0,y) = 1, para   0;

ii) A(1,0) = 2

iii) A(x,0) = x+2, para    2 ;

iv)  A(x+1, y+1) = A(A(x,y+1), y ) para quaisquer x e y não negativo, é recursiva. O valor de A(2,1) é:

a) 4
b) 3
c) 2
d) 1
e) 5

Solução:
A(2,1) = A(1+1, 0+1) = A(A(1,0),0) = A(2,0) + 2+2 = 4 ; levando ao item a).