Algoritmlar samaradorligini tahlil qilish

Асосий самарадорлик синфлари

• Самарадорликнни таҳлил қилиш тизими ўсиш тартиблари доимий кўпайтма билан фарқ қиладиган барча функцияларни бирлаштирган бўлса ҳам бундай функциялар кўп.
• Мисол учун кўрсаткичли функциялари а асосининг турли қийматлари учун турли хил ўсиш тартибига эга. Шунинг учун кўп сонли алгоритмларнинг вақт самарадорлиги фақат бир нечта синфларга тўғри келиши мумкин. Бу синфлар 1- жадвалда уларнинг номлари ва бир неста изоҳлари билан келтирилган.
• Алгоритмларни асимтотик самарадорлиги бўйича таснифлаш жуда кам амалий аҳамиятга эга. Чунки мултипликатив константаларнинг қийматлари одатда аниқланмаган. Бу ҳақиқий ўлчамдаги киришлар учун самаралироқ синфдаги алгоритмга қараганда самарасизроқ синфдаги алгоритмнинг тезроқ ишлаш имкониятини очиб беради.
• Мисол учун, агар бир алгоритмнинг ишлаш вақти n3 бўлса, иккинчисининг ишлаш вақти 106 n2 бўлса ва n 106 дан ошмаса, куб алгоритми квадратик алгоритмдан яхши ишлайди.

•  

Энг яхши самарадорликлардан жуда кам мантиқий мисоллар келтириш мумкин, чунки алгоритмнинг ишлаш вақти одатда кириш ҳажми чексиз катталашганда чексизгача боради.
Таржима
1-жадвал
Одатда, натижа муаммонинг ўлчамини алгоритмнинг ҳар бир итерациясида доимий омил билан кесишади. Шуни ёдда тутингки, логарифмик алгоритм унинг барча киришларини ёки ҳатто унинг қатъий бир қисмини ҳисобга олмайди: буни амалга оширадиган ҳар қандай алгоритм камида чизиқли ишлаш вақтига эга бўлади.
n ўлчамли рўйхатни сканерловчи алгоритмлар (масалан, кетма-кет қидириш) бу синфга тегишли.
divide-and-conquer алгоритмлари, ўртача ҳолатда бирлаштириш ва тезкор саралаш, шу тоифага киради.
Одатда, иккита ўрнатилган ҳалқали алгоритмларнинг самарадорлигини тавсифлайди. Элементар саралаш алгоритмлари ва нхн матрицалари устидаги айрим амаллар стандарт мисоллардир.
Одатда, учта ўрнатилган ҳалқа билан алгоритмларнинг самарадорлигини тавсифлайди. Чизиқли алгебрадан бир нечта notrivial алгоритмлар ушбу синфга киради.
n-элементлар тўпламининг барча кичик тўпламларини яратувчи алгоритмлар. Кўпинча, "eksponensial" атамаси ушбу ва каттароқ ўсиш тартибларини ўз ичига олиш учун кенгроқ маънода ишлатилади.
N-элемент тўпламининг барча алмаштиришларини ҳосил қилувчи алгоритмлар