Gå til innhold

Holgers lille NTNU-tråd | *Se første post for spørsmål om hybel*


HolgerL

Hvilket sted tilhører du?  

1 457 stemmer

  1. 1. Velg ett av alternativene

    • Dragvoll
      254
    • Gløshaugen
      1019
    • Annet
      202


Anbefalte innlegg

Videoannonse
Annonse
Skrevet

Bah, var bare i nærheten når det kom til oppg 3b. Ellers helt på bærtur. Bare glad jeg er ferdig med skiten.

Skrevet

Skrev fra telefon i går kveld så orket ikke kommentere :p

Kom så langt, spørsmålet er hva du dytter inn i hashen. Dytter du inn alle foreldrene, er det lg(n) foreldre, og du får O(n lg(n))

Grafen trenger heller ikke være balansert, så kan faktisk bli opp til n foreldre, så blir O(n^2)

 

Du lagrer barnet som key og parent som value. Så henter du ut parent og slår opp på nytt til du har enten roten eller den du leter etter. Alle oppslag skjer i konstant tid.

Oppslagene skjer i konstant tid, ja. Men du må nøste deg igjennom, som ikke blir konstant.

 

Vet noen også fikk til "når er x = z + y" i lineær tid ved å hashe alle x - z, så hashe y og se etter kollisjoner.

Skrevet

Skrev fra telefon i går kveld så orket ikke kommentere :p

Kom så langt, spørsmålet er hva du dytter inn i hashen. Dytter du inn alle foreldrene, er det lg(n) foreldre, og du får O(n lg(n))

Grafen trenger heller ikke være balansert, så kan faktisk bli opp til n foreldre, så blir O(n^2)

Ja, men med mindre den ikke har forgreninger i det hele tatt blir det etter det jeg husker O(log(n)). Det blir det samme som at Quicksort _egentlig_ er O(n^2) i worst-case, men

med randomisering så kommer det aldri til å skje, så vi sier den er O(n*log(n))

 

Du lagrer barnet som key og parent som value. Så henter du ut parent og slår opp på nytt til du har enten roten eller den du leter etter. Alle oppslag skjer i konstant tid.

Oppslagene skjer i konstant tid, ja. Men du må nøste deg igjennom, som ikke blir konstant.

 

Vet noen også fikk til "når er x = z + y" i lineær tid ved å hashe alle x - z, så hashe y og se etter kollisjoner.

Jeg hashet hele B-tabellen, regnet ut z=x-y for hver x i A, så slo jeg opp z i B. Kjøretid: O(n)

Skrevet

Gikk det så dårlig?

 

Eksamen var ok, var bare jeg som ikke kunne nok av det det ble spurt om ;-)

Forhåpentligvis står jeg, muligens ikke. Har egentlig ikke prioritert å lese på det heller forsåvidt, så det er jo greit.

Skrevet

Har du lest på noe i det hele tatt? Synes du skriver "</3" for alle fag.

 

Jeg HAR lest, jeg har kanskje bare litt tungt for det:-P

 

Når er det eksamen i matte 1?

 

21. desember :-)

Skrevet (endret)

Ble fortalt av en kar at man ikke kan stryke på masteroppgaven hvis man ikke har fått varsel. Kan dette stemme?

 

Du kan stryke jo, men du skal få beskjed innen ganske kort tid (ikke først etter den tre måneder lange sensurfristen). Det komiske er at du kan "konte" den hvis du stryker; dvs at du får en mulighet til å levere en "revidert" utgave (hvor man, i utgangspunktet, faktisk får 20 uker på seg - like mye som første gangen, noe som er så latterlig at det ikke kan beskrives med ord).

Endret av drgz

Opprett en konto eller logg inn for å kommentere

Du må være et medlem for å kunne skrive en kommentar

Opprett konto

Det er enkelt å melde seg inn for å starte en ny konto!

Start en konto

Logg inn

Har du allerede en konto? Logg inn her.

Logg inn nå
×
×
  • Opprett ny...