Tabl Cynnwys[Cuddio][Dangos]
Mae cyfrifiadureg yn ymwneud â deall cymhlethdodau algorithmau a strwythurau data.
Mae gennych restr o eitemau sydd angen eu didoli, ond nid oes gennych yr amser na'r adnoddau i ddefnyddio algorithm didoli mwy cymhleth.
Trefnu mewnosodiad yw un o'r algorithmau didoli symlaf, ond gall fod yn araf ar gyfer rhestrau mawr.
Mae gweithredu a dealltwriaeth hawdd wedi gwneud y dull hwn yn ffefryn ymhlith rhaglenwyr. Mae'n berffaith ar gyfer rhestrau bach neu pan fydd angen ateb cyflym arnoch.
Yn y blogbost hwn, byddwn yn edrych ar gymhlethdod amser didoli mewnosod. Defnyddir yr algorithm hwn i ddidoli araeau, ac mae ganddo amser rhedeg o O(n2). Mae hyn yn golygu bod y cymhlethdod amser yn cynyddu gyda maint yr arae.
Fodd bynnag, gall yr algorithm hwn fod yn gyflymach yn aml nag algorithmau didoli eraill, megis quicksort.
Gadewch i ni edrych yn agosach ar sut mae didoli mewnosodiadau yn gweithio!
Beth yw Algorithm Trefnu Mewnosod?
Un elfen ar y tro, mae trefn mewnosod yn cynhyrchu arae y gellir ei didoli, a elwir yn aml yn rhestr.
Er enghraifft, cymhwysir didoli mewn rhaglenni cyfrifiadurol cymhleth fel casglwyr, lle mae trefn y tocynnau yn bwysig i ddehongliad y rhaglen.
Sut Mae Mewnosod Didoli yn Gweithio?
Pan ddefnyddiwn drefnu mewnosod i ddidoli arae, mae'r algorithm yn dechrau trwy ddod o hyd i'r eitem leiaf yn y rhestr a'i gosod yn y safle cywir.
Yna mae'n dod o hyd i'r eitem leiaf nesaf ac yn ei fewnosod yn y safle cywir, ac ati.
Mae'r algorithm yn gweithio trwy ddolennu trwy'r rhestr, gan gymharu pob eitem â'r un sy'n dod o'i blaen.
Os yw'r eitemau yn y drefn anghywir, mae'r algorithm yn eu cyfnewid. Yna mae'n gwirio i weld a yw'r rhestr wedi'i didoli, ac os ydyw, mae'r algorithm yn dod i ben.
Yn ymarferol, mae didoli mewnosod yn aml yn cael ei weithredu gan ddefnyddio ychydig linellau o god, gan ei wneud yn ddewis poblogaidd ar gyfer didoli araeau bach. Fodd bynnag, dylid ystyried cymhlethdod amser wrth ddefnyddio'r algorithm hwn.
enghraifft:
Dyma enghraifft o sut mae didoli mewnosod yn gweithio. Byddwn yn defnyddio'r arae canlynol:
1, 2, 3, 4, 5, 6
Mae'r algorithm yn dechrau trwy ddod o hyd i'r eitem leiaf yn y rhestr, sef 1. Yna mae'n ei fewnosod yn y safle cywir, y safle cyntaf. Yna mae'n dod o hyd i'r eitem leiaf nesaf, sef 2. Mae'n ei fewnosod yn y safle cywir, sef yr ail safle.
Yna mae'n dod o hyd i'r eitem leiaf nesaf, sef 3. Mae'n ei fewnosod yn y safle cywir, sef y trydydd safle.
Yna mae'n dod o hyd i'r eitem leiaf nesaf, sef 4. Mae'n ei fewnosod yn y safle cywir, sef y pedwerydd safle, ac ati. Mae'r rhestr bellach wedi'i threfnu!
Gallwn weld o'r enghraifft bod yr algorithm yn cymryd chwe chymariaethau a chyfnewidiadau i ddidoli'r rhestr. Mae hyn oherwydd ei fod yn cymryd n2 cymariaethau a chyfnewidiadau i ddidoli rhestr o n eitem. Yn yr achos hwn, n=6.
Sut i Wella Cymhlethdod Amser Trefnu Mewnosod?
Er bod gan y didoli mewnosod amser rhedeg o O(n2), gellir ei wella trwy ddefnyddio algorithm didoli gwell, fel quicksort.
Mae gan Quicksort amser rhedeg O(n log n), sy'n llawer cyflymach nag O(n2).
Fodd bynnag, mewn rhai achosion, gall didoli mewnosod fod yn gyflymach na quicksort.
Er enghraifft, os yw'r rhestr eisoes mewn trefn, bydd didoli mewnosod yn cymryd llai o amser na quicksort.
Yn ymarferol, mae didoli mewnosod yn aml yn cael ei weithredu gan ddefnyddio ychydig linellau o god, gan ei wneud yn ddewis poblogaidd ar gyfer didoli araeau bach.
Fodd bynnag, dylid ystyried cymhlethdod amser wrth ddefnyddio'r algorithm hwn.
Cymhlethdodau Amser
Cymhlethdod yr Achos Gwaethaf O(n2):
Mae cymhlethdod amser yn cynyddu gyda maint yr arae. Mae'n cymryd n2 cymariaethau a chyfnewidiadau i ddidoli rhestr o n eitem.
Er enghraifft, os oes gennym amrywiaeth o faint 1000, bydd yr algorithm yn cymryd 1,000,000 o gymariaethau a chyfnewidiadau i ddidoli'r arae.
Cymhlethdod Achos Gorau O(n):
Mae'r cymhlethdod amser yr un peth â maint yr arae mewnbwn. i
t cymryd n cymariaethau a chyfnewid i ddidoli rhestr o n eitem. Er enghraifft, ystyriwch arae o faint 5. Bydd yr algorithm yn cymryd pum cymhariaeth a chyfnewidiad i ddidoli'r arae.
Cymhlethdod Achos Cyfartalog O(n2):
Mae'r cymhlethdod amser rhwng y cymhlethdodau achos gwaethaf a gorau yn yr achos hwn.
Mae'n cymryd n2 cymariaethau a chyfnewidiadau i ddidoli rhestr o n eitem.
Felly, mae didoli mewnosod yn algorithm didoli sefydlog.
Pam Mae Trefn Mewnosod yn Sefydlog?
Mae didoli mewnosod yn sefydlog oherwydd ei fod yn cadw trefn yr elfennau cyfartal yn yr arae mewnbwn.
Mae hyn yn bwysig ar gyfer llawer o gymwysiadau, megis adalw data neu ddadansoddi ariannol. Er enghraifft, os oes gennym ddwy restr o rifau ac eisiau eu cymharu, mae angen i ni wneud yn siŵr bod trefn yr elfennau yn cael ei gadw.
Os na chaiff y rhestrau eu didoli, ni fyddwn yn eu cymharu'n gywir.
Gadael ymateb