ALGORITMOS E IMPLEMENTAÇÕES ⇒ Analise de algoritmos Tópico resolvido

[Auto Excluído (ID:24530)]

Vamos supor que estamos comparando implementações de ordenação por inserção e ordenação
por intercalação na mesma máquina. Para entradas de tamanho n, a ordenação por inserção é
executada em 8n²
etapas, enquanto a ordenação por intercalação é executada em 64n lg n etapas.
Para que valores de n a ordenação por inserção supera a ordenação por intercalação?
tem alguma maineira de resolver sem ser usando o gráfico ou ir dando valores?

[AnthonyC]

Bem, primeiro você escreve matematicamente o que quer, "para que valores de [tex3]n[/tex3] a ordenação por inserção supera a ordenação por intercalação?" A ordenação por inserção é executada em [tex3]8n^2[/tex3] etapas, enquanto a ordenação por intercalação é executada em [tex3]64n \log_{10} n[/tex3] etapas. Então, queremos descobrir quando:
[tex3]8n^2>64n \log_{10} n[/tex3]
[tex3]n^2>8n \log_{10} n[/tex3]
[tex3]n>8\log_{10}n[/tex3], já que [tex3]n\neq0[/tex3]
Já que [tex3]n[/tex3] é o número de etapas, então [tex3]n\in \mathbb{N}[/tex3]. Assim, podemos dividir em casos baseados no número de dígitos de [tex3]n[/tex3].

• Se [tex3]1\leq n \lt 10[/tex3]

[tex3]0\leq \log_{10}n\ <1[/tex3]
[tex3]0\leq 8\log_{10}n\ <8[/tex3]
Como [tex3]8 >8\log_{10}n[/tex3], então se [tex3]n=\{8,9\}[/tex3], [tex3]n >8\log_{10}n [/tex3].

• Se [tex3]10\leq n <100[/tex3]

[tex3]1\leq \log_{10}n\ <2[/tex3]
[tex3]8\leq 8\log_{10}n\ <16[/tex3]
Como [tex3]n=100\implies8\log_{10}n\ =16[/tex3], podemos ver que [tex3]n[/tex3] sempre será maior que [tex3]8\log_{10}n[/tex3]. Assim, daqui pra frente, [tex3]n[/tex3] sempre terá ordem de grandeza maior que [tex3]8\log_{10}n[/tex3].

Assim, só nos resta testar os valores entre 1 e 7.

• [tex3]n=1\implies 8\log_{10}n=0[/tex3], então [tex3]n>8\log_{10}n[/tex3]

• [tex3]n=2\implies 8\log_{10}n\approx 2,4[/tex3], então [tex3]n<8\log_{10}n[/tex3]

• [tex3]n=3\implies 8\log_{10}n\approx 3,8[/tex3], então [tex3]n<8\log_{10}n[/tex3]

• [tex3]n=4\implies 8\log_{10}n\approx 4,8[/tex3], então [tex3]n<8\log_{10}n[/tex3]

• [tex3]n=5\implies 8\log_{10}n\approx 5,5[/tex3], então [tex3]n<8\log_{10}n[/tex3]

• [tex3]n=6\implies 8\log_{10}n\approx 6,2[/tex3], então [tex3]n<8\log_{10}n[/tex3]

• [tex3]n=7\implies 8\log_{10}n\approx 6,7[/tex3], então [tex3]n>8\log_{10}n[/tex3]

Assim, concluímos que para [tex3]\{n\in \mathbb{N}/n=1 \text{ ou } n\geq 7\}[/tex3], a ordenação por inserção supera a ordenação por intercalação.

[Auto Excluído (ID:24530)]

Bem, primeiro você escreve matematicamente o que quer, "para que valores de nn a ordenação por inserção supera a ordenação por intercalação?" A ordenação por inserção é executada em 8n28n2 etapas, enquanto a ordenação por intercalação é executada em 64nlog10n64nlog10⁡n etapas. Então, queremos descobrir quando:

tinha escrevido matematicamente porem achava que lg era [tex3]log_2[/tex3]
e que só log era [tex3]log_{10}[/tex3]
kkkkkkk obrigado