Existem problemas que ficam mais fáceis à medida que aumentam de tamanho?

62

Essa pode ser uma pergunta ridícula, mas é possível ter um problema que realmente fica mais fácil à medida que as entradas aumentam de tamanho? Duvido que quaisquer problemas práticos sejam assim, mas talvez possamos inventar um problema degenerado que possua essa propriedade. Por exemplo, talvez comece a "se resolver" à medida que aumenta, ou se comporta de alguma outra maneira bizarra.

algorithms asymptotics dsaxton
fonte

7

Um problema real com essa propriedade que vem à mente é o quebra de hash de senha sem sal quando é formulado como "dado n hashes, quebre pelo menos um hash". Como a velocidade de craqueamento escalaria linearmente com n, o tempo de execução seria proporcional a 1 / n - exceto que não podemos realmente atribuir um tempo definitivo, pois o craqueamento é estocástico e não possui um limite superior constante no tempo.

amon

1

@amon O tempo de duração não é igual a . Leva tempo apenas para ler os hashes que você recebeu como entrada!

1 / n

$1/n$

n

$n$

n

$n$

David Richerby

3

Você quer dizer mais fácil em termos absolutos ou relativos? Quais medidas de custo você permite? Você precisa de um custo estritamente decrescente ou não aumenta (de algum ponto em diante) o suficiente?

Raphael

2

@DavidRicherby Neste exemplo, é legítimo ignorar o custo da leitura da entrada, desde que eu não faça nenhuma declaração sobre o custo absoluto. Em vez disso, a velocidade aumenta linearmente com a entrada. Portanto, n • T (1)> T (n) mesmo ao considerar o custo de leitura da entrada. Ou seja, para esse problema, é mais fácil resolver uma entrada grande de uma só vez, em vez de dividir a entrada, mesmo que o problema seja divisível. Não estou dizendo que T (n)> T (n + 1) para todos os n.

amon

4

Para todos que desejam postar mais uma resposta do formulário, "Algum problema em que a entrada é uma pergunta, além de várias dicas sobre a resposta": isso não funciona. As entradas mais difíceis de comprimento são aquelas em que você usa todos os bits para fazer a pergunta e não fornece dicas. O fato de ser fácil lidar com perguntas curtas com muitas dicas não significa que o pior dos casos seja bom.

n

$n$

n

$n$

precisa saber é o seguinte

39

Não, não é possível: pelo menos, não em um sentido assintótico, onde você exige que o problema continue ficando estritamente mais fácil, para sempre, como . $n \to \infty$

Seja o melhor tempo de execução possível para resolver esse problema, onde é o tamanho da entrada. Observe que o tempo de execução é uma contagem do número de instruções executadas pelo algoritmo, portanto, ele deve ser um número inteiro não negativo. Em outras palavras, para todos os . Agora, se considerarmos uma função , veremos que não existe uma função que diminua estritamente monotonicamente. (Seja o que for , ele deve ser finito, digamos ; mas, como é monotonicamente estritamente decrescente, e $T(n)$ $n$ $T(n) \in \mathbb{N}$ $n$ $T: \mathbb{N} \to \mathbb{N}$ $T(0)$ $T(0)=c$ $T$ $T(c) \le 0$ $T(c+1) \le -1$ , o que é impossível.) Por razões semelhantes, não há função que esteja assintoticamente estritamente diminuindo: podemos provar da mesma forma que não há função de tempo de execução onde exista modo que, para todos os , é monotonicamente estritamente decrescente (qualquer função desse tipo teria que se tornar eventualmente negativa). $T(n)$ $n_0$ $n \ge n_0$ $T(n)$

Portanto, esse problema não pode existir, pela simples razão de que os tempos de execução precisam ser números inteiros não negativos.

Observe que esta resposta cobre apenas algoritmos determinísticos (ou seja, o pior tempo de execução). Não descarta a possibilidade de algoritmos aleatórios cujo tempo de execução esperado diminui estritamente monotonicamente, para sempre. Não sei se é possível que esse algoritmo exista. Agradeço a Beni Cherniavsky-Paskin por esta observação .

DW
fonte

9

Esta é uma boa prova, mas eu discordo da premissa. Em vez de solicitar um tempo de execução estritamente monotônico, a pergunta pode estar mais razoavelmente exigindo uma função em que exista a, b com a <b, de modo que T (a)> T (b), ou seja, sua diminuição não estritamente monotônica. Então, é claro, é possível encontrar funções inteiras adequadas. Mas por que números inteiros? Fiquei com a impressão de que o tempo de execução denotava um tempo, não uma contagem de instruções (exceto, é claro, para máquinas de Turing), e que a expressão T poderia usar operações não inteiras, como log () ou expoentes não inteiros.

amon

2

@amon "tempo de duração indicado, não contagem de instruções" Absolutamente não. O tempo de execução é sempre uma contagem de instruções. Seria impossível pensar em qualquer outra coisa, pois dependeria de muitos detalhes de implementação.

precisa saber é o seguinte

3

Por mais vaga que seja a pergunta, não vejo como ela exclui uma função de custo de, digamos, . Agora, mas para "pequeno" , então o problema "fica mais fácil", relativamente falando. (Os custos absolutos crescem assintoticamente, é claro).

T (n) = n^{2} \cdot (1 + ϵ)^{- n} + n

$T(n) = n^2 \cdot (1+\epsilon)^{-n} + n$

T (n) \sim n

$T(n) \sim n$

T (n) \approx n^{2}

$T(n) \approx n^2$

n

$n$

Raphael

2

@Raphael, não é um problema cada vez mais fácil: aumenta à medida que aumenta, então o problema fica mais difícil à medida que aumenta, uma vez que é grande o suficiente. Na primeira frase da minha resposta, afirmei que nenhum problema pode ficar cada vez mais fácil para sempre. Obviamente, um problema pode ficar mais fácil por um tempo ( pode estar diminuindo por , por exemplo), mas, mas não pode ficar cada vez mais fácil para sempre.

T (n) \sim n

$T(n) \sim n$

T (n)

$T(n)$

n

$n$

n

$n$

n

$n$

T (n)

$T(n)$

n \leq c

$n \le c$

DW

1

Mesmo com tempos inteiros, para um algoritmo aleatório , o tempo esperado (ou qualquer outra medida da distribuição) pode ser fracionário e pode gradualmente se aproximar de alguma constante de cima. [Isto não significa que tais problemas realmente existem, só que a "nenhuma tal função existe" argumento é insuficiente.]

T

$T$

Beni Cherniavsky-Paskin

25

Embora não seja exatamente uma resposta para sua pergunta, o algoritmo de busca por cordas de Boyer-Moore se aproxima. Como Robert Moore diz em sua página da web sobre o algoritmo,

Nosso algoritmo tem a propriedade peculiar de que, grosso modo, quanto maior o padrão, mais rápido o algoritmo vai.

Em outras palavras, de maneira geral, o algoritmo procura por uma instância de uma cadeia de destino em uma cadeia de origem e por uma cadeia de origem fixa, quanto maior a cadeia de destino, mais rápido o algoritmo é executado.

Rick Decker
fonte

10

Indiscutivelmente, o padrão não é o tamanho do problema, mas o comprimento da string que está sendo pesquisada. Como no comentário de David Richerby acima , eu argumentaria que o comprimento do padrão é mais uma dica sobre como resolver o problema (pesquisou a string) do que o próprio problema (ver se um padrão corresponde a uma string de um determinado comprimento) .)

Kevin - Restabelece Monica

4

@ Kevin A declaração sugere que pesquisar um padrão de comprimento em um texto de comprimento é mais rápido do que pesquisar um padrão de comprimento . Observando essas entradas de relação fixa (ou seja, pares de strings), acho que Rick deu uma resposta adequada à pergunta (se não no sentido clássico, assintótico).

\sqrt{n}

$\sqrt{n}$

n

$n$

\log n

$\log n$

Raphael

10

Claramente, do ponto de vista puramente matemático, puramente de algoritmo CS, isso é impossível. Mas, na verdade, existem vários exemplos reais de quando o dimensionamento do seu projeto facilita, muitos dos quais não são intuitivos para os usuários finais.

Direções : quanto mais longas as rotas, às vezes elas ficam mais fáceis. Por exemplo, se eu quiser que o Google Maps me forneça instruções para ir para o oeste 3000 milhas, eu poderia dirigir até a costa oeste - e obter instruções de direção de cross-country. Mas se eu quisesse ir 9.000 milhas a oeste, acabaria com instruções significativamente mais simples: pegar um avião de Nova York a Hokkaido. Oferecer-me uma rota de cross-country que incorpore tráfego, estradas, condições meteorológicas etc. é um pouco difícil algoritmicamente, mas dizer-me para embarcar em um avião e procurar voos em um banco de dados é comparativamente mais simples. Gráfico ASCII de dificuldade vs distância:

           |     /
           |    /
