Мундарижа Кириш

1.4.1. Баҳолаш мезонини усуллари

Алгоритм мураккаблиги ўсиш тезлиги муҳим аҳамият касб этади ва биз кўрдикки, ўсиш тезлиги формуланинг юқори устун қисми билан аниқланади. Шунинг учун секин ўсувчи кичик қисмларни қисқартирамиз. Барча кичик қисмларни ташлаб юбориб функциянинг ёки алгоритмнинг тартиби деб номланувчи мураккаблик ўсиш тезлигига эга бўламиз. Алгоритмларни мураккаблигини уларнинг ўсиш тезликлари бўйича гуруҳлаштириш мумкин. биз уч категорияни киритамиз: мураккаблиги ҳеч бўлмаганда ушбу фунция тезлигидек ўсадиган алгоритмлар, мураккаблиги ҳудди шундай тезликда ўсадиган алгоритмлар ва мураккаблиги ушбу функциядан секин ўсадиган алгоритмлар.

Катта Омега

Ҳеч бўлмаганда f функция тезлигида ўсувчи функциялар синфини билан белгилаймиз (катта омега деб ўқилади). д функция ушбу синфга тегишли, агар n аргументнинг барча қийматларида қандайдир мусбат с сони учун тенгсизлик бажарилса. синф ўзининг пастки чегарасини беради, яъни ундаги барча функциялар ҳеч бўлмаганда f дек тез ўсади.

Биз алгоритмларнин самарадорилги билан шуғулланамиз, шунинг учун синф бизни унчалик қизиқтирмайди. Масалан, га n²дан кўра тез ўсувчи функциялар (n³ ва 2ⁿ) киради.