I. Correção de Algoritmos Não

I. Correção de Algoritmos Não-Recursivos
Nos exercícios a seguir, você deverá demonstrar a correção dos algoritmos por meio dos
conceitos vistos nos slides da Aula 03.
1) Prove que o seguinte algoritmo para efetuar a exponenciação de números naturais está
correto:
unsigned power(unsigned a, unsigned b)
{
x = 1;
while (b > 0)
{
x = x * a;
b = b – 1;
}
return x;
}
2) Prove que o seguinte algoritmo para determinar o quadrado de um número natural está
correto:
unsigned quadrado(unsigned a)
{
x = 0;
i = 0;
while (i < a)
{
x = x + a;
i = i + 1;
}
return x;
}
3) Prove que o seguinte algoritmo para calcular o fatorial de um número natural está correto:
unsigned fatorial(unsigned a)
{
x = 1;
i = 1;
while (i <= a)
{
x = x * i;
i = i + 1;
}
return x;
}
4) Prove que o seguinte algoritmo para calcular o produto de dois números naturais está
correto:
unsigned fatorial(unsigned a, unsigned b)
{
x = 0;
while (b > 0)
{
if (b%2) x = x + a;
x = 2 * x;
b = b / 2;
}
return x;
}
5) Considere o seguinte algoritmo para ordenar n números armazenados em um arranjo A,
conhecido como ordenação por seleção :
Localizar o menor elemento de A e permutar esse elemento com
o elemento contido em A[0]. Em seguida, encontrar o segundo
menor elemento de A e permutá-lo com o elemento A[1].
Proceder dessa maneira para os primeiros n–1 elementos de A.
a) Escreva uma função em linguagem C para implementar este algoritmo.
b) Demonstre a correção deste algoritmo, enunciando e demonstrando a validade de
propriedades invariantes para os dois laços do algoritmo.
c) Explique por que ele só precisa ser executado para os primeiros n–1 elementos, e não
para todos os n elementos.
6) O bubblesort é um algoritmo de ordenação popular, que opera permutando repetidamente
elementos adjacentes que estão fora de ordem. Observe a implementação do algoritmo
bubblesort em linguagem C listada abaixo:
void bubblesort(float A[], int n)
{
for (i=0; i<n; i++)
{
for (j=n-1; j>=i+1; j--)
{
if (A[j] < A[j-1])
{
aux = A[j]; A[j] = A[j-1]; A[j-1] = aux;
}
}
}
}
a) Enuncie uma propriedade invariante mantida pelo laço “for” interno e demonstre sua
validade.
b) Usando a condição de término garantida pela propriedade invariante que você
enunciou e demonstrou no item anterior para o laço “for” interno, enuncie e demonstre
uma propriedade invariante do laço “for” externo que garanta que, ao final do
algoritmo, os elementos do vetor A estarão dispostos em ordem crescente.
Dica:
Seja A’ o arranjo resultante produzido pelo algoritmo, é necessário demonstrar que:
• A’ é uma permutação válida de A
• A’[0] ≤ A’[1] ≤ . . . ≤ A’[n–1]
II. Limites Assintóticos de Funções
Nos exercícios a seguir, você trabalhará com os conceitos de limites assintóticos abordados nos
slides da Aula 05 do curso.
7) Determine um limite assintoticamente restrito para a função n3/1000 – 100n2 – 100n + 3
em termos da notação Θ e demonstre este limite.
8) Mostre que ∑log = Θ log 9) Sejam f(n) e g(n) funções assintoticamente não negativas. Usando a definição básica da
notação Θ, prove que max(f(n) , g(n)) = Θ(f(n) + g(n)) .
10) Mostre que, para quaisquer constantes reais a e b, onde b > 0, + = 11) É verdade que 2 = O(2 )? Justifique.
12) É verdade que 2 = O(2 )? Justifique.
13) Podemos estender nossa notação ao caso de dois parâmetros n e m que podem tender a infinito
independentemente a taxas distintas. Para uma dada função g(n,m), denotamos por O(g(n,m)) o
conjunto de funções
O(g(n,m)) = {f(n,m) : existem constantes positivas c, e tais que 0≤ f(n, m) ≤ c.g(n,m)
para todo n ≥ e m ≥ } .
Forneça definições correspondentes para Ωg(n,m)) e ϴ(g(n,m)).
14) A função 15) A função "
!
é polinomialmente limitada ? Justifique.
# $%!
é polinomialmente limitada ? Justifique.
16) Ordene as funções a seguir por ordem de crescimento; ou seja, encontre um arranjo
gl, g2, . . . , g30 das funções que satisfazem a gl = Ω (g2), g2 = Ω (g3), . . . , g29 = Ω (g30)
Particione sua lista em classes de equivalência tais que f(n) e g(n) estejam na mesma
classe se e somente se f(n) = Θ(g(n)).
Obs: a função “lg” significa “log2”.
17) Para cada afirmação abaixo, determine se ela é sempre verdadeira, nunca verdadeira,
ou às vezes verdadeira e às vezes falsa para as funções assintoticamente não-negativas f
e g. Se for sempre verdadeira ou nunca verdadeira, demonstre o motivo. Se for às vezes
verdadeira e às vezes falsa, dê um exemplo em que é verdadeira e outro em que é falsa.
a) & = '& b) & +
= ϴmax#&, $
c) & + '#&$ = ϴ&
d) & = Ω# $ - & = e) & ≠ '# $ -
≠ '&
18) Verifique se a afirmação abaixo é verdadeira ou falsa. Justifique sua resposta.
Sejam f e g funções assintoticamente não negativas. Então pelo menos uma dentre as
relações f(n) = O(g(n)) e g(n) = O(f(n)) deve ser sempre verdadeira.
III. Análise Assintótica de Algoritmos Não-Recursivos
Nos exercícios a seguir, você exercitará as técnicas de análise assintótica de algoritmos
abordadas nos slides da Aula 05 do curso.
19) Considere o seguinte algoritmo para ordenar n números armazenados em um arranjo A,
conhecido como ordenação por seleção :
Localizar o menor elemento de A e permutar esse elemento com
o elemento contido em A[0]. Em seguida, encontrar o segundo
menor elemento de A e permutá-lo com o elemento A[1].
Proceder dessa maneira para os primeiros n–1 elementos de A.
a) Escreva uma função em linguagem C para implementar este algoritmo (ver item a do
exercício 5).
b) Forneça limites assintóticos justos inferior (melhor caso) e superior (pior caso) para o
tempo de execução deste algoritmo, usando as notações Ω e O.
20) Observe o algoritmo abaixo para ordenar n números armazenados em um arranjo A, onde
um laço “while” é utilizado para fazer uma pesquisa sequencial varrendo o sub-arranjo
A[0…j–1] de trás para frente à procura de um elemento maior que a chave A[j]:
void insertionsort(float A[], int n)
{
for (j=1; j<n; j++)
{
chave = A[j];
i = j-1;
while (i>0 && A[i]>chave)
{
A[i+1] = A[i];
i = i-1;
}
A[i+1] = chave;
}
}
a) Forneça limites assintóticos justos inferior (melhor caso) e superior (pior caso) para o
tempo de execução deste algoritmo, usando as notações Ω e O.
b) Repare que, em cada iteração j do laço “for” externo, os elementos do sub-arranjo
A[0…j–1] já estão ordenados. Verifique se é possível reduzir a complexidade de pior
caso deste algoritmo para O(n.log(n)) se a pesquisa sequencial implementada no laço
“while” for substituída por uma pesquisa binária. Justifique sua resposta.
21) O bubblesort é um algoritmo de ordenação popular, que opera permutando repetidamente
elementos adjacentes que estão fora de ordem. Observe a implementação do algoritmo
bubblesort em linguagem C listada abaixo:
void bubblesort(float A[], int n)
{
for (i=0; i<n; i++)
{
for (j=n-1; j>=i+1; j--)
{
if (A[j] < A[j-1])
{
aux = A[j]; A[j] = A[j-1]; A[j-1] = aux;
}
}
}
}
a) Forneça limites assintóticos justos inferior (melhor caso) e superior (pior caso) para o
tempo de execução deste algoritmo, usando as notações Ω e O.
b) De que forma o laço “for” externo poderia ser modificado (sem nenhuma mudança no
laço “for” interno) de modo a melhorar substancialmente o comportamento assintótico
do algoritmo no melhor caso (arranjo de entrada previamente ordenado) ?
c) Qual seria o novo limite assintótico inferior justo após essa modificação ?
IV. Implementação de Algoritmos Recursivos em C
Os exercícios a seguir são um treinamento para você exercitar seu raciocínio na elaboração de
algoritmos recursivos e também na implementação desses algoritmos em linguagem C.
Todas as funções solicitadas nesses exercícios devem ser implementadas em linguagem C,
sendo proibido o uso de estruturas de controle de laço (while e for). Chamadas recursivas
devem ser sempre utilizadas em lugar de laços.
Sugere-se o uso das técnicas descritas nos slides da Aula 06 do curso.
Em alguns exercícios, pode ser conveniente reutilizar funções recursivas construídas em
exercícios anteriores.
22) Escreva uma função recursiva que retorne a soma de todos os números naturais entre 1 e
um número natural n.
23) Escreva uma função recursiva que retorne a soma de todos os números naturais que
sejam múltiplos de 3 entre 1 e um número natural n.
24) Generalize a função recursiva do exercício anterior para trabalhar com múltiplos de 3
entre os números naturais m e n.
25) Generalize ainda mais a função recursiva do exercício anterior para trabalhar com
múltiplos de um número natural k entre m e n.
26) Escreva uma função recursiva que retorne o valor do dígito mais significativo de um
número natural n.
27) Escreva uma função recursiva que retorne a quantidade de dígitos de um número natural
n.
28) Escreva uma função recursiva que retorne a soma de todos os dígitos de um natural n.
29) Escreva uma função recursiva que determine se um número natural é “palíndrome”
(exemplos de números “palíndromes”: 12421 e 123321).
Sugestão: tente uma estratégia de recursividade baseada no resultado obtido para o número
correspondente ao argumento de entrada sem os dígitos mais e menos significativos.
30) Escreva uma função recursiva que determine se um número natural m “pertence” a um
número natural n (exemplos: 12 “pertence” a 490127, mas 327 não “pertence” a 490127).
31) Idem ao exercício anterior, mas sem ser necessário que os dígitos de m estejam contíguos
em n (exemplos: 12 e 469 “pertencem” a 34166729, mas 327 não pertence a 234125).
32) Escreva uma função recursiva que retorne o valor do maior dígito de um natural n.
33) Escreva uma função recursiva que determine se todos os dígitos de um número natural n
estão em ordem crescente.
34) Escreva uma função recursiva que determine se as somas de todos os pares de dígitos
“diametralmente opostos” de um número natural n são as mesmas. Por exemplo, as somas
em 13524 são as mesmas pois 1+4=3+2=5.
Sugestão: a mesma fornecida para o exercício dos “palíndromes”.
35) Escreva uma função recursiva que retorne o valor correspondente a um número natural n
com os seus dígitos reorganizados em ordem reversa.
36) Escreva uma função recursiva que determine se todos os dígitos de um número natural n
são pares.
37) Escreva uma função recursiva para “rodar” os dígitos de um número natural n para a
direita um total de k vezes. Por exemplo, rodar o número 23412 para a direita 3 vezes
resulta no número 41223.
38) Escreva uma função recursiva para “deslocar” os dígitos de um número natural n para a
direita um total de k vezes descartando o dígito menos significativo a cada deslocamento.
Por exemplo, deslocar o número 23412 para a direita 3 vezes resulta no número 23.
39) Escreva uma função recursiva para determinar se todos os dígitos de um número natural
n são potências de 2.
40) Escreva uma função para determinar o k-ésimo maior dígito de um número natural n.
41) Escreva uma função que subtraia uma unidade de cada dígito de um número natural n.
Por exemplo, para o número 4312 a sua função deve retornar como resultado o número
3201. Suponha que o seu número não contém dígitos 0.
42) Escreva uma função recursiva para multiplicar todos os dígitos de um número natural n.
Por exemplo, para o número 3459 a sua função deve retornar 3 × 4 × 5 × 9, isto é, 540.
43) Escreva uma função recursiva que determine quantas vezes um dígito k ocorre em um
número natural n. Por exemplo, o dígito 2 ocorre 3 vezes em 762021192.
44) Escreva uma função para determinar a maior soma de dígitos diametralmente opostos de
um número natural n.
45) 26. Escreva uma função para determinar o menor número de vezes que eu tenho que
“rodar” para a direita os dígitos de um número natural n de tal forma a obter o próprio
número novamente. Por exemplo, “rodando” 2 vezes os dígitos do número 272727 este
mesmo número é obtido como resultado.
46) Escreva uma função recursiva que determine se as somas dos dígitos “diametralmente
opostos” de um número inteiro estão em ordem crescente de fora para dentro. Por
exemplo: 2534 e 25934 têm essa propriedade, pois 2+4 = 6 < 5+3 = 8 < 9.
47) Escreva uma função para determinar se todas as somas dos dígitos diametralmente
opostos de um número inteiro são números pares (neste caso 2534 tem essa propriedade,
mas 25934 não).
V. Correção de Algoritmos Recursivos
Nos exercícios a seguir, você deverá demonstrar a correção dos algoritmos recursivos pelo
método indutivo abordado nos slides da Aula 06.
48) Prove por indução as afirmativas abaixo:
a) Para todo ≥ 1, ∑4
− 1 − 2 = − 1 − 2 − 3/4
b) Para todo ≥ 0, ∑4
2 + 1 = c) Para todo ≥ 1, ∑ = + 1/2
d) Para todo ≥ 0, 6 − é divisível por 5.
e) Para todo ≥ 0, ∑ 7 = 7 − 1, sendo 7 o n-ésimo número de Fibonacci.
49) Demonstre pelo método indutivo que o seguinte algoritmo recursivo retorna o valor
5 − 3 , para todo ≥ 0.
float g(float n)
{
if (n<=1) return 2*n;
return 8*g(n-1) – 15*g(n-2);
}
50) Descreva uma implementação recursiva (em pseudo-código ou em linguagem C) para os
algoritmos abaixo e demonstre sua correção pelo método indutivo:
a) Busca Binária
b) Ordenação por Inserção
c) Ordenação por Intercalação
VI. Resolução de Recorrências
Nos exercícios a seguir, você deverá solucionar as recorrências pelos métodos abordados nos
slides da Aula 06.
51) Sejam a, b e c constantes não negativas. Prove que a solução para
9
@ = 1
>1
:1 = c
Tn = a. T/b + c. n
para n uma potência de b é:
On ,
T(n) = BOn log n ,
O#nFGHI J $ ,
a < E,
a = b,@
a > E
52) Resolva as equações de recorrência :
a) K
b) 9
Tn = 2T LNO + n,
M
T1 = 27
para n > 1@
Tn = 7Tn/2 + n , para n > 1@
T1 = 0
Tn = T#√n$ + log n, para n ≥ 1@
T1 = 1
Dica: use mudança de variáveis.
c) K
53) Usando substituição, resolva as recorrências :
a) Mostre que a solução para T(n) = 2T(⌊n/2⌋) + 17 é O(n lg n).
b) T(n) = 2T(√n) + 1
54) Resolva assintoticamente as recorrências abaixo. Suponha T(n) constante para n pequeno.
a) T(n) = 3T(n/2) + n lg n
b) T(n) = 2T(n/2) + n/ lg n
c) T(n) = 4T(n/2) + n lg n
55) Use indução matemática para mostrar que, quando n é uma potência exata de 2, a solução
da recorrência
: = K
2
V- = 2,
2: L O + V- > 2 , XY Z > 1
W
é : = log .
@
56) Demonstre, com o auxílio de uma árvore de recursão, que a solução para a recorrência
T(n) = T(n/3) + T(2n/3) + c.n, onde c é uma constante, é Ω(n.log(n)).
57) Use uma árvore de recursão para fornecer um limite assintoticamente restrito para a
recorrência T(n) = T([.n) + T((1–[).n) + c.n, onde α é uma constante no intervalo 0 < [< 1
e c > 0 também é uma constante.
58) Forneça limites assintóticos superiores e inferiores para T(n) em cada uma das
recorrências a seguir. Suponha que T(n) seja constante para n suficientemente pequeno.
Torne seus limites tão restritos quanto possível e justifique suas respostas.
a) : = 2: L O + \
b) : = : LO + ]
c) : = 16: L NO + d) : = 7: L \O + e) : = 7: L O + f) : = 2: L NO + √
g) : = : − 1 + h) : = :#√$ + 1
i) : = 3: L O + log j) : = 5: L O +
6
FGH k) : = 4: L O + √
l) : = 3: L \ + 5O + m) : = 2: L O +
FGH n) : = : L O + : L O + : L O + o T = T − 1 +
N
_
p T = T − 1 + log q : = : − 2 + 2 log r : = √:#√$ + s) : = 2 : L O + log \
t) : = 3 : L O + log 6
u) : = : L O + 2
v) : = :#√$ + ϴlog log n
w) : = 10: L \O + 17 .
x) : = 7: L O + \
y) : = : L + √O + √6046
z) : = : − 2 + log aa) : = : L 6 O + : L 6 O + ϴ
N
bb): = √:#√$ + 100
59) Considere a recorrência : = : L O + : L NO + . Use o método da substituição para
encontrar o limite superior mais justo possível para a recorrência, utilizando a notação O.
60) Demonstre um limite superior o mais justo possível (notação O) na solução de cada
recorrência a seguir:
a) : = 2: L _O + √
a
b) : = : L O + : L O + 5
c) : = K
\
N
8: L O 9 + ϴ1 V- > d,@
d V- < d,
61) Use o método da substituição para provar um limite inferior justo (notação Ω) na solução
da seguinte recorrência:
: = 4: L O + 62) Verifique se a afirmação abaixo é verdadeira ou falsa e justifique sua resposta:
A solução para a recorrência : = 3: L \ O + 'log é : = ϴ log .
VII. Análise Assintótica de Algoritmos Recursivos
Nos exercícios a seguir, você determinará limites assintóticos para algoritmos recursivos,
determinando as recorrências que descrevem o tempo de execução destes algoritmos e
resolvendo estas recorrências, pelos métodos abordados nos slides da Aula 06.
63) A ordenação por inserção pode ser expressa sob a forma de um procedimento recursivo
como a seguir.
Para ordenar um arranjo A[1 ... n], ordenamos recursivamente o sub-arranjo A[1 ... n–1]
e em seguida inserimos o elemento A[n] no sub-arranjo ordenado A[0 ... n–1].
Escreva uma recorrência para o tempo de execução dessa versão recursiva da ordenação
por inserção.
64) Embora a ordenação por intercalação funcione no tempo de pior caso ϴ(n.log(n)) e a
ordenação por inserção funcione no tempo de pior caso ϴ ( ), os fatores constantes na
ordenação por inserção a tornam mais rápida para n pequeno. Assim, faz sentido usar a
ordenação por inserção dentro da ordenação por intercalação quando os subproblemas se
tornam suficientemente pequenos.
Considere uma modificação na ordenação por intercalação, na qual n/k sub-listas de
comprimento k são ordenadas usando-se a ordenação por inserção e, em seguida,
intercaladas com o uso do mecanismo padrão de intercalação, onde k é um valor a ser
determinado.
a) Mostre que as n/k sub-listas, cada uma de comprimento k, podem ser ordenadas
através da ordenação por inserção no tempo de pior caso ϴ(n.k).
b) Mostre que as sub-listas podem ser intercaladas no tempo de pior caso
ϴ(n.Iog(n/k)).
c) Dado que o algoritmo modificado é executado no tempo de pior caso
ϴ(n.k + n.Iog(n/k)), determine o maior valor assintótico (notação ϴ) de k como uma
função de n para a qual o algoritmo modificado tem o mesmo tempo de execução
assintótico que a ordenação por intercalação padrão.
d) Como k deve ser escolhido na prática?
65) Para cada algoritmo abaixo, forneça a recorrência que descreve seu tempo de execução no
pior caso e dê o seu tempo de execução no pior caso usando a notação ϴ.
a) Busca Binária
b) Ordenação por Inserção
c) Ordenação por Intercalação
VIII. Construção de Algoritmos Eficientes
Nos exercícios a seguir, você construirá algoritmos ótimos e/ou sujeitos a especificações de
eficiência assintótica, utilizando os conhecimentos abordados nos slides da Aula 04, 05 e 06.
66) Considere o problema de construir um arranjo ordenado C[1...m+n] composto de m+n
números distintos obtidos de dois arranjos ordenados A[1...m] e B[1...n].
a) Determine uma cota inferior para este problema, expressa em notação Ω.
b) Construa um algoritmo ótimo para resolver este problema, ou seja, um algoritmo
que tenha a cota inferior do problema como limite assintótico superior de seu
tempo de execução de pior caso.
67) Considere um conjunto S com ≥ 2 números distintos. Diz-se que um par de números
distintos x,y ∈ g são próximos em S se |i − j| ≤ 4 max k − min k , k ∈ g, ou seja, se a
distância entre x e y é, no máximo, a distância média entre números consecutivos
ordenados.
a) Explique brevemente porque todo grupo S com ≥ 2 números distintos contém
um par de elementos próximos em S.
b) Suponha que particionemos S em torno de um elemento pivô X ∈ g, organizando o
resultado em dois subgrupos g = mi ∈ g | i ≥ Xn e g = mi ∈ g | i ≤ Xn. Prove que,
para algum Z ∈ m1,2n, existe um par x, y ∈ gW de números que são próximos em S (e
não somente em Sk).
c) Descreva um algoritmo de tempo O(n) para encontrar um par de números
próximos em S (Dica use a estratégia “dividir para conquistar”).
d) Analise seu algoritmo, demonstrando o limite superior assintótico O(n).
68) Seja A[l...n] um arranjo de n números distintos. Se i < j e A[i] > A[j], então o par ( i , j ) é
chamado uma inversão de A.
a) Liste as cinco inversões do arranjo { 2, 3, 8, 6, 1 }.
b) Qual arranjo com elementos do conjunto { 1, 2, ... , n } tem o número máximo de
inversões ? Quantas inversões ele tem ?
c) Qual é o relacionamento entre o tempo de execução da ordenação por inserção e o
número de inversões no arranjo de entrada? Justifique sua resposta.
d) Construa um algoritmo que determine o número de inversões em qualquer
permutação sobre n elementos no tempo do pior caso de ϴ(n.Iog(n)). Sugestão:
modifique a ordenação por intercalação.
69) Um vetor A[1..n] é unimodal se consiste de uma sequência crescente seguida de uma
sequência decrescente, ou mais precisamente, se existe um índice m ∈ m1,2, … , n tal que
•
•
pqr < pq + 1r XY st 1 ≤ < pqr > pq + 1r XY st ≤ < Em particular, A[m] é o maior elemento, e é, também, o único máximo local rodeado por
elementos menores (A[m-1] e A[m+1]).
a) Construa um algoritmo para determinar o maior elemento de um vetor unimodal
A[1..n] em tempo O(log n).
b) Prove que o seu algoritmo está correto.
c) Prove o limite superior assintótico de seu tempo de execução.
Um polígono é convexo se todos os seus ângulos internos são menores que 180o, como
ilustrado na figura abaixo:
Representa-se um polígono convexo como um vetor V[1..n] onde cada elemento do vetor
representa um vértice do polígono na forma de um par ordenado (x,y). Sabe-se que V[1] é
o vértice com a menor coordenada x e os vértices V[1..n] são ordenados no sentido
horário, como mostra a figura. Deve-se assumir que as coordenadas x dos vértices são
todas distintas entre si, assim como as coordenadas y o são.
a) Construa um algoritmo para encontrar o vértice com a maior coordenada x em
tempo O(log n).
b) Construa um algoritmo para encontrar o vértice com a maior coordenada y em
tempo O(log n).
70) Descreva um algoritmo de tempo ϴ(n.log(n)) que, dado um número x e um conjunto S
composto de n números distintos, determine se existem ou não dois elementos em S cuja
soma seja exatamente x.
71) Verifique se a afirmação abaixo é verdadeira ou falsa e justifique sua resposta:
Um arranjo composto de n números cujos valores podem ser somente
–1, 0 ou 1 pode ser ordenado em tempo de pior caso de O(n).
IX. Análise Assintótica Experimental
No exercício a seguir, você estimará limites assintóticos e fará previsões a partir de medições
experimentais construirá algoritmos ótimos e/ou sujeitos a especificações de eficiência
assintótica, utilizando os conhecimentos abordados nos slides da Aula 04 e 05.
72) Três algoritmos (A, B e C) foram desenvolvidos para resolver um mesmo problema. A
tabela abaixo mostra os tempos de processamento obtidos nos testes dos 3 algoritmos na
resolução de problemas com tamanhos n=10, n=20, n=30 e n=40.
Tamanho do
Problema
n = 10
n = 20
n = 30
n = 40
Algoritmo A
Algoritmo B
Algoritmo C
( hh:mm:ss )
( hh:mm:ss )
( hh:mm:ss )
00:00:04
00:00:32
00:01:48
00:04:15
00:00:20
00:01:20
00:02:59
00:05:19
00:08:18
00:16:36
00:24:55
00:33:13
a) Estime as taxas de crescimento dos três algoritmos, expressando-as na notação O.
b) Estime o tempo de processamento que cada algoritmo consumiria na resolução de um
problema de tamanho n=100 e n=1000.
c) Qual dentre os três algoritmos é o mais recomendável para ser utilizado na resolução
de problema de grande porte ? E para problemas de tamanho pequeno e moderado ?