Difficulty |   /                  ____-------
           |  /           ____----
           | /    ____----
            ---------------------------------
                       Distance

Renderização : digamos que eu queira renderizar uma face e renderizar 1000 faces; trata-se de um anúncio em outdoor, portanto, as duas imagens finais devem ter 10000 x 5000 x 5000. Renderizar um rosto de forma realista seria difícil - com a resolução de vários milhares de pixels, é necessário usar máquinas realmente poderosas - mas para a multidão de 1000 rostos, cada rosto precisa ter apenas dez pixels de diâmetro e pode ser facilmente clonado! Provavelmente eu poderia render 1000 faces no meu laptop, mas renderizar uma face realista de 10000px levaria muito tempo e máquinas poderosas. Gráfico ASCII de dificuldade vs. objetos renderizados, mostrando como a dificuldade de renderizar n objetos para uma imagem de um tamanho definido diminui rapidamente, mas depois retorna lentamente:

           | -    
           |- -                     _________
Difficulty |   --      ______-------            
           |     ------      
           |       
            ---------------------------------
                        Objects

Controle de hardware : muitas coisas com hardware ficam muito mais fáceis. "Mover motor X 1 grau" é difícil e / ou impossível, e você precisa lidar com todos os tipos de coisas com as quais não precisaria lidar com "mover motor X 322 graus".

Tarefas de curta duração: digamos que você queira que o item X esteja ativado por (muito pouco tempo) a cada segundo. Ao aumentar a quantidade de tempo que o X é executado, você precisará de um software menos complexo e de um hardware.

Owen Versteeg
fonte

No seu exemplo de "direções", indique exatamente qual é o problema computacional e qual é a instância. Não está claro para mim que seu exemplo de 6 mil milhas é uma instância maior ou apenas um exemplo de uma parte fácil de algo (por exemplo, se eu fornecer um gráfico conectado a um grande gráfico mais um vértice isolado, pedir os caminhos mais curtos em geral é "difícil", mas pedir um caminho mais curto do vértice isolado para qualquer lugar é trivial). Novamente, para o seu exemplo de renderização, qual é o problema computacional real? Qual é a instância contra a qual você está medindo a complexidade?

precisa saber é o seguinte

O exemplo de renderização não parece ser instâncias do mesmo problema: o primeiro é renderizar uma única imagem; o segundo é renderizar muitas imagens pequenas e colar várias cópias dessas imagens em alguma área.

precisa saber é o seguinte

Eu acho que escrever os parâmetros seria o nome das duas cidades en seria o número de caracteres para codificá-las.

Emory

3

Existem casos. São os casos em que o critério de sucesso é uma função dos dados, em vez de tentar encontrar uma única resposta. Por exemplo, processos estatísticos cujos resultados são redigidos com intervalos de confiança podem se tornar mais fáceis.

Um caso particular em que estou pensando é em problemas que têm uma transição de comportamentos discretos para comportamentos contínuos, como fluxos de fluidos. Resolver o pequeno problema com um grau de erro pode envolver a modelagem de todas as interações discretas, o que pode exigir um supercomputador. Os comportamentos contínuos geralmente permitem simplificações sem produzir resultados fora de um limite de erro relacionado.

Cort Ammon
fonte

2

A questão é interessante e ÚTIL, porque nossa filosofia em informática é resolver problemas, quanto mais lemos, mais difícil é. Mas, de fato, a maioria dos problemas apresentados da maneira típica (difícil) pode ser facilmente representada da maneira "fácil"; mesmo sabendo a resposta da DW (que está errada, considerando que fácil não significa mais rápido, significa "menos lento"; portanto, você não precisa encontrar tempos negativos, mas sim encontrar um tempo assintótico).

O truque para encontrar um é colocar a parte da solução como dicas como uma entrada e considerar a entrada do problema como um parâmetro constante.

Exemplo: Qual é o caminho mais longo entre Londres e Paris, evitando visitar duas vezes uma cidade francesa e uma britânica e não visitar outro país? considerando, você tem que ir a Birmingham antes de Ashford, Orleans antes de Versailles, La Rochelle antes de Limoge, etc ...

É claro que esse problema com entradas longas será mais fácil do que com entradas curtas.

Exemplo de uso: imagine um jogo gerenciado pela máquina, e o IA do computador precisa determinar se ele precisa explorar mais a peça para encontrar mais dicas ou então, se é hora de deduzir qual é a melhor decisão a ser assumida .

Juan Manuel Dato
fonte

2

Seu exemplo não funciona. Instâncias que são grandes porque possuem tantas dicas que as dicas determinam uma ordem linear dos vértices do gráfico são realmente fáceis. No entanto, instâncias grandes porque fornecem um gráfico grande, quase sem dicas, são tão difíceis quanto o problema comum do caminho hamiltoniano. Portanto, o pior caso de tempo de execução de qualquer algoritmo que resolva esse problema será pelo menos tão ruim quanto o pior caso de tempo de execução do melhor algoritmo para o caminho Hamiltoniano, o que não parece ser "super fácil".

precisa saber é o seguinte

@ David, sua resposta está completamente incorreta: 1. A entrada não é um gráfico: o gráfico grande é um PARÂMETRO. Portanto, o problema hamiltoniano é convertido em uma constante (muito grande, mas uma constante). 2. A entrada é a solução do problema, portanto: se maior, você está oferecendo uma explicação combinatória das dicas. Uma entrada de uma dica dá uma ajuda, duas dicas a dupla, três dicas ficarão próximas a quatro vezes ..., porque você está eliminando possíveis soluções. Portanto, este não era um hamiltoniano, esta é uma solução de um gráfico específico e o problema é o que fazer com partes das soluções.

Juan Manuel Dato

Eu acho que seu argumento é interessante, já que instâncias maiores são "mais fáceis" em algum sentido, mas acho que a resposta para a pergunta original é, em última análise, "não". Como o gráfico é finito, existem apenas poucas dicas possíveis. Portanto, cada instância pode ser resolvida em tempo constante (por exemplo, usando uma tabela de pesquisa). Embora instâncias maiores sejam (intuitivamente) mais fáceis na visão da ciência da computação (assintótica), todas as instâncias são igualmente difíceis (solucionáveis em tempo constante).

Tom van der Zanden

@ Tom, eu concordo que sua consideração sobre a complexidade será constante, mas o problema é como estamos aceitando as novas dicas: se com nossa filosofia de calcular a entrada longa não for melhor do que uma entrada curta, precisamos mudar nossa filosofia. - porque isso é um fato: entradas longas implicam problemas mais fáceis. Portanto, não podemos trabalhar dessa maneira ... Eu recomendaria o meu livro, mas não tenho reputação ...

Juan Manuel Dato

n \log n

$n\log n$

1

Considere um programa que tenha como entrada o que você sabe sobre uma senha e tente decifrá-la. Eu acho que isso faz o que você quer. Por exemplo:

Nenhuma entrada-> Força bruta rachadura sobre todos os símbolos e uma palavra de qualquer comprimento
Comprimento da senha -> Brute força todos os símbolos em uma palavra desse tamanho
Símbolos contidos -> Reduz a lista de símbolos para verificar
...
Símbolos contidos, incluindo várias ocorrências e comprimento -> Somente permutações de computação
Todos os símbolos na ordem correta -> basicamente se resolveu

Devo acrescentar que isso é um truque, pois o problema declarado dessa forma é inverso ao tamanho da entrada. Você pode deixar de fora uma camada de abstração e dizer que o tamanho da entrada é grande para nenhuma entrada (verifique todos os símbolos e comprimentos de palavras) e pequeno se você digitar a senha correta no início.

Então, tudo se resume em quanta abstração você permite.

RunOrVeith
fonte

2

b

$b$

0

De fato, tenho um problema que fica menor à medida que os dados aumentam. Um dos meus aplicativos registra os atributos de um produto específico, como queijo. Os atributos são, por exemplo, CheeseType, Marca, País, Área, MilkType, etc. Todo mês ou mais, recebo uma lista de novos queijos que entraram no mercado durante esse período, juntamente com seus atributos. Agora, esses atributos são digitados à mão por um grupo de humanos. Alguns cometem erros de digitação ou simplesmente não sabem o valor de todos os atributos.

