A complexidade espacial do reconhecimento dos palíndromos de Watson-Crick

10

Eu tenho o seguinte problema algorítmico:

Determinar o espaço Turing complexidade de reconhecer seqüências de DNA que são palíndromos Watson-Crick.

Os palíndromos de Watson-Crick são cadeias cujo complemento invertido é a cadeia original. O complemento é definido em letras, inspirado no DNA: A é o complemento de T e C é o complemento de G. Um exemplo simples de um palíndromo da WC é o ACGT.

Eu vim com duas maneiras de resolver isso.

É necessário espaço.O(n)

  • Quando a máquina terminar de ler a entrada. A fita de entrada deve ser copiada para a fita de trabalho na ordem inversa.
  • A máquina lerá a entrada e as fitas de trabalho da esquerda e comparará cada entrada para verificar se a célula na fita de trabalho é o complemento da célula na entrada. Isso requer espaço.O(n)

O outro requer espaço .O(logn)

  • Enquanto lê a entrada. Conte o número de entradas na fita de entrada.
  • Quando a fita de entrada terminar de ler
    • copie o complemento da carta na fita de trabalho
    • copie a letra L para o final da fita de trabalho
  • (Ponto de loop) Se o contador = 0, limpe a área de trabalho e escreva yes, então pare
  • Se a fita de entrada indicar L
    • Mova a cabeça de entrada para a esquerda pelo número de vezes indicado pelo contador (requer um segundo contador)
  • Se a fita de entrada indicar R
    • Mova a cabeça de entrada para a direita pelo número de vezes indicado pelo contador (requer um segundo contador)
  • Se a célula que contém o valor na fita de trabalho corresponder à célula atual na fita de entrada
    • diminuir o contador em dois
    • Mova um para a esquerda ou para a direita, dependendo de R ou L estar na pasta de trabalho, respectivamente
    • copie o complemento de L ou R para a pasta de trabalho no lugar do atual L ou R
    • continue o loop
  • Se os valores não corresponderem, limpe a fita de trabalho e escreva não, pare

Isso resulta em cerca de espaço para armazenar os dois contadores, o complemento atual e o valor L ou R.2registron+2

Meu problema

O primeiro requer tempo e espaço linear. O segundo requer tempo elognespaço. Recebi o problema da citação e criei essas duas abordagens, mas não sei qual delas seguir. Eu só preciso dar a complexidade espacial do problema.n22registron

A razão pela qual estou confuso

Eu diria que a segunda é a melhor opção, já que é melhor em termos de tempo, mas essa resposta só vem da minha sorte e da criação de um algoritmo. Parece que se eu quiser dar a complexidade espacial de algo, não seria necessário ter sorte com o algoritmo certo. Estou esquecendo de algo? Eu deveria mesmo encontrar uma solução para o problema para responder à complexidade do espaço?

justausr
fonte
Eu acho que a pergunta seria ainda melhor se você desse o pseudocódigo para os algoritmos. Procure aqui ajuda na formatação.
Raphael

Respostas:

8

DSPUMACE(O(1 1))=REGchar

Para mostrar que um problema tem uma complexidade de espaço específica, geralmente é necessário criar um algoritmo que tenha essa complexidade de espaço. Isso pode exigir tentativa e erro, mas uma abordagem melhor é ter um bom entendimento do problema que você está procurando e uma boa experiência em algoritmos e complexidade.

O(n2)

Dica: por que usar espaço adicional, quando você pode usar o espaço ocupado pela entrada?

Dica: percorra a string verificando um caractere de cada vez - use o estado da Máquina de Turing para lembrar qual personagem você está verificando e apagando os caracteres que você já verificou.

Dave Clarke
fonte
isso é o que meu segundo algoritmo faz. Para ir e voltar através de uma sequência, você precisa de contadores. Para uma entrada de comprimento, é necessário espaço n de log para armazenar o contador. A menos que eu sou mal-entendido, mas parece que você não podia ir e voltar do outro lado da corda, sem manter o controle de qual parte foi comparado
justausr
3
Por que você precisa armazenar um balcão?
31412 Dave
Se eu chegar ao final da entrada e tiver 10 caracteres. Preciso voltar 10 caracteres e salvar qual foi o último caractere na entrada. Quando chego ao início, comparo e copio o segundo caractere e movo para a direita 7 vezes e verifico se o segundo caractere corresponde ao nono. Como sei que são 7 vezes, a menos que eu esteja acompanhando?
justausr
11
A cabeça pode estar apenas em um lugar da fita por vez, mas o estado da TM pode lembrar o que a cabeça viu e pode-se marcar a fita com outros caracteres para indicar quais partes da fita já foram visitadas ( em certas fases do algoritmo).
58512 Dave
11
Não entendo o que você quer dizer. Se você estiver apagando ou marcando os caracteres no fluxo de entrada (com a mesma marca), poderá determinar facilmente quando terminar de processar a sequência de entrada porque a sequência de entrada ficou sem.
58512 Dave
3

Da maneira como a pergunta é feita, você deve criar um limite superior e um limite inferior na complexidade do espaço.

O(registron)

umaeub2euumaeueuω(1 1)O(registron)

cΓs(n)nΓs(n)Ω(registron)


Observe que você não precisa se preocupar com o complemento de letras, pois essa operação é trivial; portanto, tudo o que funciona em palíndromos comuns pode ser modificado com mais alguns estados para resolver seu problema.

frafl
fonte
0

SΩ(n2/S)

Tempo×Espaço=Ω(n2).
TS=Θ(n2)TS=Θ(n2registron)Ω(registron)O(n2/registron)SΩ(n2/S)
Yuval Filmus
fonte