¿Cuál es la complejidad esperada del tiempo de verificar la igualdad de dos cadenas arbitrarias?

Question

La respuesta simple (ingenua?) sería O (N) donde N es la longitud de la cadena más corta. Porque en el peor de los casos, debe comparar cada par de caracteres.

tan bueno. Creo que todos podemos estar de acuerdo en que la comprobación de la igualdad de dos la misma longitud se requiere o (n) Tiempo de ejecución.

Sin embargo, muchos (más?) Idiomas (estoy usando Python 3.7) Almacene las longitudes de las cadenas para permitir las constantizaciones de tiempo constante. Por lo tanto, en el caso de dos longitud desigual cadenas, simplemente puede verificar simplemente len(string_1) != len(string_2) en tiempo constante. Puedes verificar que Python 3 realiza esta optimización.

Ahora, si estamos comprobando la igualdad de dos verdaderamente cadenas arbitrarias (de longitud arbitraria), es mucho más probable (infinitamente, creo) que las cadenas serán de longitud desigual que de igual longitud. Que (estadísticamente) garantiza que casi siempre podamos compararlos en un tiempo constante.

Para que podamos comparar dos cadenas arbitrarias en el promedio de O (1), con un peor caso muy raro de O (n). ¿Deberíamos considerar que las comparaciones de cadenas sean O (1) de la misma manera que consideramos las buscaplas de la tabla de hash para ser O (1)?

Answer 1

Para discutir la complejidad del tiempo esperado de una operación, debe especificar una distribución en las entradas, y también explique lo que quiere decir con $ n $ .

uno tiene que tener cuidado, sin embargo. Por ejemplo, considere la sugerencia en los comentarios, para considerar algún tipo de distribución sobre palabras de longitud como máximo 20. En este caso, la comparación de cadenas es claramente $ O (1) $ , ya que 20 es solo una constante. Hay varias formas de evitarlo:

• Pregunte por una complejidad de tiempo no asintótica. Dado que la complejidad del tiempo depende en gran medida del modelo de cálculo, puede contar (por ejemplo) el número de celdas de memoria de entrada a las que se accede.

• Puede especificar una distribución de entrada que depende de un parámetro $ m $ y luego solicite la complejidad asintótica en términos de $ m $ .

Aquí hay un ejemplo. Dadas dos cadenas binarias aleatorias de longitud $ n $ , habrá aproximadamente 4 accesos en la expectativa. En contraste, si las cadenas se eligen al azar de la colección $ 0 ^ i1 ^ {ni} $ , el número de accesos será aproximadamente $ (2/3) n $ . Estas dos distribuciones se pueden separar, incluso si usamos la notación asintótica: el algoritmo se ejecuta en $ o (1) $ en la primera distribución, y en $ \ theTa (n) $ en el segundo.

Otro problema es el significado de $ n $ . Considere, por ejemplo, una cadena $ 0 ^ m $ , donde $ m \ sim g (1/2) $ Es una variable geométrica aleatoria. Cuando se ejecuta en las entradas de longitudes $ a, b $ , el tiempo de ejecución es $ \ theTa (\ min (a, b )) $ . ¿Cómo deberíamos expresar esto en términos de $ n= a + b $ ? Una opción es solicitar el tiempo de funcionamiento esperado dado que la longitud de entrada es $ n $ . En este 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) \ aprox \ frac {n} {4}, $$ por lo que el tiempo de ejecución esperado es $ \ theta (n) $ .