Está correto ou incorreto dizer que uma entrada diz que $ c $ causa um tempo médio de tempo de um algoritmo?

Question

Eu estava passando pela introdução de texto ao algoritmo por Cormen ET. al. onde me deparei com um trecho que eu senti exigido um pouco de esclarecimento.

Agora, tanto quanto eu soube que, enquanto o melhor caso e pior caso complexidades de tempo de um algoritmo surgem para uma determinada entrada física ao algoritmo (digamos que um entrada $ a $ faz com que o pior caso tempo de execução para um algoritmo ou diga uma entrada $ B $ faz com que o O melhor tempo de execução de um algoritmo, assintoticamente), mas não há tal entrada física que causa o tempo médio de tempo de execução de um algoritmo como o tempo médio de execução de um algoritmo é por sua definição O tempo de execução do algoritmo em média sobre todas as entradas possíveis . É algo que espero que só exista matematicamente.

Mas, por outro lado, insumos para um algoritmo que não são a melhor entrada de caso, nem a pior entrada de caso deve estar em algum lugar entre os extremos e o desempenho de nosso algoritmo é medido neles por ninguém menos que a média Complexidade de tempo de caso como a complexidade média do tempo do algoritmo está entre as piores e as melhores complexidades de caso, assim como nossa entrada entre os dois extremos.

Está correto ou incorreto dizer que uma entrada diz $ c $ causa um tempo médio de tempo de um algoritmo?

O trecho do texto que me fez fazer essa pergunta é a seguinte:

.

no contexto da análise do QuickSort,

No caso médio, a partição produz uma mistura de divisões "boas" e "ruins". Em uma árvore de recursão para uma execução média de caso de partição, as coisas boas e ruins são distribuídas aleatoriamente por toda a árvore. Suponha, por uma questão de intuição, que o bom e ruim divide os níveis alternativos na árvore, e que as boas divisões são divisões de casos e as divisões ruins são piores divisões. A figura (a) mostra as divisões a dois níveis consecutivos na árvore de recursão. Na raiz da árvore, o custo é $ n $ para particionamento, e os subarrays produzidos têm tamanhos $ n- 1 $ e $ 0 $ : o pior caso. No próximo nível, a subarray de tamanho $ n- 1 $ sofre particionamento melhor caso em subarrays de tamanho $ (n -1) / 2 - 1 $ e $ (n-1) / 2 $ vamos supor que o custo de condição limite é $ 1 $ para a subarray de tamanho $ 0 $ .

A combinação da divisão ruim seguida pela boa divisão produz três sub-matrizes de tamanhos $ 0 $ , $ ( n-1) / 2 - 1 $ e $ (N-1) / 2 $ a um custo de particionamento combinado de $ \ theta (n) + \ theta (n-1)=theta (n) $ . Certamente, esta situação não é pior do que na figura (b), nomeadamente um único nível de particionamento que produz dois subarrays de tamanho $ (N-1) / 2 $ , a um custo de $ \ theta (n) $ . No entanto, esta última situação é equilibrada!

Answer 1

o tempo médio de execução de um algoritmo com relação a alguma distribuição $ D $ é, por definição , o tempo de execução esperado do algoritmo quando executado em uma entrada amostrada de acordo com $ D $ .

Isso deve ser contrastado com o tempo de execução de pior caso , que é o tempo máximo de funcionamento em qualquer entrada Qualquer de um determinado comprimento, e melhor caso em execução tempo , que é o tempo mínimo de funcionamento em qualquer entrada de comprimento determinado.

Como o tempo de execução do pior e melhor caso é definido como máximo e mínimo, existem insumos atingindo-os. O tempo médio de execução é uma expectativa, e por isso não tem sentido falar sobre uma entrada atingindo-os.

Se você jogar um dado, o número esperado que você recebe é 3.5. Isso não é alcançado por qualquer lançamento em particular. Se o dado tivesse 5 lados, o número esperado é 3, o que corresponde a algum lance, mas isso não significa que o lance seja "caso médio".

---

.

O que às vezes acontece é que você pode isolar uma classe de insumos $ x $ tal que, quando executado em uma entrada da $ X $ , o tempo de execução do algoritmo está dentro de um fator constante do tempo médio de execução (para que isso faça sentido, $ x $ Deve realmente corresponder a uma sequência $ x_n $ de entradas de cada comprimento, ou pelo menos infinitamente muitos comprimentos). Você pode dizer que $ x $ "alcança" o tempo de execução esperado do algoritmo.