Por que tamanhos de entrada maiores implicam em instâncias mais difíceis?

12

Abaixo, suponha que estamos trabalhando com uma máquina de Turing com fita infinita.

Ao explicar a noção de complexidade de tempo a alguém e por que ela é medida em relação ao tamanho de entrada de uma instância, deparei-me com a seguinte afirmação:

[..] Por exemplo, é natural que você precise de mais etapas para multiplicar dois números inteiros com 100000 bits do que, digamos, multiplicar dois números inteiros por 3 bits.

A alegação é convincente, mas de alguma forma, acenando com a mão. Em todos os algoritmos que deparei, quanto maior o tamanho da entrada, mais etapas você precisará. Em palavras mais precisas, a complexidade do tempo é uma função monotonicamente crescente do tamanho da entrada.

Será que a complexidade do tempo é sempre uma função crescente no tamanho da entrada? Se sim, por que é esse o caso? Existe uma prova disso além do acenar com a mão?

Kaveh
fonte
"Diretamente proporcional" tem um significado matemático específico que significa tempo essencialmente linear. Em outras palavras, se sua entrada tiver tamanho , se o tempo for diretamente proporcional, o algoritmo será executado no tempo . Eu imagino que não é isso que você quer dizer, pois muitos algoritmos não são executados em tempo linear, ou seja, classificação. Você pode explicar mais? c nncn
SamM 13/08/12
Então você está perguntando sobre um algoritmo que é executado em tempo? significa que o algoritmo é executado ao mesmo tempo, independentemente do tamanho da entrada,O ( 1 ) o ( 1 ) significa que corre mais rápido à medida que a entrada aumenta. Eu não consigo pensar em um que seja executado no topo da minha cabeça, mas a notação é bastante comum porque um algoritmo geralmente é executado em algo como O ( n 2 ) + o ( 1 ) tempo - em outras palavras , leva tempo O ( n 2 ) e existem outros termos que ficam menores à medida que a entrada aumenta. o(1)O(1)o(1)O(n2)+o(1)O(n2)
SamM 13/08/12
Boa pergunta. E o contra-exemplo de cálculo dos fatores primos de para alguns c grandes (essa é apenas uma função crescente para n c )? @ Sam Observe que uma função crescente diz que o tempo deve estar diminuindo em algum momento ao longo da linha real (isto é, f ( b ) < f ( a ) , a < b ). c/ncncf(b)<f(uma),uma<b
Casey Kuball
@Darthfett Receio não seguir. Nem todas as funções crescentes estão diminuindo em algum momento ao longo da linha real.
SamM 13/08/12
@ Jennifer Sim, eu entendo, isso faz sentido. Eu recomendo usar o termo , pois tem o significado que você está procurando. E gostaria de enfatizar que a proporcionalidade direta implica linearidade; Entendo o que você está dizendo, mas pode ser confuso para quem está lendo a pergunta pela primeira vez. o(1)
SamM 13/08/12

Respostas:

12

É o caso de que a complexidade do tempo é sempre uma função crescente no tamanho da entrada? Se sim, por que é esse o caso?

Não. Considere uma máquina de Turing que pare após etapas quando o tamanho de entrada n for par e pare após n 2 etapas quando n for ímpar.nnn2n

Se você quer dizer a complexidade de um problema , a resposta ainda é não. A complexidade do teste de primalidade é muito menor para números pares do que para números ímpares.

JeffE
fonte
4

É o caso de que a complexidade do tempo é sempre uma função crescente no tamanho da entrada? Se sim, por que é esse o caso? Existe uma prova disso além do acenar com a mão?

Deixe denotar o tamanho da entrada. Para ler toda a entrada, uma máquina de turing já precisa de n etapas. Portanto, se você assumir que um algoritmo deve ler toda a entrada (ou n / c para alguma constante c ), sempre terá pelo menos tempo de execução linear.nnn/cc


O problema com a definição de algoritmos com uma "função de tempo de execução que diminui monotonicamente" é que você precisa definir o tempo de execução para alguma forma. Você precisa configurá-lo para algum valor finito . Mas existem infinitos valores possíveis para n > 1 , então você acaba com uma função que é constante para muitos valores infinitos.n=1n>1


Provavelmente algoritmos sublineares são de seu interesse, que não leem toda a entrada. Veja, por exemplo, http://www.dcs.warwick.ac.uk/~czumaj/PUBLICATIONS/DRAFTS/Sublinear-time-Survey-BEATCS.pdf .

Christopher
fonte
Existem algoritmos sublineares. Por exemplo, consulte people.csail.mit.edu/ronitt/sublinear.html . É um campo razoavelmente novo, mas é muito interessante. Existem outros contra-exemplos para isso. Encontrar um elemento com uma lista classificada leva tempo no modelo de RAM. Concordo com a ideia por trás da sua postagem. Não faz sentido que um algoritmo leve menos tempo à medida que a entrada aumenta, porque não tem tempo para ler toda a entrada (como é que isso leva menos tempo?). Mas eu não sei como provar que eles não existem, e que um truque não poderia fazê-lo o ( 1 ) . O(registron)o(1)
SamM 14/08/12
@ Sam: Desculpe, eu não vi seu comentário antes da minha edição (adicionando algoritmos sublineares).
Christopher
muito pelo contrário; Não vi sua edição antes de adicionar meu comentário. Gostaria de excluí-lo, mas a segunda metade ainda se aplica e um link adicional não pode prejudicar o OP
SamM
1
um contraexemplo: uma função constante como . O que você descreve funciona para funções que precisam ler suas entradas. f(x)=0 0
Kaveh
1

(N,)Ω(1)

Dito isto, os tempos de execução médios podem conter componentes oscilantes, por exemplo, o Mergesort .

Rafael
fonte
Não vejo como essa resposta está relacionada à pergunta.
A.Schulz
@ A.Schulz Ele prova a questão principal "É o caso de que a complexidade do tempo é sempre uma função crescente no tamanho da entrada?", Lendo "crescente" como "não decrescente", ou seja, não aumentando estritamente.
Raphael
1
@ A.Schulz: Ainda assim, minha interpretação parece ser a que Jennifer está interessada .
Raphael