Paradigmas para análise de complexidade de algoritmos

16

A análise de casos piores e médios são medidas bem conhecidas para a complexidade de um algoritmo. A análise suavizada recentemente surgiu como outro paradigma para explicar por que alguns algoritmos exponenciais no pior dos casos funcionam tão bem na prática, por exemplo, o algoritmo simplex.

Minha pergunta é - existem outros paradigmas para medir a complexidade de um algoritmo? Estou particularmente interessado naqueles que tentam explicar por que alguns algoritmos que apresentam uma complexidade de pior caso funcionam bem na prática.

Optar
fonte

Respostas:

21

Existem variantes naturais da análise de pior caso que também são úteis. Talvez o mais famoso seja a complexidade parametrizada. Aqui, consideramos uma medida "bidimensional": o comprimento de entrada usual e algum número inteiro não negativo adicional k , o parâmetro Embora um algoritmo possa ser executado horrivelmente no pior dos casos (para todos os valores de n e k ), pode ser que todos os casos em um aplicativo que precisam ser resolvidos, esse parâmetro k seja baixo, portanto o algoritmo funcione bem nessas instâncias.nknkk

Por exemplo, suponha que você queira resolver o Conjunto Independente Máximo em alguma classe de gráficos e desenvolva um algoritmo interessante que seja surpreendentemente rápido. Investigando mais detalhadamente a classe de gráficos em si, você descobre que todos os gráficos examinados têm uma largura de árvore no máximo . Bem, Bodlaender (cf. Neidermeier [1]) mostrou que quando a largura da árvore é k, o Max Independent Set é um parâmetro fixo tratável : pode ser resolvido no tempo O ( 2 k ( | E | + | V | ) ) . Isso fornece algumas explicações sobre por que seu algoritmo funciona bem.10O(2k(|E|+|V|))

[1] R. Niedermeier, convite para algoritmos de parâmetro fixo. Série de Palestras de Oxford em Matemática e suas Aplicações, Oxford University Press, Oxford, 2006.

Ryan Williams
fonte
15

Há complexidade amortizada - por que algumas operações podem ser caras no pior dos casos, mas se você considerar muitas operações, o custo médio por operação é bom.

Um exemplo clássico é uma estrutura de dados que se esvazia quando está cheia, copiando todos os seus elementos para algum armazenamento. A operação de cópia pode ser cara, mas isso não acontece com freqüência - é necessário inserir elementos suficientes na estrutura de dados para provocá-la.

Dana Moshkovitz
fonte