6

Preciso resolver um exercício com o seguinte enunciado:

Como entrada temos um vetor de n elementos, onde cada elemento possui valor entre 0 e k. Além disso temos dois valores inteiros a e b. Devemos responder quantos elementos no vetor de entrada possuem valor no intervalo [a,b]. Projete um algoritmo cuja complexidade seja O(1) para este problema.

Não consigo imaginar nenhum algoritmo com complexidade constante para resolver isso. Os mais rápidos que eu conheço (os de ordenação linear) não atendem pois são de complexidade O(n). Seria possível resolver esse problema com complexidade O(1)? Ou existe um erro no enunciado?

8
  • 2
    Eu não comecei nada ainda porque não pensei em nenhum algoritmo. Os mais rápidos que eu conheço (os de ordenação linear) não atendem pois são de complexidade O(n). Seria possível resolver esse problema com complexidade O(1)? 27/04/2014 às 22:25
  • 4
    Gustavo, bem-vindo ao site. Editei sua pergunta para resolver dois problemas, que levaram aos votos contra e para fechar: (1) as perguntas aqui precisam ser auto-suficientes, e a sua exigia uma visita a um link externo; (2) parecia que você estava pedindo para resolverem sua lição de casa, e pelos seus comentários entendi que o problema é outro, então editei de acordo. Se discordar, você pode alterar novamente, ou reverter minha edição.
    – bfavaretto
    27/04/2014 às 23:10
  • 1
    @PauloMaciel Eu acho que a pergunta não era bem o que parecia, dê uma olhada na edição que fiz.
    – bfavaretto
    27/04/2014 às 23:26
  • 1
    Muito obrigado gente! Eu sou novo aqui e não sabia muito bem como funcionava, muito obrigado pela ajuda e desculpem qualquer coisa! =) 28/04/2014 às 1:14
  • 1
    Eu conheço um algoritmo para realizar o somatório de n números de um vetor qualquer em tempo O(lg n), mas para isso ele precisa de um processo de preparação anterior para montar uma tabela, cujo tempo é O(n). Supondo que o enunciado esteja correto, não seria esse o caso que o professor pede? Pode ser que o algoritmo pedido tenha um tempo de preparação maior do que O(1), mas depois, durante o funcionamento, tem tempo O(1)... Quase como uma tabela de hash funciona? Fiquei curioso agora! 28/04/2014 às 12:35

2 Respostas 2

5

Eu não consigo te dar uma prova matemática rígida, mas eu afirmo com segurança que o que se pede é impossível. Para qualquer caso não trivial:

  • k < 0 (somente admite o vetor vazio com entrada, o retorno é zero)
  • a > k (o retorno sempre é zero)
  • b < 0 (o retorno sempre é zero)
  • b < a (o retorno sempre é zero)
  • a = 0 E b = k (o retorno sempre é n - assumindo que o tamanho do vetor pode ser determinado em tempo constante)

é possível se produzir dois vetores distintos:

  • V + [x], onde x ∈ [a,b]
  • V + [y], onde y ∉ [a,b]

que produzirão resultados diferentes se avaliados por essa função.

Suponha que exista um algoritmo com complexidade O(1). Então, para vetores de tamanho maior ou igual a n0 existe uma constante K tal que o tempo de execução é menor ou igual a K. Seja V o vetor (um dos vetores?) cujo tempo de execução seja o maior de todos (i.e. K), e cujo valor de retorno seja R. Como esse algoritmo avaliaria V + [_]?

  • Se ele não executar nenhuma operação adicional às que ele já executou para avaliar V, então ele não pode dizer deterministicamente se o resultado é R ou R + 1 - já que o elemento adicional pode ser pelo menos x ou y;
  • Se ele executar uma ou mais operações adicionais, então seu tempo de execução é maior do que K (assumindo que uma operação possui tempo de execução maior que zero). Ou seja, o algoritmo não possui ordem de complexidade O(1), como pressuposto.

A propósito, isso também significa que - ao contrário do pressuposto - o vetor V não era de fato aquele que possui o "maior tempo de execução de todos". Na verdade, tal vetor não existe - já que o conjunto de todos os vetores possíveis com elementos de 0 a k é infinito (ainda que enumerável). Qualquer vetor que você eleger como "o maior" pode - conforme demonstrado - dar origem a um vetor cujo tempo de execução seja pelo menos uma operação elementar maior que ele.

O melhor algoritmo que soluciona esse problema terá complexidade de O(n). É inevitável que todos os elementos do vetor sejam visitados ao menos uma vez - seja para comparar, seja pra incluir numa contagem, seja para ser objeto de uma operação aritmética. A menos que haja alguma "pegadinha" que eu não esteja vendo, esse exercício não tem solução...

0

Bom pessoal, muito obrigado. Usei um pouco de cada informação que vocês deixaram aqui para compor minha resposta. No fim dividi ela em dois casos: 1º Considerando que há métodos que irão percorrer e determinar a quantidade de elementos que estão entre [a, b] e chamar meu método de complexidade O(1) passando a quantidade correta. 2º Considerando que a < 0 e b > k, nesse caso meu método de complexidade O(1) retornaria o tamanho do vetor pois todos os elementos estarão nesse intervalo. Irei conversar com o professor sobre essa questão e posto o resultado aqui depois. Muito obrigado mais uma vez.

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .