Heaps og uppsafnaður reiknitími

Choose a study mode

Play Quiz
Study Flashcards
Spaced Repetition
Chat to Lesson

Podcast

Play an AI-generated podcast conversation about this lesson
Download our mobile app to listen on the go
Get App

Questions and Answers

Í uppsöfnuðu tímaflækju, ef rauntími fyrir aðgerð er táknaður sem $c_i$ og uppsafnaður tími er reiknaður með jöfnunni $a_i = c_i + \Phi(H_{i+1}) - \Phi(H_i)$, hvaða fullyrðing er rétt varðandi $\Delta\Phi$?

  • $\Delta\Phi$ táknar alltaf jákvæða breytingu á möguleikafalli.
  • $\Delta\Phi$ táknar alltaf neikvæða breytingu á möguleikafalli.
  • $\Delta\Phi$ táknar breytinguna á möguleikafalli og getur verið jákvæð eða neikvæð, sem hefur áhrif á uppsafnaðan tíma. (correct)
  • $\Delta\Phi$ getur verið bæði jákvæð og neikvæð, en hefur engin áhrif á uppsafnaðan tíma.

Í samhengi við uppsöfnuð tímaflækju og mættisfalls (potential method), hvaða fullyrðing er sönn um gildi mættisfallsins, $\Phi(H)$, fyrir gagnagrind $H$?

  • $\Phi(H)$ er alltaf jákvætt og eykst með hverri aðgerðir.
  • $\Phi(H)$ er alltaf stærra eða jafnt og núll og táknar ákveðna eiginleika gagnagrindarinnar. (correct)
  • $\Phi(H)$ getur verið neikvætt ef gagnagrindin er óhagkvæm.
  • $\Phi(H)$ er alltaf jafnt núlli.

Hvernig hefur val á mættisfalli (potential function) áhrif á greiningu á uppsöfnuðum tímaflækjum?

  • Val á mættisfalli hefur engin áhrif á greininguna, þar sem uppsafnaður kostnaður er reiknaður óháð því.
  • Mættisfallið er eingöngu notað til að einfalda útreikninga og hefur ekki raunveruleg áhrif á niðurstöðurnar.
  • Besta mættisfallið er alltaf það sem gefur lægsta mögulega uppsafnaða kostnað.
  • Val á mættisfalli getur haft veruleg áhrif á niðurstöður greiningarinnar, þar sem það ákvarðar hvernig kostnaður er jafnaður yfir aðgerðir. (correct)

Hvaða fullyrðing lýsir best hlutverki amortized kostnaðar við greiningu á reikniritum?

<p>Amortized kostnaður gefur raunsærri mynd af kostnaði við aðgerðir yfir tíma, sérstaklega þegar kostnaðurinn er mjög breytilegur. (D)</p>
Signup and view all the answers

Í tengslum við fylki sem stækka tvöfalt þegar þörf er á meira plássi, hvaða fullyrðing er rétt um tímaflækju þess að bæta við staki?

<p>Tímaflækjan er $O(1)$ í amortized tíma, en getur verið $O(n)$ í versta falli þegar fylkið þarf að stækka. (A)</p>
Signup and view all the answers

Þegar unnið er með fylki af stærð $m$ sem inniheldur $n$ stök og stækkar tvöfalt ef vantar pláss, hvaða fullyrðing er sönn ef við höldum fylkinu alltaf 25% fullu?

<p>Þetta dregur úr minnisnýtingu þar sem stórt fylki er í notkun þrátt fyrir fá stök. (C)</p>
Signup and view all the answers

Ef við notum mættisfallið $\Phi(n) =$ fjöldi ása í tvíundartölunni $n$ fyrir aðgerðir á fylki, hvernig hjálpar það til við að greina uppsöfnuðu tímaflækjuna?

<p>Það hjálpar til við að jafna kostnaðinn við aðgerðir, þar sem dýrar aðgerðir (þ.e. stækkanir) minnka mættisfallið og ódýrar aðgerðir auka það. (D)</p>
Signup and view all the answers

Hvaða áhrif hefur það á heildarkostnaðinn ef mættisfallið er skilgreint sem $\Phi(H) = 3n - m \geq 0$, þar sem $n$ er fjöldi staka og $m$ er stærð fylkisins, og við stækkum fylkið tvöfalt þegar það er fullt?

<p>Heildarkostnaðurinn endurspeglar raunverulegan kostnað betur þar sem mættisfallið jafnar kostnaðinn yfir aðgerðir. (D)</p>
Signup and view all the answers

Í Fibonacci hrúgu, hvaða fullyrðing er sönn um tvítengda listann af trjám?

<p>Hann inniheldur tré þar sem hvert tré uppfyllir hrúguröðun og min bendir á tréð með minnsta rót. (A)</p>
Signup and view all the answers

Hvaða þýðingu hefur það í Fibonacci hrúgu þegar sumir hnútar eru merktir?

<p>Það gefur til kynna að þeir hafa misst barn og verða hugsanlega skornir burt síðar. (B)</p>
Signup and view all the answers

Hvernig er rank(x) skilgreint í Fibonacci hrúgu og hvaða þýðingu hefur það?

<p><code>rank(x)</code> er fjöldi barna hnútsins x og gefur til kynna gráðu hnútsins. (D)</p>
Signup and view all the answers

Hvaða áhrif hefur aðgerðin Link(T1, T2) á Fibonacci hrúgu?

<p>Hún sameinar tré T1 og T2 í eitt tré, þar sem rót annars trésins verður barn hinnar. (B)</p>
Signup and view all the answers

Gefið að $\Phi(H) = trees(H) + 2 \cdot marks(H)$ í Fibonacci hrúgu, hvernig breytist möguleikafallið við Link aðgerð?

<p>$\Phi(H)$ minnkar um 1 þar sem fjöldi trjáa minnkar. (B)</p>
Signup and view all the answers

Hvaða skref felur í sér delete_min aðgerðin í Fibonacci hrúgu?

<p>Hún fjarlægir minnsta stakið og bætir börnum þess við tvítengda listann og leitar að nýju min. (D)</p>
Signup and view all the answers

Hvað gerist þegar leitað er að nýju min í delete_min aðgerðinni í Fibonacci hrúgu?

<p>Trjám með sama <code>rank(x)</code> er tengt saman þar til öll tré hafa mismunandi <code>rank(x)</code>. (B)</p>
Signup and view all the answers

Hvað er átt við með Vanlar kostnaður í samhengi við Fibonacci hrúgur?

<p>Það er amortized kostnaðurinn við aðgerð, reiknaður út frá breytingum á möguleikafallinu. (B)</p>
Signup and view all the answers

Hver er munurinn á Insert aðgerðinni í Fibonacci hrúgu og öðrum hrúgum?

<p>Í Fibonacci hrúgu er nýi hnúturinn bætt við sem sér nýtt tré, en í öðrum hrúgum þarf hann að finna réttan stað strax. (A)</p>
Signup and view all the answers

Hvaða af eftirfarandi fullyrðingum lýsir best decrease_key aðgerðinni í Fibonacci hrúgu?

<p>Hún lækkar gildi lykils og endurraðar hrúgunni ef hrúguröðun er brotin. (D)</p>
Signup and view all the answers

Hvað gerist ef hnútur í Fibonacci hrúgu missir tvö börn?

<p>Hann er skorinn burt og settur á trjáalistann. (A)</p>
Signup and view all the answers

Hver er tímaflækjan fyrir rank(H) í Fibonacci hrúgu með $n$ lykla?

<p>$O(log n)$ (B)</p>
Signup and view all the answers

Hvaða fullyrðing er rétt um tímaflækjuna fyrir Allen gedir hate (allar aðgerðir nema delete-min) í Fibonacci hrúgu?

<p>Þær hafa allar tímaflækju $O(1)$. (A)</p>
Signup and view all the answers

Hver er áætluð tímaflækja fyrir aðgerðina delut-min (delete-min) í Fibonacci hrúgu?

<p>$O(log n)$ (C)</p>
Signup and view all the answers

Hvernig er möguleikafallið (potential function) $\Phi(H) = trees(H) + 2 \cdot marks(H)$ notað til að greina tímaflækju Fibonacci hrúga?

<p>Það er notað til að jafna kostnaðinn við aðgerðir yfir tíma, þannig að dýrar aðgerðir hafa minni áhrif á heildarflækjuna. (A)</p>
Signup and view all the answers

Hver er helsti munurinn á Fibonacci hrúgu og tvíhrúgu (binary heap) hvað varðar tímaflækju lykilaðgerða?

<p>Fibonacci hrúgur hafa betri amortized tímaflækju fyrir innsetningu og lækkun lykla, en tvíhrúgur eru betri fyrir að finna og fjarlægja minnsta stakið. (B)</p>
Signup and view all the answers

Hvaða hlutverki gegnir merking hnúta í Fibonacci hrúgum og hvernig hefur það áhrif á tímaflækjuna?

<p>Merking hnúta gerir hrúgunni kleift að fylgjast með hnútum sem hafa misst barn, sem hjálpar til við að halda hrúgunni jafnvægi og bætir tímaflækjuna. (B)</p>
Signup and view all the answers

Í decrease_key aðgerðinni, ef nýja gildið brýtur ekki hrúguröðun, hvað gerist?

<p>Gildið er lækkað og ekkert annað gerist. (B)</p>
Signup and view all the answers

Segjum að þú sért að nota Fibonacci hrúgu til að útfæra Dijkstra reikniritið fyrir stysta leið í grafi. Hvernig hefur notkun Fibonacci hrúgu áhrif á heildar tímaflækju reikniritsins samanborið við notkun tvíhrúgu?

Signup and view all the answers

Flashcards

Hvað er potential method?

Mættisfall (Φ(H)) er alltaf stærri en eða jafnt og núll, og upphafsgildið Φ(Ø) er núll.

Hvað er uppsafnaður tími?

Rauntími aðgerðar leiðréttur með breytingu á mættisfallinu (Φ).

Hvernig er mættisfallið fundið?

Finna fall sem sýnir ákjósanlega framkvæmd.

Hvað getum við notað fyrir bitatalningu?

Þ(n) = fjöldi ása í n

Signup and view all the flashcards

Fastayrðing Fibonacci hrúga

H er tvítengdur listi af trjám, hvert tré uppfyllir hrúguröðun, min bendir á tréð með minnstu rót, sumir hnútar eru merktir.

Signup and view all the flashcards

Hvað er Φ(H) í Fibonacci hrúgu?

Þ(H) = trees(H) + 2 * marks(H)

Signup and view all the flashcards

Hvað gerir Link(T1, T2)?

Tengir tvö tré saman.

Signup and view all the flashcards

Hvað gerist í delete_min?

Fjarlægir rótina á min, bætir börnunum við tvítengda listann, leitar að nýju min.

Signup and view all the flashcards

Hvað gerir Insert?

Bætir við hnút sem er nýtt sérstakt tré, setur í listann og athugar hvort þurfi að uppfæra min.

Signup and view all the flashcards

Hvað gerist í decrease_key?

Ef nýja gildið brýtur ekki hrúguröðun, lækka gildið. Annars er hnúturinn skorinn burt og settur á trjáalistann.

Signup and view all the flashcards

Hvað gildir um rank(H) í Fibonacci hrúgu?

Fyrir Fibonacci hrúgu með n lykla gildir rank(H) = O(log(n)).

Signup and view all the flashcards

Study Notes

  • The text is about analyzing algorithms, specifically heaps and amortized time complexity.
  • Author: Páll Melsted, 2025

Accumulated Time Complexity

  • Potential method uses a potential function Φ(H) which is greater than or equal to 0, and Φ(Ø) = 0.
  • Real time for an operation is cᵢ, amortized time is aᵢ = cᵢ + Φ(Hᵢ₊₁) – Φ(Hᵢ) = cᵢ + ΔΦᵢ.
  • Total cost for the first m operations is ∑cᵢ = ∑(aᵢ – (Φ(Hᵢ₊₁) – Φ(Hᵢ)) = (∑aᵢ) + Φ(H₀) – Φ(Hₘ).

Potential Funtion

  • The potential function is found by vimw/heppni/reynsla; translates to effort/lucky/experience

  • For bit counting, Φ(n) = number of ones in n.

  • An array of size m with n elements is doubled in size if space runs out, keeping it 25% full.

  • Value of Φ(0) = 0

  • aᵢ = cᵢ + ΔΦ = (t+1) + (-t+1) = 2

  • ∑cᵢ ≤ ∑aᵢ = 2 * n

  • For an array places in n items, n items takes up 25%

  • cᵢ = 1 if n < m, cᵢ = m if n = m, then doubles the array, and moves items over

  • Φ(H) = 3n – m ≥ 0, as well as Φ(Ø) = 0

  • aᵢ = cᵢ + ΔΦ = 1 + (3(n+1) – m) – (3n – m) = 4 if n<m and m + (3(n+1) – 2m) – (3n – m) = 3 if n=m

  • Total cost for first operations is ∑cᵢ ≤ ∑aᵢ ≤ 4 * n

Fibonacci Heaps

  • H is a doubly linked list of trees.

  • Each tree satisfies the heap order property.

  • "min" points to the tree with the smallest root.

  • Some nodes are marked.

  • rank(x) = number of children of x, degree.

  • rank(H) = largest degree of any node.

  • marks(H) = number of marked nodes.

  • trees(H) = number of trees.

  • Φ(H) = trees(H) + 2 * marks(H)

  • Link(T1, T2) joins two trees together.

  • aᵢ = cᵢ + ΔΦ = cᵢ - 1 ≤ 1

  • delete_min removes the root of the minimum tree, adds the children to the doubly linked list, and searches for the new minimum.

  • When searching for a new minimum, trees are linked with each other to ensure all trees have different ranks.

  • cᵢ = #börnmin + #trjágjörð ≤ rank(H) + trees(H)

  • aᵢ = cᵢ + Φ ≤ rank(H) + trees(H) + ΔΦ

  • Can be estimated as ≤ 2 * rank(H) + 1

  • When inserting a new node into the Fibonacci heap, it is added to the list of trees, and the minimum is updated, if necessary

  • cᵢ = 1, ΔΦ = 1

  • The decrease_key operation

    • If the new key value does not break the heap order, decrease the key.
    • Otherwise, cut the node and insert it into the list of trees
    • Nodes that are marked have lost one child. If the node loses another child, it is added to the list and the mark is removed.

  • cᵢ = 1 + # marked nodes being removed. can be estimated to less than 1 + marks(H)

  • ΔΦ = 1 + mᵢ – 2mᵢ = 1 – mᵢ. where m is new trees

  • For Fibonacci heaps with n keys rank(H) = O(log(n))

  • Amortized Cost

    • All other operations have O(1)
    • Delete-min has = O(log(n))

Studying That Suits You

Use AI to generate personalized quizzes and flashcards to suit your learning preferences.

Quiz Team

Related Documents

More Like This

Use Quizgecko on...
Open
Browser
Browser