Como usar argumentos adversários para seleção e inserção de classificação?

8

Me pediram para encontrar os argumentos do adversário necessários para encontrar os limites inferiores para a seleção e o tipo de inserção. Não consegui encontrar uma referência a ele em nenhum lugar.

Eu tenho algumas dúvidas sobre isso. Entendo que argumentos adversários são geralmente usados ​​para encontrar limites mais baixos para certos "problemas", em vez de "algoritmos".

Eu entendo o problema de fusão. Mas como eu poderia escrever um para seleção e inserção?

user5507
fonte
1
Dica: é muito mais fácil para um adversário enganar um algoritmo conhecido do que todos os algoritmos.
Raphael
@ Rafael Eu sei que é simples, já que o adversário conhece o algoritmo que ele conhece no pior caso em que o algoritmo se comporta. Então, no caso de seleção / inserção, a complexidade é O (n ^ 2), o limite inferior seria esse? Estou um pouco confuso sobre um algoritmo específico. Limite inferior significa o limite inferior no pior dos casos?
user5507
@ user5507: Sim, geralmente argumentos contraditórios são feitos para provar um limite inferior para toda uma classe de problemas, não para um algoritmo específico. Nesse caso, você só precisa especificar a estratégia para o adversário que resulta na entrada do pior caso para esses 2 algoritmos.
Peter
1
"Adversário" significa simplesmente "entrada do pior caso" nessa configuração.
Jeffe

Respostas:

8

Pelo seu comentário, parece que você está confundindo o significado de limites inferiores, limites superiores e notação assintótica. Por exemplo, tome Classificação de inserção. Seu melhor tempo de execução é (isso acontece quando a entrada já está classificada). O pior tempo de execução é (isso acontece quando a entrada está na ordem inversa). Portanto, como o tempo de execução fica entre uma função linear de e uma função quadrática de , você pode dizer que o tempo de execução da Classificação de Inserção é e . É importante entender, neste caso, que você não pode dizer que o tempo de execução éΘ(n)Θ(n2)nnΩ(n)O(n2)Ω(n2). Por quê? Porque existe uma entrada que faz com que o algoritmo seja executado em . No entanto, você pode dizer que o pior caso de execução é , novamente porque existe uma entrada que faz com que o algoritmo seja executado em . No entanto, geralmente usamos a notação para o pior caso, pois estamos interessados ​​em um limite superior do número de operações realizadas pelo algoritmo.O(n)Ω(n2)Ω(n2)O

Agora, vamos pensar em um argumento adversário para a Classificação por inserção (você pode tentar derivar um para a Classificação por seleção aplicando as mesmas idéias).

Considere o algoritmo de Insertion Sort jogando contra um oponente que chamaremos de adversário. O objetivo do adversário é fornecer uma entrada X para o algoritmo que maximize o número de comparações feitas pelo algoritmo. Isso geralmente é analisado no contexto das árvores de decisão . Uma árvore de decisão mostra todas as sequências possíveis de comparações que o algoritmo poderia fazer. Cada nó interno de uma árvore de decisão representa uma única comparação. Os dois filhos de um nó representam os dois resultados da comparação (sim / não ou verdadeiro / falso). Cada folha representa uma saída possível. Para algoritmos de classificação, as folhas são permutaçõesdas chaves. O algoritmo começa na raiz e segue um caminho até uma folha. Em cada nó interno, a resposta para a comparação feita informa ao algoritmo qual nó deve ser visitado a seguir. Quando o algoritmo atinge uma folha, ele gera sua permutação correspondente. O tempo de execução de um algoritmo (visto como uma árvore de decisão) para uma determinada entrada é o número de comparações feitas no caminho da raiz à folha de saída. Agora, o adversário possui uma estratégia simples que funcionará contra qualquer algoritmo de classificação baseado em comparação, incluindo Classificação por Inserção: sempre que o algoritmo faz uma comparação, o adversário escolhe a resposta que eliminará o menor número possível de permutações.

Em geral, devido ao fato de que com elementos existempossíveis permutações, qualquer árvore de decisão para classificação deve ter pelo menossai e, portanto, deve ter profundidade (pela aproximação de Stirling). Para Classificação de Inserção, o adversário pode criar uma entrada específica que faça com que a árvore de decisão correspondente tenha profundidade de pelo menos .nn!n!Ω(log(n!))=Ω(nlogn)Ω(n2)

O algoritmo usa uma matriz para armazenar os elementos de entrada e é baseado na seguinte invariável:A[1..n]

No início de cada iteração do loop for, a sub-matriz consiste nos elementos originalmente em , mas na ordem classificada.A[1..j1]A[1..j1]

Em cada iteração, os elementos em são, por conseguinte, já na ordem de classificação, e o algoritmo analisa e insere-o no seu lugar final, adequado, comparando o valor de contra o valor dos elementos em , começando em e retornando a e assim sucessivamente até que não seja mais o maior no comparação. Os elementos em estão em um estado desconhecido (com relação à ordem de classificação) e serão processados ​​em iterações posteriores.A[1..j1]A[j]A[j]A[1..j1]A[j1]A[j2]A[j]A[j+1..n]

Aqui está a estratégia do adversário. Sabendo que o algoritmo funciona inserindo em seu devido lugar, movendo os elementos em , a estratégia óbvia é maximizar na ésima iteração o número de elementos que devem ser movido para acomodar . Isso é facilmente realizado escolhendo cuidadosamente a entrada para que ela esteja na ordem inversa . De fato, nesse caso, o número de elementos que devem ser movidos em cada iteração é . Isso leva ao pior tempo de execução (determinado pela série aritmética correspondente).A[j]A[1..j1]jA[j]j1Ω(n2)

Massimo Cafaro
fonte
9
tl; dr: A estratégia do adversário é apresentar uma matriz de ordem inversa como entrada e, em seguida, sair na praia em algum lugar, tomar algumas bebidas, talvez aprender a surfar.
Jeffe