Quando você faz uma pesquisa no meu banco de dados, tento prever, a partir das estatísticas, o sabor do queijo, com base nesses atributos. O que acontece é que, para cada atributo, acabo com uma faixa de valores; alguns são válidos outros são inválidos. Eliminar ou corrigir esses inválidos só é possível se eu tiver dados suficientes. Trata-se de fazer a diferença entre valores reais e ruído, sem eliminar valores raros, mas válidos.

Como você pode imaginar, com baixo volume, o ruído é muito importante para consertar as coisas corretamente. Se você tem 5 instâncias de Cheddar, 1 de Brie, 1 de Bri e 1 de Chedar, como posso saber qual está correto e qual é um erro de digitação? Com mais volume, os erros de digitação tendem a se manter muito baixos, mas os valores raros obtêm alguns incrementos cruciais, fazendo-os escapar do barulho (respaldado pela experiência). Nesse caso, eu poderia imaginar 50000 Cheddar, 3000 Brie, 5 Bri, 15 Chedar, por exemplo.

Então, sim, alguns problemas se resolvem eventualmente, quando você tem dados suficientes.

chris
fonte

1

Isso falha pelo motivo usual. Uma entrada grande pode ser aquela em que as pessoas falam sobre muitos tipos diferentes de queijo, em vez de uma em que elas falam sobre alguns tipos de queijo, mas algumas delas o digitam incorretamente. Além disso, não está claro que "mais fácil" seja interpretado como "permita maior confiança no resultado".

precisa saber é o seguinte

Este é um problema da vida real (já o tive duas vezes), que não pode ser resolvido com baixa quantidade de dados. Pode, e fica ainda mais fácil distinguir, bons valores de valores errados, à medida que o volume aumenta. Ele tem o mérito de responder à pergunta "Existem problemas que ficam mais fáceis à medida que aumentam de tamanho?" Não importa quantos tipos de queijos surjam, eventualmente, com volume suficiente, eles terão mais "hits" do que os erros de digitação. Isso é cs .stackexchange, não maths, então os problemas são diferentes, e resolvê-los às vezes é simplesmente ter maior confiança nos resultados.

21417 chris

Não é esse também o tipo de premissa do programa de TV Numbers ? Ou pelo menos alguns episódios - eu sei que me lembro especificamente de uma cena em que o matemático observa que o algoritmo que ele está usando para resolver o problema em questão se torna mais eficaz com um conjunto de dados maior.

Dan Henderson

2

"Fica mais eficaz"! = "Fica mais fácil".

precisa saber é o seguinte

-1

Considere o problema NP-completo 3-SAT. Se você continuar aumentando o problema fornecendo entradas do formato x_i = true / false, você acaba convertendo as disjunções individuais em cláusulas de duas variáveis, criando um problema 2-SAT que é decididamente P, ou você simplesmente obtém uma resposta verdadeira / falsa.

No caso em que há redundância nas entradas x_i = true / false (a mesma entrada é fornecida várias vezes ou entradas contraditórias), você pode classificar facilmente as entradas e ignorar os valores redundantes ou relatar um erro se os valores contradizerem.

De qualquer forma, acho que isso representa um problema "realista" que fica mais fácil de resolver à medida que o número de entradas aumenta. O aspecto 'mais fácil' está na conversão de um problema NP-completo em um problema P. Você ainda pode jogar o sistema fornecendo entradas ridículas, de modo que apenas a classificação demore mais do que o bruto forçando o problema.

Agora, um cenário muito interessante seria se estamos dispostos a aceitar T (0) (utilizando a notação de DW na resposta acima) pode ser infinito. Por exemplo, T (0) poderia ser equivalente a resolver o problema de parada de Turing. Se pudéssemos conceber um problema de tal forma que adicionar mais insumos o converta em um problema solucionável, teremos encontrado ouro. Observe que não é suficiente convertê-lo em um problema solucionável assintoticamente - porque isso é tão ruim quanto a força bruta forçar o problema.

v vv cvvcv
fonte

1

Essas entradas específicas ficam mais fáceis. No entanto, quando você considera todas as entradas possíveis, o 3SAT em geral fica significativamente mais difícil à medida que você adiciona mais cláusulas: as entradas rígidas são aquelas que não possuem essas cláusulas de "dica". Se você não permitir entradas gerais, precisará declarar exatamente quais entradas está permitindo.

