¿Cómo verificar y agregar de manera eficiente si un elemento no existe en una lista anidada?

Un poco codicioso:

cleansed_lists = [[word for word in sentence if word != '+'] for sentence in nested_list]
result = []
for sentence in cleansed_lists:
    new_list = ['+'] * (2 * len(sentence) - 1)
    new_list[::2] = sentence
    result.append(new_list)

Complejidad del tiempo:

Suponga que Nes la longitud de su lista externa y nes la longitud promedio de cada una de sus listas internas (sus oraciones).

Línea 1 : iteramos a través de la lista externa una vez y cada lista interna una vez, usando operaciones O (1) (es decir if word != '+'). Por lo tanto, la línea 1 tiene una complejidad temporal de O (n * N) .

Líneas 3-6 : iteramos a través de nuestra lista externa una vez (Línea 3), el equivalente a una lista dos veces el tamaño de nuestra lista interna (Línea 4), y todos los demás elementos de una lista dos veces el tamaño de nuestra lista interna (Línea 5). Esto produce una complejidad de tiempo de O (N * (2n + n)) , que se simplifica a O (n * N) .

= O(n*N) + O(N*(2n+n))
= O(n*N) + O(N*3n)
= O(n*N) + O(N*n)
= O(n*N)

Por tanto, la complejidad final es O (n * N) .