Үймөк сортторуна кошумча орун керекпи?

2024 Автор: Fiona Howard | [email protected]. Акыркы өзгөртүү: 2024-01-10 06:40

Heapsort – бул экилик үймөк маалымат структурасын колдонгон салыштырууга негизделген сорттоо алгоритми. Бириктирүү иреттөө сыяктуу Информатика илиминде бириктирүү сорту (көбүнчө бириктирүү деп да жазылат) натыйжалуу, жалпы максаттуу жана салыштырууга негизделгенсорттоо алгоритми. Көпчүлүк ишке ашыруулар туруктуу сортту чыгарышат, бул киргизүү жана чыгарууда бирдей элементтердин тартиби бирдей экенин билдирет. https://en.wikipedia.org › wiki › Merge_sort

Бириктирүү сорту - Wikipedia

үймө сорттун иштөө убактысы O (n log ⁡ n), O(n\log n), O(nlogn) жана кыстаруу сыяктуу үймөк сорттор ордунда сорттолот, ошондуктан сорттоодо кошумча орун талап кылынбайт.

Үймөк түрүндөгү эс мейкиндиги кандай?

Үймөк иреттөө O (n lg ⁡ (n)) O(n\lg(n)) O(nlg(n)) убакытта иштейт, ал n чоңойгондой масштабланат. Ыкчам сорттоодон айырмаланып, эң начар O (n 2) O(n^2) O(n2) татаалдыгы жок. Космос үнөмдүү. Үймөк иреттөө O (1) O(1) O(1) бош орун алат.

Эмне үчүн үймөк түрдөгү O 1 мейкиндик татаалдыгы?

2 Жооптор. HEAP SORT өзүн чакырган MAX_HEAPIFY функциясын колдонот, бирок аны жөнөкөй while циклинин жардамы менен жасоого болот жана муну менен аны кайталанма функцияга айландырса болот, ал мейкиндикти талап кылбайт, ошондуктан HEAP SORT мейкиндик татаалдыгы чейин азайтылышы мүмкүн. O(1).

Үймөктөп сорттоо жөнүндө эмне айтууга болот?

Үймөк сорттоо бул Бинардык үймөк берилиштер структурасына негизделген салыштырууга негизделген сорттоо ыкмасы. Бул тандоо сортуна окшош, анда биз алгач минималдуу элементти таап, эң башына минималдуу элементти коёбуз. Ушул эле процессти калган элементтер үчүн кайталайбыз.

5 максималдуу үйүлгөндө кандай абалда болот?

5 тамырда болот.