Qual é a complexidade de tempo esperado de verificar a igualdade de duas cordas arbitrárias?

Question

A resposta simples (ingênua?) seria O (n) onde n é o comprimento da string mais curta. Porque no pior caso você deve comparar todos os pares de caracteres.

até agora tão bom. Acho que todos podemos concordar que verificando a igualdade de dois igual comprimento strings requer o (n) tempo de execução.

No entanto, muitos (mais?) Idiomas (estou usando o Python 3.7) armazene os comprimentos de strings para permitir a pesquisa de tempo constante. Assim, no caso de duas strings desiguais , basta verificar a len(string_1) != len(string_2) em tempo constante. Você pode verificar se o Python 3 de fato faz essa otimização.

Agora, se estamos verificando a igualdade de duas strings arbitrárias em verdadeiras (de comprimento arbitrário), então é muito mais provável (infinitamente, eu acredito) que as cordas serão de um comprimento desigual do que de igual comprimento. Que (estatisticamente) garante que possamos quase sempre compará-los em tempo constante.

para que possamos comparar duas cadeias arbitrárias em O (1) média, com um pior-caso muito raro de O (n). Devemos considerar as comparações de strings então para ser O (1) da mesma forma que consideramos pesquisas de mesa de hash para ser O (1)?

Answer 1

Para discutir a complexidade de tempo esperado de uma operação, você deve especificar uma distribuição nas entradas e também explicar o que você quer dizer com $ n $ .

é preciso ter cuidado, no entanto. Por exemplo, considere a sugestão nos comentários, para considerar algum tipo de distribuição sobre as palavras de comprimento no máximo 20. Neste caso, a comparação de string é claramente $ O (1) $ , já que 20 é apenas uma constante. Existem várias maneiras de evitá-lo:

• Peça uma complexidade de tempo não assintótica. Como a complexidade do tempo é altamente dependente do modelo de computação, você pode contar (por exemplo) o número de células de memória de entrada acessadas.

• Você pode especificar uma distribuição de entrada que depende de um parâmetro $ m $ e, em seguida, peça a complexidade assintótica em termos de $ m $ .

Aqui está um exemplo. Dadas duas cadeias binárias aleatórias de comprimento $ n $ , haverá aproximadamente 4 acessos na expectativa. Em contraste, se as cordas forem escolhidas aleatoriamente a partir da coleção $ 0 ^ i1 ^ {ni} $ , o número de acessos será aproximadamente $ (2/3) n $ . Essas duas distribuições podem ser separadas mesmo se usarmos notação assintótica: o algoritmo é executado em $ o (1) $ na primeira distribuição, e na matemática $ \ theta (n) $ no segundo.

Outra questão é o significado de $ n $ . Considere, por exemplo, uma string $ 0 ^ m $ , onde $ m \ sim g (1/2) $ é uma variável aleatória geométrica. Quando executar em entradas de comprimentos $ a, B $ , o tempo de execução é $ \ theta (\ min (A, B )) $ . Como devemos expressar isso em termos de $ n= A + B $ ? Uma escolha é pedir o tempo de execução esperado, dado que o comprimento de entrada é $ n $ . Nesse caso, $$ \ mathbb {e} [\ min (a, b)]=sum_ {a= 1} ^ {n-1} \ frac {(1/2) ^ a (1/2) ^ {n-1-a }} {\ sum_ {a '= 1} ^ {n-1} (1/2) ^ {a'} (1/2) ^ {n-1-a '}} \ min (A, nA)=FRAC {1} {n-1} \ sum_ {a= 1} ^ {n-1} \ min (a, na) \ appar \ frac {n} {4}, $$ então o tempo de execução esperado é $ \ theta (n) $ .