Komputado temas pri kompreni la kompleksecojn de algoritmoj kaj datumstrukturoj.
Vi havas liston de ordigaj aĵoj, sed vi ne havas tempon aŭ rimedojn por uzi pli kompleksan ordigan algoritmon.
Enmeta ordigo estas unu el la plej simplaj ordigaj algoritmoj, sed ĝi povas esti malrapida por grandaj listoj.
Facila efektivigo kaj kompreno igis ĉi tiun metodon plej ŝatata inter programistoj. Ĝi estas perfekta por malgrandaj listoj aŭ kiam vi bezonas rapidan solvon.
En ĉi tiu bloga afiŝo, ni rigardos la tempan kompleksecon de eniga ordigo. Ĉi tiu algoritmo estas uzata por ordigi tabelojn, kaj ĝi havas rultempon de O (n2). Tio signifas ke la tempokomplekseco pliiĝas kun la grandeco de la tabelo.
Tamen, ĉi tiu algoritmo povas esti pli rapida ofte ol aliaj ordigaj algoritmoj, kiel Quicksort.
Ni rigardu pli detale kiel funkcias enmeta ordigo!
Kio Estas Enmeta Ordigo-Algoritmo?
Unu elemento samtempe, enmeta varo generas ordigeblan tabelon, kiu estas ofte nomata listo.
Ekzemple, ordigo estas aplikata en komplikaj komputilaj programoj kiel ekzemple kompililoj, kie la ordo de ĵetonoj estas grava al la interpreto de la programo.
Kiel Funkcias Enmeta Ordo?
Kiam ni uzas enmeta ordigon por ordigi tabelon, la algoritmo komencas trovi la plej malgrandan eron en la listo kaj enmeti ĝin en la ĝustan pozicion.
Ĝi tiam trovas la sekvan plej malgrandan objekton kaj enmetas ĝin en la ĝustan pozicion, ktp.
La algoritmo funkcias per buklo tra la listo, komparante ĉiun objekton kun tiu, kiu venas antaŭ ĝi.
Se la eroj estas en la malĝusta ordo, la algoritmo interŝanĝas ilin. Ĝi tiam kontrolas ĉu la listo estas ordigita, kaj se ĝi estas, la algoritmo finiĝas.
En praktiko, enmeta ordigo ofte estas efektivigita uzante kelkajn liniojn de kodo, igante ĝin populara elekto por ordigi malgrandajn tabelojn. Tamen, tempkomplekseco devus esti pripensita kiam uzado de ĉi tiu algoritmo.
ekzemple:
Jen ekzemplo de kiel funkcias enmeta ordigo. Ni uzos la sekvan tabelon:
1, 2, 3, 4, 5, 6
La algoritmo komencas trovante la plej malgrandan eron en la listo, kiu estas 1. Ĝi tiam enigas ĝin en la ĝustan pozicion, la unuan pozicion. Ĝi tiam trovas la sekvan plej malgrandan objekton, kiu estas 2. Ĝi enigas ĝin en la ĝustan pozicion, kiu estas la dua pozicio.
Ĝi tiam trovas la sekvan plej malgrandan eron, kiu estas 3. Ĝi enigas ĝin en la ĝustan pozicion, kiu estas la tria pozicio.
Ĝi tiam trovas la sekvan plej malgrandan eron, kiu estas 4. Ĝi enigas ĝin en la ĝustan pozicion, kiu estas la kvara pozicio, ktp. La listo nun estas ordigita!
Ni povas vidi el la ekzemplo, ke la algoritmo prenas ses komparojn kaj interŝanĝojn por ordigi la liston. Ĉi tio estas ĉar ĝi prenas n2 komparoj kaj interŝanĝoj por ordigi liston de n eroj. En ĉi tiu kazo, n=6.
Kiel Plibonigi Kompleksecon de Enmeto Ordigo?
Dum enmeta varo havas rultempon de O (n2), ĝi povas esti plibonigita uzante pli bonan ordigan algoritmon, kiel Quicksort.
Quicksort havas O (n log n) rultempon, kio estas multe pli rapida ol O (n2).
Tamen, en kelkaj kazoj, enmeta ordigo povas esti pli rapida ol rapidsortado.
Ekzemple, se la listo jam estas en ordo, enmeta ordigo daŭros malpli da tempo ol rapida ordigo.
En praktiko, enmeta ordigo ofte estas efektivigita uzante kelkajn liniojn de kodo, igante ĝin populara elekto por ordigi malgrandajn tabelojn.
Tamen, tempkomplekseco devus esti pripensita kiam uzado de ĉi tiu algoritmo.
Tempokompleksaĵoj
Plej malbona Kaza Komplekseco O(n2):
La tempokomplekseco pliiĝas kun la grandeco de la tabelo. Necesas n2 komparoj kaj interŝanĝoj por ordigi liston de n eroj.
Ekzemple, se ni havas tabelon de grandeco 1000, la algoritmo prenos 1,000,000 komparojn kaj interŝanĝojn por ordigi la tabelon.
Plej bona Kaza Komplekseco O(n):
La tempokomplekseco estas la sama kiel la grandeco de la eniga tabelo. mi
t prenas n komparojn kaj interŝanĝojn por ordigi liston de n eroj. Ekzemple, konsideru tabelon de grandeco 5. La algoritmo prenos kvin komparojn kaj interŝanĝojn por ordigi la tabelon.
Meza Kaza Komplekseco O(n2):
La tempokomplekseco estas inter la plej malbona kaj plej bona kazo kompleksecoj en ĉi tiu kazo.
Necesas n2 komparoj kaj interŝanĝoj por ordigi liston de n eroj.
Tiel, enmeta ordigo estas stabila ordiga algoritmo.
Kial Enmeta Ordo Estas Stabila?
Enmeta ordigo estas stabila ĉar ĝi konservas la ordon de egalaj elementoj en la eniga tabelo.
Ĉi tio estas grava por multaj aplikoj, kiel ekzemple datumoj reakiro aŭ financa analizo. Ekzemple, se ni havas du listojn de nombroj kaj volas kompari ilin, ni devas certigi, ke la ordo de la elementoj estas konservita.
Se la listoj ne estas ordigitaj, ni ne komparos ilin precize.
Lasi Respondon