Vurdering av min algoritme

[Gjest Slettet+45613274]

Hei,

Er ny med algoritmer og ønsker tilbakemelding på mitt arbeid. Har akkurat startet så vi har ikke lært noe mer enn brute-force.

 

Oppgave:

Finne den minste differansen mellom to tall i en liste L. F.eks [tex]L_n {19, 31, 15, 21} [/tex] Her er løsningen 2 siden 21-19 er 2. Kalkuler big O av algoritmen.

 

Big O:

Her er jeg veldig usikker, men tenker at den må bli: Eller kanske bare ?

 

Input: L:{y_1, y_2, y_3, ... , y_n}

 

Output: x      // smallest difference between two numbers in L

 

 

  // number of computational combinations

  // initializing the output x

 

 

 

while i_3 < n_x
        z <- |Li_1 - Li_2|           //subtracting element i_1 and i_2 in L
        if z < x
            x <- z
        else
            x <- x                        // Is this necessary?
        
        if i_2 < n                       // incrementing matrix in x direction (arbitrarily)
            i_2 <- i_2 + 1
            i_3 <- i_3 + 1
        else
            i_1 <- i_1 + 1            // incrementing matrix in y direction and reset x direction (arbitrarily)
            i_2 <- i_1 + 1
            i_3 <- i_3 + 1

end
output: x

Endret 29. september 2017 av Slettet+45613274

[OneWingedAngel]

Algoritmen din gjør sammenligninger som du nevner. Dette er mer eller mindre det samme som å brute-force de mulige kombinasjonene med to for-løkker, noe som kanskje ikke er helt optimalt.

 

Finnes det en måte å kun måtte gjøre sammenligninger i stedet (dvs. kun iterere gjennom listen én gang)?

[Gjest Slettet+45613274]

Algoritmen din gjør sammenligninger som du nevner. Dette er mer eller mindre det samme som å brute-force de mulige kombinasjonene med to for-løkker, noe som kanskje ikke er helt optimalt.

 

Finnes det en måte å kun måtte gjøre sammenligninger i stedet (dvs. kun iterere gjennom listen én gang)?

Takk for svar. Ok, big O har jeg da forstått.

 

Når det gjelder å itere bare en gang så er ikke det mulig i mitt hode fordi man får automatisk en 2-dimensjonal matrise for å teste alle elementene i L. Altså L_1 - L_2, L_1 - L_3, L_1 - L_4 helt til siste leddet når L_n. Så må man begynne på L_2 - L_3, L_2 - L_4 osv.

[Gavekort]

Tror ikke O(n) er mulig. Jeg har ikke tenkt noe grundig over dette, men kan du ikke sortere listen med O(n log(n)) og iterere O(n)?

[OneWingedAngel]

Tror ikke O(n) er mulig. Jeg har ikke tenkt noe grundig over dette, men kan du ikke sortere listen med O(n log(n)) og iterere O(n)?

 

Var selvsagt dette jeg forsøkte å hinte til. Sortere tar O(n log (n)) + iterere O(n) (altså O(n) sammenligninger). Blir riktignok O(n log n) samlet sett.

Endret 29. september 2017 av OneWingedAngel

[0laf]

Dette er et velkjent matematisk problem, gjerne kalt "nearest neighbor" problemet.

I programmering kaller vi det som oftest for et "closest pair" problem.

Selv om du er ute etter kun differansen, så må jo den regnes ut for å finne de to punktene, eller tallene, som er nærmest hverandre, derav "closest pair".

 

Slike problemer har stort sett de samme løsningene, enten brute force, slik at du har gjort, eller sortering og sammenligning, som helt korrekt er O(n log n) kompleksitet.

 

Nå er det faktisk mulig å løse dette med O(n) kompleksitet, dersom man bruker tilfeldig generering og litt triksing.

Metoden ble funnet opp Rabin, og jeg har vært borti den i noen lærebøker, men den brukes nok svært sjeldent i programmering, jeg har i det minste aldri skrevet noe slikt så vidt jeg kan huske.

Jeg har også litt problemer med å finne eksempler i kode, det eneste jeg fant i farten var

 

 

https://rjlipton.wordpress.com/2009/03/01/rabin-flips-a-coin/

[Gjest Slettet+45613274]

 

Tror ikke O(n) er mulig. Jeg har ikke tenkt noe grundig over dette, men kan du ikke sortere listen med O(n log(n)) og iterere O(n)?

 

Var selvsagt dette jeg forsøkte å hinte til. Sortere tar O(n log (n)) + iterere O(n) (altså O(n) sammenligninger). Blir riktignok O(n log n) samlet sett.

 

Takk også adeneo for innsikt. Men jeg tolker dere som at det jeg har gjort er korrekt, så det er iallefall noe

 

Så bare for å dobbelsjekke. Dere vil sortere først for så å sjekke |L_1 - L_2|, |L_2 - L_3| osv...?