¿Esto es complejidad O(n), verdad? Las instrucciones “if” no afectan la complejidad temporal, ¿cierto?
class Solution:
def containsDuplicate(self, nums: List[int]) -> bool:
storing_list = []
counter = 0
for i in nums:
if i in storing_list:
counter += 1
else:
storing_list.append(i)
if counter > 0:
return True
else:
return False
¿Debería funcionar en O(n) verdad? Leetcode está indicando que se excede el límite de tiempo, lo que significa que se ejecuta muy lento. Estoy confundido sobre cuál es el tiempo de ejecución de este algoritmo.
davy.ai
Basado en el código proporcionado, la complejidad temporal de la función
containsDuplicatees de hecho O(n). El bucleforitera a través de cada número en la lista de entradanums, y la instrucciónifverifica si cada número ya está en la listastoring_list. Lastoring_listes una tabla hash, lo que permite una búsqueda en tiempo constante de elementos. Por lo tanto, la complejidad temporal general es O(n).Sin embargo, el hecho de que un algoritmo tenga una cierta complejidad temporal no siempre significa que se ejecutará de manera eficiente en la práctica, especialmente en entradas grandes. En este caso, es posible que la
storing_listse vuelva demasiado grande para un uso eficiente de la memoria, o puede haber otros factores que influyan en el tiempo de ejecución que no son inmediatamente evidentes en el código.También es posible que el límite temporal en Leetcode esté establecido muy bajo, o que el tamaño de entrada utilizado para las pruebas sea mucho mayor de lo esperado. Vale la pena probar el código con varios tamaños de entrada y comparar el tiempo de ejecución para ver si el problema está en el algoritmo o en los parámetros de prueba.