Análise de complexidade de pior caso do ShellSort por algoritmos

• Ano de defesa: 2019
• Autor(a) principal: Souza, Raquel Marcolino de
• Tipo de documento: Dissertação
• Tipo de acesso: Acesso aberto
• Idioma: por
• Instituição de defesa: Universidade do Estado do Rio de Janeiro; Centro de Tecnologia e Ciências::Instituto de Matemática e Estatística; BR; UERJ; Programa de Pós-Graduação em Ciências Computacionais
• Palavras-chave em Português: ShellSort; Algorithm Complexity; Empirical Method; Algoritmos; Complexidade de Algoritmos; Método Empírico; CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO
• Link de acesso: http://www.bdtd.uerj.br/handle/1/7668

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.