Alternativa più efficiente che controlla se un elenco può essere reso palindromo

Per la mia classe di algoritmi e strutture di dati, devo scrivere un algoritmo più efficiente nel peggiore dei casi del seguente algoritmo:

def algo_X(A):
    i = 0
    j = len(A)-1
    while i < j:
        if A[i] != A[j]:
            k = i + 1
            while k < j:
                if A[i] == A[k]:
                    A[k], A[j] = A[j], A[k]
                    break
                elif A[j] == A[k]:
                    A[k], A[i] = A[i], A[k]
                    break
                else:
                    k += 1
            if k == j:
                return False
        i += 1
        j -= 1
    return True

Questo algoritmo restituisce True se gli elementi della lista passati come argomento possono essere manipolati (scambiati) per creare una nuova lista, che, se si legge da sinistra o da destra, ha lo stesso ordine di elementi (palindrome ). Else restituisce False. Ad esempio, questa lista ['a', 'a', 'b', '2', 'b', 'b', ‘2’] può essere ordinata in modo da avere una lista con gli stessi elementi nelle stesse posizioni, se leggiamo contemporaneamente da sinistra e da destra: ['a', 'b', '2', 'b', '2', 'b', ‘a’] .

Si noti che questa è la mia interpretazione dell'algoritmo, non ci hanno detto cosa avrebbe dovuto fare questo algoritmo.

Se non sbaglio, questo algoritmo, nel peggiore dei casi (e nel caso medio), è O (n ² ), e Ɵ (n) nel migliore dei casi.

L'esercizio indica specificamente che non devo necessariamente modificare l'elenco (come in algo_X ), ma solo per restituire True o False specificando rispettivamente se l'elenco può essere reso palindromo o meno.

Non possiamo usare librerie, ma solo costrutti integrati. Ad esempio, non possiamo nemmeno usare la sezione. Questo perché non "conosciamo" esattamente la complessità temporale di tali funzioni. Modificherò la mia domanda

Per fare un algoritmo migliore nel peggiore dei casi, pensavo di poter usare merge sort , la cui complessità temporale è sempre n * log (n), più un ciclo, che non renderebbe l'algoritmo peggiore, asintoticamente.

Questa è la mia funzione merge per la mia funzione di ordinamento di tipo merge:

def merge(A, B):
    ls = []
    a, b = 0, 0
    while a < len(A) and b < len(B):
        if A[a] <= B[b]:
            ls.append(A[a])
            a += 1
        else:
            ls.append(B[b])
            b += 1
    while a < len(A):
        ls.append(A[a])
        a += 1
    while b < len(B):
        ls.append(B[b])
        b += 1
    return ls

Questa è la mia funzione di ordinamento di tipo merge:

def merge_sort(A):
    if len(A) < 2:  # basic condition
        return A
    L = merge_sort(A[0:len(A)//2])
    R = merge_sort(A[len(A)//2:])
    return merge(L, R)

Infine, ecco la mia alternativa, che restituisce True , se l'elenco può essere reso palindromo, False altrimenti:

def better_algo_x(A):
    if len(A) < 2:
        return True
    sorted_A = merge_sort(A)
    odd_groups = 0
    current = sorted_A[0]
    c = 1  # Used to count the number of characters that are equal between them
    for i in range(1, len(sorted_A)):
        if current == sorted_A[i]:
            c += 1
        else:
            if c % 2 == 1:
                odd_groups += 1
            if odd_groups > 1:
                return False
            current = sorted_A[i]
            c = 1
    # for the last group of characters
    if c % 2 == 1:
        odd_groups += 1
    if odd_groups > 1:
        return False
    return True

Ho alcune domande:

• Le mie funzioni sono corrette?

• La mia analisi della complessità temporale dell'algoritmo algo_X è corretta?

• Il mio better_algo_x fa ciò che dovrebbe fare?

• Lo fa in n * log (n) nel peggiore dei casi?

• Posso ancora migliorarlo? Come?

• Conosci altre (alternative) alternative per algo_X ?

Certo, alcune domande potrebbero sembrare sciocche, ma mi piacerebbe sentire l'opinione di alcuni esperti. Certo, ho provato i miei algoritmi.