precisa saber é o seguinte

Primeiro: concordamos que adicionar mais entradas pode aumentar o tempo de execução. Eu digo essencialmente a mesma coisa acima. Segundo, digo claramente que estamos pegando um 3-SAT existente e adicionando apenas entradas do formato x_i = verdadeiro / falso. Acho que isso é claro o suficiente e não preciso fazer mais esclarecimentos. Acho que você está se esforçando para formar a interpretação mais mal interpretada do que escrevi. Por favor, não se incomode.

Vvv cvvcv

1

Não, sério. Que problema computacional você está resolvendo? Um problema computacional é decidir a associação de um conjunto de strings (digamos, um conjunto de fórmulas para evitar aborrecimentos sobre a codificação). Qual é o conjunto de fórmulas para as quais você afirma que decidir se uma fórmula longa está no conjunto é mais fácil do que decidir que uma fórmula curta está no conjunto? Assim que você tentar fazer isso com precisão, tenho certeza de que sua reivindicação será desfeita.

precisa saber é o seguinte

Você pode, por favor, explicitar sua compreensão de 'minha reivindicação'? Assim que você tentar fazer isso com precisão, tenho certeza de que você deixará de desperdiçar largura de banda da Internet.

Vvv cvvcv

Sou um cientista da computação, não um leitor de mentes. Tornar sua reivindicação precisa é seu trabalho, não meu.

precisa saber é o seguinte

-1

A pergunta é: "é possível ter um problema que realmente fica mais fácil à medida que as entradas aumentam de tamanho?" E se as entradas forem recursos a serem usados pelo algoritmo para trabalhar em um trabalho. É do conhecimento geral que quanto mais recursos, melhor. Abaixo está um exemplo, no qual quanto mais houver funcionários, melhor.

$n$
$t$ $p$

$n$

3) Saída:
A saída é o caminho entre as tarefas a serem executadas pelos funcionários. Cada caminho está associado ao número de funcionários que o seguem. Por exemplo:

$n1$
$n2$
$n3$
$n4$
$n5$

4) Solução possível:
Uma solução possível é primeiro calcular o caminho mais curto para os nós mais próximos de A. Esse será um caminho direto. Em seguida, calcule recursivamente o caminho a seguir para cada tarefa visitada. O resultado é uma árvore. Por exemplo:

          UMA
      BC
    DE

$n$ $n1$ $n2$ $n2 \neq 0$

$n=\infty$ $n = 1$

$n$

yemelitc
fonte

6

Obrigado por compartilhar seus pensamentos. Normalmente, na ciência da computação, entende-se que um algoritmo aceita uma sequência de bits como entrada e gera outra sequência de bits. Com esse entendimento padrão, não vejo como essa resposta possa fazer sentido. Se você tem uma noção diferente de algoritmo, acho que ajudaria se você editasse a pergunta para descrever o que você entende por algoritmo (já que parece que você não está usando o termo de uma maneira que corresponda ao uso padrão do método prazo, como eu o entendo).

DW

A entrada pode ser simplesmente um número (o número de recursos). Isso afetará o número de computação extra que o algoritmo terá que passar. Vou editar a resposta para fornecer um exemplo mais concreto.

yemelitc

Obrigado pela sua edição - isso torna muito mais claro. Agora vejo que você não está confundindo o custo de calcular a solução com o custo de executá-la, como eu pensava originalmente. Mas agora estamos na situação usual. Primeiro, leva pelo menos tempo linear para ler a entrada. Segundo, as instâncias difíceis não são aquelas em que você dá uma árvore pequena e um zilhão de pessoas, mas em que você dá uma árvore grande e relativamente poucas pessoas. (Por exemplo, se você me permitir um milhão de bits, escolherei uma árvore com cerca de mil vértices e darei a você cinco pessoas, não uma árvore com cinco vértices e mil pessoas.)

David Richerby

Concordo. Parece que todos nós acabamos criticando bastante, ao contrário do que a pergunta original nos tentou! Mas espero que você entenda minha ideia de 'entrada como recurso': não importa o tamanho do trabalho, quanto mais pessoas, melhor. Ainda no sentido assintótico, você está definitivamente certo, devo apenas culpar os números inteiros não negativos.

yemelitc

Existem problemas que ficam mais fáceis à medida que aumentam de tamanho?

Respostas: