Adolygu Ffeithiau Uned 3

Cysylltwch yr algorithmau efo'r cymhlethdod amser cywir.

Groups:

(a) O (log n)

,

(b) O (n)

,

(c) O (n log n)

,

(d) O (n²)

• Trefnu Mewnosod

• Trefnu Cyflym (achos waethaf)

• Chwilio Deuaidd

• Chwilio Llinol

• Trefnu Cyflym (gorau)

• Trefnu Bwrlwm

Mae ​ (a)   yn galluogi i ddata gael ei gywain, mewnosod a dileu yn gyflym, ond nid yw'n bosib rhoi trefn ar y data ac mae'n strwythr aneffeithlon o ran y cof. Mae ​ rhestri cysylltiedig yn fwy effeithlon o ran y cof, ond mae'n arafach - O(n) - i ​ (b)   data.

• tablau stwnsh
• araeau 2d
• coed chwiliadau deuaidd
• cywain (nol)
• mewnosod (ychwanegu)
• dileu

Categoreiddiwch y prosesau canlynol yn ôl eu effeithlonrwydd amser

Groups:

(a) O(1)

,

(b) O(n)

,

(c) O(log n)

• Chwilio am ddata mewn rhestr cysylltiedig

• Chwilio am nod mewn coeden chwiliadau deuaidd cytbwys

• Chwilio am nod mewn coeden chwiliadau deuaidd ANGHYTBWYS

• Dileu nod o restr cysylltiedig

• Indecsio arae

Pa groesiad sy'n cael ei ddefnyddio er mwyn clonio coeden chwiliadau deuaidd?

• Croesiad cyn-drefnol

• Croesiad ôl-drefnol

• Croesiad mewn trefn

Pa groesiad sy'n cael ei ddefnyddio er mwyn dileu coeden chwiliadau deuaidd un nod ar y tro?

• Croesiad cyn-drefnol

• Croesiad ôl-drefnol

• Croesiad mewn trefn

Ticiwch pob strwythr data ble mae modd cywain (fetch) data mewn amser O(1)

• Arae

• Rhestr Cysylltiedig

• Coeden Chwiliadau Deuaidd

• Tabl Stwnsh

Ticiwch pob strwythr data ble mae modd ychwanegu data yng nghanol y strwythr mewn amser O(1) heb ddinistrio trefn

• Arae

• Rhestr Cysylltiedig

• Coeden Chwiliadau Deuaidd

Ydy'r datganiadau yma yn wir neu gau ar gyfer COED CHWILIADAU DEUAIDD

Groups:

(a) GWIR

,

(b) GAU

• Maent yn addas ar gyfer basau data

• Mae'n gyflym iawn i ychwanegu data at y strwythr data yma

• Mae modd canfod data ym mhob coeden chwiliadau deuaidd mewn amser O(log n)

• Mae'r strwythr data yma yn aneffeithlon o ran cof

• Mae'r strwythr yma yn ddeinamig

• Mae'r algorithm stwnsh yn effeithio cyflymder canfod data

Beth a olygir gan GWRTHDRAWIAD mewn tabl stwnsh?

• Mae'r strwythr yn anghytbwys ac mae'r amser chwilio nawr yn dilyn O(n)

• Mae'r algrorithm stwnsh yn rhoi yr un indecs ar gyfer dau werth allweddol gwahanol

• Mae 'nwl' ble dylai fod data

• Mae'r trefn wedi dinistrio a nawr dydy chwilio deuaidd ddim yn bosib

Cysylltwch y disgrifiadau i'r strwythr data

• Coeden Chwiliadau Deuaidd

• Cyflym i gywain data ond araf i ychwanegu tra'n cadw trefn

• Arae

• Ychwanegu, dileu a chywain data cyflym ond defnydd aneffeithlon o'r cof

• Tabl Stwnsh

• Ychwanegu/dileu data yn gyflym, ond araf i ddarganfod data

• Rhestr Cysylltiedig

• Strwythr deinamig wedi ei optimeiddio i gywain data mewn amser O(log n)