Rikiavimo palyginimais apatinė riba
Skirtingų raktų palyginimams reikia pakankamai šakų, kad būtų galima atskirti jų išsidėstymo tvarkas.
Esminės žinios
Rikiuojant n skirtingų raktų dvejetainiais palyginimais, galimos n! išsidėstymo tvarkos. Todėl algoritmo sprendimų medžio gylis blogiausiu atveju turi būti bent ⌈log₂(n!)⌉, o tai yra Ω(n log n).
Sąlygos ir taikymo ribos
- Algoritmas informaciją apie raktų tvarką gauna tik juos palygindamas.
- Sveikųjų skaičių raktų rikiavimas skaičiavimu arba skaitmenimis naudoja papildomas operacijas, todėl ši apatinė riba jam netaikoma.
Šaltiniai · 1
Šaltiniai
Šaltiniai išlaiko savo taikymo ribas. Vien nuoroda nepatvirtina kiekvieno teiginio patikrinimo.
Pagrindimas ir peržiūra
Fizinis puslapis 2: palyginimų sprendimų medis, n! rezultatų ir Ω(n log n) apatinė riba; sveikųjų skaičių raktų rikiavimui naudojamas kitas modelis.
2026-10-10 · Palyginimų sprendimų medžio apatinė riba, paskaita 5.
Įrašo informacija
Nuolatinė nuoroda į šį įrašą ↗- Įrašo identifikatorius
- info-comparison-sorting
- Versija
- university-reference.1
- Struktūruotas žinyno įrašas
- Universitetinis žinynas