An1lise e Projeto de Algoritmos

Apuntes

Análise e Projeto de Algoritmos Márcia Cappelle e Erika Coelho com slides (adaptados) dos Profs. Humberto Longo e Hugo Nascimento Instituto de Informática Universidade Federal de Goiás 2023 INF/UFG – APA 2023 – M. Cappelle & E. Coelho (1 – 1 de 831) Seleção em um conjunto Definições I A i -ésima estatística de ordem de um conjunto de n elementos é o i -ésimo menor elemento. I O mínimo de um conjunto é a primeira estatística de ordem ( i = 1 ); I O máximo é a n -ésima estatística de ordem ( i = n ); I Informalmente a mediana é o ponto “médio” do conjunto. INF/UFG – APA 2023 – M. Cappelle & E. Coelho Seleção (407 – 426 de 831) Seleção em um conjunto Definição I Entrada: I Conjunto A de n números (distintos) e um número i , com 1 ≤ i ≤ n . I Saída: I Elemento x ∈ A maior que exatamente i − 1 outros elementos de A . I Seleção( i ): I elemento mínimo → i = 1 . I elemento máximo → i = n . I mediana → i =? Mediana I i -ésimo menor elemento, para i = b n +1 2 c e i = d n +1 2 e . I n ímpar → i = n +1 2 . I n par → i = n 2 e i = n 2 + 1 . INF/UFG – APA 2023 – M...