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?
ALGORITMOS E IMPLEMENTAÇÕES ⇒ Analise de algoritmos Tópico resolvido
Moderador: [ Moderadores TTB ]
Jun 2020
23
13:37
Re: Analise de algoritmos
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] .
[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] .
[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]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 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]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]
[tex3]\color{YellowOrange}\textbf{Não importa o quanto se esforce ou evolua, você sempre estará abaixo do Sol}[/tex3]
[tex3]\textbf{Escanor}[/tex3]
[tex3]\textbf{Escanor}[/tex3]
-
Auto Excluído (ID:24530)
- Última visita: 31-12-69
Jun 2020
24
10:56
Re: Analise de algoritmos
tinha escrevido matematicamente porem achava que lg era [tex3]log_2[/tex3]AnthonyC escreveu: ↑Ter 23 Jun, 2020 13:37Bem, 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 64nlog10n64nlog10n etapas. Então, queremos descobrir quando:
e que só log era [tex3]log_{10}[/tex3]
kkkkkkk obrigado
Última edição: Auto Excluído (ID:24530) (Qua 24 Jun, 2020 11:01). Total de 2 vezes.
-
- Tópicos Semelhantes
- Respostas
- Exibições
- Última msg
-
- 2 Respostas
- 2088 Exibições
-
Última msg por PeterPark
-
- 1 Respostas
- 2347 Exibições
-
Última msg por LucasPinafi
-
- 0 Respostas
- 975 Exibições
-
Última msg por ITAIME
-
- 1 Respostas
- 2189 Exibições
-
Última msg por Cardoso1979
-
- 0 Respostas
- 697 Exibições
-
Última msg por Dyrlan
/loiro.png)
