A Análise Computacional do Problema da Seleção

UNIVERSIDADE DE SÃO PAULO-USP

ESCOLA DE ARTES, CIÊNCIAS E HUMANIDADES - EACH

INTRODUÇÃO A ANÁLISE DE ALGORITMOS - IAA

 

                     Guilherme Jose da Silva Nascimento

                                   NºUSP: 12543252

 

                          Exercício de Programação I - EP1

 Tema: Problema da Seleção

 

 

 

 

 

 

SÃO PAULO

        Novembro / 2021

SUMÁRIO

 

1-INTRODUÇÃO.................................................................3

2-OBJETIVOS....................................................................12

3-RESULTADOS………....................................................14

4-CONCLUSÃO..................................................................17

5-REFERÊNCIAS...............................................................18

---

1-  INTRODUÇÃO

Este relatório consiste na análise de dois algoritmos que a priori seriam possíveis soluções para o problema da Seleção. O problema da Seleção consiste na elaboração de um algoritmo que receba como valores de entrada: Um Array de números inteiros contendo ‘n’ elementos e um número inteiro ‘i’, tal que i deverá ser um valor entre 0 e n - 1 (Em pseudo código ou para linguagens como FORTRAN, o valor de i variaria entre 1 e n, esta diferença se dá pela diferente sintaxe da maneira como um elemento de um array é utilizado).

O algoritmo para o problema da Seleção deve retornar o i-ésimo menor elemento do array em questão, sendo este array ordenado ou não. Esse algoritmo para Seleção é deveras interessante podendo ser usado para estudo estatísticos de diferentes espaços amostrais  facilitando encontrar a mediana e os valores extremos de um determinado conjunto. Para a resolução deste problema temos dois algoritmos em pseudocódigo para se analisar e averiguar se resolvem o problema explicado e qual desses dois seria a solução mais eficiente em relação ao seu tempo de processamento. Os dois pseudocódigos de solução são:

Selecao1 ( A , i )

1- Ordene( A )

2- return ai

---

Selecao2 ( A , i )

1- q ← Particao( A )

2- if n = 1

3-        then return a1

4- if i < q

5-        then return Selecao2 ( A[ 1 : q - 1] , i )

6- else if i > q

7-        then return Selecao2 ( A[ q + 1 : n] , i - (q + 1) )

8- else return aq

Para a análise dessa situação iremos adaptar os pseudocódigos para linguagens que possam ser compiladas ou interpretadas, realizaremos testes para primeiro, atestar se o algoritmo de fato soluciona o problema da seleção, e  segundo analisar o tempo de execução de cada algoritmo para se concluir qual é mais eficiente

Para a “tradução” dos pseudocódigos apresentados usaremos da linguagem de programação interpretada Python, mais especificamente em sua versão 3.8.9, em uma computador pessoal Windows 7 Ultimate com 4Gb de RAM  e com processador Intel Pentium Dual CPU E2160 1.80Ghz, usando da IDE Visual Studio Code versão 1.56.2.

No algoritmo da Selecao1 temos uma estrutura bem simples, o array é primeiramente reorganizado sendo ordenado em ordem crescente, uma vez que este array está ordenado se retorna o elemento  A[i] (Para linguagens em que o array vai de 1 até n) para saber qual é o i-ésimo menor elemento do array. O tempo de processamento deste algoritmo em questão depende muito do tipo de ordenação escolhida, em nosso caso usaremos um algoritmo de ordenação de alta eficiência com tempo de processamento  equivalente a Θ(n.lg(n)) em caso médio,  se considerarmos o tempo de ‘return’ como ‘c1’, teríamos um tempo de processamento próximo de Θ(n.lg(n)) + c1.

 

Código da Selecao1 em Python:

def mergeSort(Array):

    if len(Array) > 1:

        mid = len(Array) // 2

        left = Array[:mid]

        right = Array[mid:]

        mergeSort(left)

        mergeSort(right)

        i = 0

        j = 0

        k = 0

        while i < len(left) and j < len(right):

            if left[i] <= right[j]:

              Array[k] = left[i]

              i += 1

            else:

                Array[k] = right[j]

                j += 1

            k += 1