Algoritmos de programação dinâmica com log no tempo de execução

A maioria dos exemplos clássicos de algoritmos de programação dinâmica possui tempos de execução como ou . Existem exemplos naturais com um tempo de execução ? $n$ $n^2$ $O(n \log n)$

algorithms reference-request dynamic-programming Joe
fonte

Pegue um algoritmo de dividir e conquistar para classificar.

Nicholas Mancuso

@ NicolasMancuso: Divide and Conquer não é programação dinâmica, pois os subproblemas não se sobrepõem.

A.Schulz

@ A.Schulz Na verdade, eles são. A mesma subsequência pode aparecer em vários ramos da recorrência (estou pensando na recorrência do Mergesort). Nós ignorar isso durante a classificação, porque nós não precisamos de mais aceleração; o fato de que precisamos tentar apenas um particionamento para cada entrada e encontrar a solução ótima (classificada) domina o efeito.

Raphael

Respostas:

Um exemplo natural é encontrar a subsequência crescente mais longa de uma sequência de números. As subsequências do candidato podem ser vinculadas na sequência de entrada. Este é um exercício bastante comum e funciona para outros tipos de subsequências. Na verdade, é o exercício 15.4-6 da 3ª edição do Cormen et al. livro também. Para um algoritmo, consulte a Seção 2.2 nestas notas . $n$

Juho
fonte

Para expandir meu comentário:

Enquanto a classificação não está fazendo uma "pesquisa de tabela", lembre-se da definição real de DP:

Método para resolver problemas com subestrutura ideal.

Vemos que uma abordagem de dividir e conquistar para classificar satisfaz isso.

Nicholas Mancuso
fonte

Estou interessado em uma definição mais diferenciada de DP. No seu exemplo, não há sobreposição de subproblemas e nenhuma memorização necessária.

8114 Joe

Até onde eu sei, não existe "a definição real de DP". A terminação "subestrutura ideal" também não é muito precisa. Com relação à afirmação de sua resposta, se você estender a noção de DP para problemas de transformação de dados (geralmente são considerados apenas problemas de otimização e decisão), acho razoável chamar, digamos, a recorrência do Mergesort uma recorrência de DP. É um caso muito especial, pois só precisamos tentar uma partição.

Raphael

O DP naturalmente é ascendente, mas a divisão e conquista é em reverência (também isso não está relacionado à memorização).

Para todos. Concordo que dividir e conquistar não se adapta realmente à forma mais típica de DP. Sempre achei que era um caso especial por questões de tecnicidade (subestrutura ideal, por exemplo, o Princípio de Optimalidade de Bellman). Mas, à luz do comentário de Joe, talvez eu deva oferecer um exemplo mais convincente. ;)

Nicholas Mancuso