| Compartilhamento |
|
Exportar este item:
Use este identificador para citar ou linkar para este item:
http://www.bdtd.uerj.br/handle/1/7668| Tipo do documento: | Dissertação |
| Título: | Análise de complexidade de pior caso do ShellSort por algoritmos |
| Título(s) alternativo(s): | ShellSort worst-case complexity analysis by algorithms |
| Autor: | Souza, Raquel Marcolino de  |
| Primeiro orientador: | Pinto, Paulo Eustáquio Duarte |
| Primeiro coorientador: | Oliveira, Fabiano de Souza |
| Primeiro membro da banca: | Szwarcfiter, Jayme Luiz |
| Segundo membro da banca: | Markenzon, Lilian |
| Terceiro membro da banca: | Nobrega, Hugo de Holanda Cunha |
| Resumo: | Utilizamos a abordagem empírica para o estudo de pior caso do algoritmo de ordenação ShellSort. A complexidade de tempo de pior caso deste algoritmo é conhecida apenas para algumas sequências específicas (uma sequência é um parâmetro do algoritmo). Desenvolvemos um método para determinar um limite superior para o pior caso, baseado em Frobenius, e utilizamos dois métodos previamente existentes, de Pratt e de Erkiö, na a determinação de limites inferiores para o número de comparações durante a ordenação. Através da análise empírica da complexidade de algoritmos, confirmamos as complexidades de pior caso para várias das sequências de passos presentes na literatura, de maneira mais simples que o estudo analítico e, usando a mesma metodologia, apresentamos conjecturas para as complexidades de pior caso desconhecidas. |
| Abstract: | We use the empirical approach to study the worst case of the ShellSort sorting algorithm. The worst case time complexity of this algorithm is known only for some specific sequences (a sequence is a parameter of this algorithm). We developed a method to determine an upper bound on the worst case, based on Frobenius, and used two previously existing methods, Pratt s and Erkiö s methods, in the determination of lower bounds for the number of comparisons during the sorting. Through the complexity empirical analysis of algorithms, we confirmed the worst case complexities for several step sequences studied in the literature in a simpler way than the analytical studies and, using the same methodology, we present conjectures to the unknown worst case complexities. |
| Palavras-chave: | ShellSort Algorithm Complexity Empirical Method Algoritmos ShellSort Complexidade de Algoritmos Método Empírico |
| Área(s) do CNPq: | CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO |
| Idioma: | por |
| País: | BR |
| Instituição: | Universidade do Estado do Rio de Janeiro |
| Sigla da instituição: | UERJ |
| Departamento: | Centro de Tecnologia e Ciências::Instituto de Matemática e Estatística |
| Programa: | Programa de Pós-Graduação em Ciências Computacionais |
| Citação: | SOUZA, Raquel Marcolino de. Análise de complexidade de pior caso do ShellSort por algoritmos. 2019. 102 f. Dissertação (Mestrado em Modelagem matemático-estatístico-computacional) - Universidade do Estado do Rio de Janeiro, Rio de Janeiro, 2019. |
| Tipo de acesso: | Acesso Aberto |
| URI: | http://www.bdtd.uerj.br/handle/1/7668 |
| Data de defesa: | 15-Fev-2019 |
| Aparece nas coleções: | Mestrado em Ciências Computacionais |
Arquivos associados a este item:
| Arquivo | Tamanho | Formato | |
|---|---|---|---|
| Raquel Marcolino de Souza_Dissertacao Mestrado.pdf | 1,16 MB | Adobe PDF | Baixar/Abrir Pré-Visualizar |
Os itens no repositório estão protegidos por copyright, com todos os direitos reservados, salvo quando é indicado o contrário.