Бөөн эрэмбэлэхэд нэмэлт зай шаардлагатай юу?

2024 Зохиолч: Fiona Howard | [email protected]. Хамгийн сүүлд өөрчлөгдсөн: 2024-01-10 06:41

Heapsort нь хоёртын овоолгын өгөгдлийн бүтцийг ашигладаг харьцуулалтад суурилсан эрэмбэлэх алгоритм юм. Mergesort mergesort-тай адил Компьютерийн шинжлэх ухаанд нэгтгэх эрэмбэлэх (мөн нэгтгэх гэж нэрлэдэг) нь үр ашигтай, ерөнхий зориулалттай, харьцуулалтад суурилсан эрэмбэлэх алгоритм юм. Ихэнх хэрэгжүүлэлт нь тогтвортой эрэмбийг гаргадаг бөгөөд энэ нь оролт, гаралтад тэнцүү элементүүдийн дараалал ижил байна гэсэн үг юм. https://en.wikipedia.org › wiki › Merge_sort

Нэгдүүлэх төрөл - Википедиа

heapsort нь 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 үндсэнд байх болно.