Di algorîtmaya yekem de hejmara "X" bi her derbasbûnê çawa mezin dibe, û girîngiya vê mezinbûnê çi ye?
Di algorîtmaya yekem de mezinbûna hejmara "X" di têgihîştina tevliheviya hesabkerî û dema xebitandinê ya algorîtmayê de faktorek girîng e. Di teoriya tevliheviya hesabkerî de, vekolîna algorîtmayan balê dikişîne ser hejmartina çavkaniyên ku ji bo çareserkirina pirsgirêkê wekî fonksiyonek mezinahiya pirsgirêkê hewce dike. Çavkaniyek girîng a ku meriv li ber çavan bigire, dema ku ji bo pêkanîna algorîtmayek digire ye, ku pir caran li gorî hejmara operasyonên bingehîn ên ku têne kirin têne pîvandin.
Di çarçoveya algorîtmaya yekem de, em bihesibînin ku algorîtma li ser komek hêmanên daneyê dubare dike û li ser her hêmanek karekî diyar dike. Hejmara "X"yên di algorîtmê de çend carên ku ev kar tê kirin nîşan dide. Her ku algorîtma di her derbasbûnê de pêşve diçe, hejmara "X" dikare celebên cûda yên mezinbûnê nîşan bide.
Rêjeya mezinbûna hejmara "X" bi hûrguliyên taybetî yên algorîtmê û pirsgirêka ku ew armanc dike ku çareser bike ve girêdayî ye. Di hin rewşan de, mezinbûn dibe ku xêzik be, li cihê ku hejmara "X"-an bi pîvana têketinê re bi rêje zêde dibe. Mînakî, heke algorîtma her hêmanek di lîsteyê de tam carekê pêvajo bike, wê hingê hejmara "X" dê bi mezinahiya lîsteyê re wekhev be.
Ji hêla din ve, rêjeya mezinbûnê dikare ji rêzê cuda be. Ew dikare sublinear be, cihê ku hejmara "X"-an ji mezinahiya têketinê hêdîtir mezin dibe. Di vê rewşê de, dibe ku algorîtm hin taybetmendiyên pirsgirêkê bikar bîne da ku hejmara operasyonên hewce kêm bike. Mînakî, heke algorîtm stratejiyek dabeş-û-biserde bikar bîne, dibe ku hejmara "X"-yê bi mezinahiya têketinê bi logarîtmîkî mezin bibe.
Wekî din, rêjeya mezinbûnê dikare superlinear be, ku hejmara "X"-an ji mezinahiya têketinê zûtir mezin dibe. Ev dikare dema ku algorîtm dubareyên hêlînkirî pêk tîne an jî dema ku operasyonên algorîtmê ji şanek xêzikek hêsan tevliheviyek mezintir heye. Mînakî, heke algorîtma hêlînek hêlînek pêk bîne ku lûleya hundurîn li ser binkeyek kêmbûnê ya têketinê dubare dibe, dibe ku hejmara "X"-yê li gorî mezinahiya têketinê bi çargoşe an jî kubarî mezin bibe.
Fêmkirina rêjeya mezinbûna hejmara "X"-an girîng e ji ber ku ew ji me re dibe alîkar ku tevliheviya dema xebitandinê ya algorîtmê analîz bikin. Tevliheviya dema xebitandinê texmînek peyda dike ka wextê darvekirina algorîtmê bi mezinahiya têketinê re çawa dibe. Bi zanîna rêjeya mezinbûna hejmara "X"-an, em dikarin tevgera dema xebitandinê ya herî xirab, rewşa çêtirîn, an navînî ya algorîtmayê texmîn bikin.
Mînakî, heke hejmara "X"-yan bi mezinahiya têketinê re bi xêzik mezin bibe, em dikarin bibêjin ku algorîtma xwedan tevliheviyek dema xebitandinê ya xêz e, ku wekî O(n) tê destnîşan kirin, ku n mezinahiya têketinê temsîl dike. Ger hejmara "X"yan bi logarîtmî mezin bibe, algorîtma xwedan tevliheviyek logarîtmîkî ya dema xebitandinê ye, wekî O(log n) tê binavkirin. Bi heman awayî, heke hejmara "X"-an bi çargoşe an kubikî mezin bibe, algorîtmayê bi rêzdarî tevliheviyek dema xebitandinê ya çargoşe (O(n^2)) an kub (O(n^3)) heye.
Fêmkirina mezinbûna hejmara "X"-ên di algorîtmaya yekem de ji bo analîzkirina karîgerî û mezinbûna wê pêdivî ye. Ew dihêle ku em ji bo çareserkirina heman pirsgirêkê algorîtmayên cihêreng bidin ber hev û biryarên agahdar bidin ka kîjan algorîtmayê di pratîkê de bikar bînin. Digel vê yekê, ew di naskirina kêşan û xweşbînkirina algorîtmayê de dibe alîkar da ku performansa dema ajotinê baştir bike.
Mezinbûna hejmara "X"-ên di algorîtmaya yekem de aliyekî bingehîn e ji bo analîzkirina tevliheviya hesabkerî û dema xebitandinê. Bi têgihiştina ku hejmara "X"-an bi her derbasbûnê re çawa diguhezîne, em dikarin karîgerî û mezinbûna algorîtmê texmîn bikin, algorîtmayên cihêreng bidin ber hev, û di derbarê karanîna pratîkî ya wan de biryarên agahdar bidin.
Pirs û bersivên din ên vê dawiyê di derbarê Tevlîheviyê:
- Ma pola PSPACE ne bi pola EXPSPACE re wekhev e?
- Ma pola tevliheviya P binkomek pola PSPACE ye?
- Ma em dikarin îsbat bikin ku çîna Np û P yek in bi dîtina çareseriyek polînomî ya bikêr ji bo her pirsgirêkek bêkêmasî ya NP li ser TM-ya diyarker?
- Ma pola NP dikare bi çîna EXPTIME re wekhev be?
- Di PSPACE de pirsgirêk hene ku ji bo wan algorîtmaya NP-ya naskirî tune?
- Ma pirsgirêkek SAT dikare bibe pirsgirêkek tevahî NP?
- Ma dibe ku pirsgirêk di pola tevliheviya NP de be heke makîneyek ziravî ya ne diyarker hebe ku dê di dema pirnomî de wê çareser bike
- NP çîna zimanên ku xwedan verastkerên dema pirnomî ne
- Ma P û NP bi rastî heman çîna tevliheviyê ne?
- Ma her çarçoveyek zimanek azad e di pola tevliheviya P de?
Pir pirs û bersivan di Complexity de bibînin