Controlla la distanza tra tutti gli elementi in una lista di numeri in O (n * lg (n))

Question

Controlla la distanza tra tutti gli elementi in una lista di numeri in O (n * lg (n))

#1 da (1 voti)
#2 da (1 voti)
#3 da (0 voti)

1

Ho un esercizio per la mia classe di algoritmi e strutture di dati, dove fondamentalmente devo implementare un dividere e conquistare algoritmo o funzione chiamato check_distance per determinare se tutti i numeri in una lista X avere distanza maggiore o uguale a k l'una dall'altra, e devo mostrare che la complessità del caso peggiore di questo algoritmo è O(n*lg(n)) .

Quando penso agli algoritmi che devono essere eseguiti al massimo in n*lg(n) time asintoticamente, penso immediatamente a merge sort, che è esattamente l'algoritmo divide and conquer che ho usato. Le mie funzioni sono corrette o no?

Prima di questo esercizio ne avevo già uno, in cui dovevo creare un'altra funzione divide and conquer per verificare se ci sono duplicati in una lista. Questa funzione dovrebbe anche essere eseguita in O(n*lg(n)) .

Questa è la mia funzione check_duplicates , che utilizza di nuovo l'algoritmo merge sort (non sto postando il codice dell'algoritmo merge sort , perché è una fusione tipica Se vuoi che lo mandi, basta chiedere!):

def check_duplicate(X):
    S = merge_sort(X)               # O(n*lg(n))
    for i in range(0, len(S) - 1):  # O(n)
        if S[i] == S[i + 1]:
            return True
    return False

Le mie prime domande sono: È corretto, e viene eseguito in tempo O (n * lg (n))?

Ora, passo al problema reale, la mia seconda funzione, che (come ho detto) dovrebbe verificare che la distanza tra ogni elemento di una lista sia maggiore o uguale di una costante k . Per questa funzione check_distance , ho usato la funzione check_duplicate sopra, per garantire che non ci siano duplicati, altrimenti restituisce immediatamente false.

Ora, il mio ragionamento principale era ancora una volta per ordinare l'elenco. Una volta che l'elenco è ordinato, l'elemento _{i + 1} sarà sempre maggiore o uguale di un _i, quindi, per tutti i _i in X , a _i < = a _{i + 1} < = a _{i + 2}, ecc.

Ora, ancora una volta, per tutto un _i in X , se riassumo un _i + k, e questo è minore o uguale di un _{i + 1}, quindi la distanza tra tutti gli elementi dovrebbe essere > = k .

Sono corretto?

def check_distance(X, k):
    if check_duplicate(X):        # n*lg(n)
        return False
    else:                         # no duplicate values
        A = merge_sort(X)
        for i in range(len(A) - 1):
            if A[i] + k > A[i + 1]:
                return False
        return True

Se non sono corretto, c'è un approccio migliore?

recursion python algorithms algorithm-analysis

posta nbro 30.03.2015 - 22:43

fonte

3 risposte

Leggi altre domande sui tag recursion python algorithms algorithm-analysis

Uso corretto della promessa Bluebird Domanda di licenza di Piwik

score 1 · Answer 1

La soluzione ovvia è ordinare l'array in O (n log n), e quindi gli elementi possono essere controllati in modo sequenziale in O (n). Mi chiedo che cosa stia accadendo nella mente degli insegnanti quando chiede un algoritmo di "divide et impera".

score 1 · Answer 2

Suppongo che tu non abbia più bisogno di questo, ma da quando ho realizzato l'urto di Gnasher solo dopo aver riflettuto su questo, lascerò comunque un codice più bello qui:

def check_distance(X, k):
    A = merge_sort(X)
    return all(b-a >= k for a, b in zip(A, A[1:]))

Sono interessato alla soluzione dell'insegnante. Aveva solo questo tipo di cervello e ha in mente, o qualcosa di più interessante?

score 0 · Answer 3

check_duplicate è ridondante. L'elenco non deve essere ordinato perché l'ordinamento arretra gli elementi.

Calcola la differenza tra due elementi consecutivi e confronta il valore con k .

def check_distance(x, k):
    l = len(x)
    if l in [0,1]:
        return False

    for i in range(l-1):
        if x[i+1] - x[i] < k:
            return False
    return True

Uso della ricorsione,

def check_dist(x,k):
    l = len(x)
    if l == 2:
        return x[1] - x[0] >= k
    if l in (0,1):
        return False
    return x[1] - x[0] >= k and check_dist(x[1:],k)