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

1.1.1. Маълумотлар синфлари
Кирувчи маълумотларнинг алгоритмларнинг таҳлилида ўта катта аҳамият касб этади, мадомики алгоритмнинг ҳаракат кетма-кетлиги кирувчи маълумотларни охирги ўринда қарамайди. Масалан, N элементдан иборат рўйхатдан энг катта элементни топиш учун қуйидаги алгоритмдан фойдаланиш мумкин:
largest = list [1]
for i = 2 to N do
if (list [i] > largest) then
largest = list[i]
end if
end for
Тушунарлики, агар рўйхат камайиш тартибида тартибланган бўлса, у ҳолда цикл бошланишидан олдин битта таъминлаш бажарилади, цикл ичида эса таъминлаш бажарилмайди. Агар рўйхат ўсиш тартибида тартибланган бўлса, у ҳолда ҳаммаси бўлиб N таъминлаш бажарилади (битта цикл олдидан ва N-1 цикл ичида). Таҳлил чоғида биз кирувчи қийматларнинг мумкин бўлган турли хил тўпламини қарашимиз керак. Агар биз битта тўплам билан чеклансак у ҳолда у ечимнинг жуда тез (ёки жуда секин) бўлишига олиб келиши мумкин. Натижада биз алгоритм ҳақидаги нотўғри тасаввурга эга бўламиз. Бунинг ўрнига биз кирувчи тўпламларнинг барча турини қараймиз.
Биз турли хил кирувчи тўпламларни алгоритмнинг ҳар бир тўпламдаги хусусиятига боғлиқ равишда синфларга ажратишга ҳаракат қиламиз. Бундай ажратиш кўриладиган имкониятлар сонини камайтиради. Масалан, 10 та ҳар хил сонларни рўйхтага турлича жойлаштиришлар сони 10!= 3 628 800 га тенг. 10 та сондан иборат рўйхатга энг катта элементни топиш алгоритмини қўллаймиз. Биринчи сони энг катта бўлган 362 880 та кирувчи тўпламларга эга бўламиз, уларнинг барчасини бир синфга киритиш мумкин. Агар катталиги бўйича энг катаси 2 ўринда турган бўлса, у ҳолда алгоритм икки таъминлаш бажаради. Бундай тўпламлар сони ҳам 362 880 ни ташкил қилади, уларни бошқа синфга киритиш мумкин. Кўриниб турибдики, энг катта соннинг ўрнини 1 дан N гача алмаштириш билан таъминлашлар сони ҳам ўзгаради. Шу сабабли биз барча кирувчи тўпламларни қилинган таъминлашларги кўра N та турли синфларга бўлишимиз керак. кўриб турибсизки ҳар бир синфга кирувчи барча тўпламларни ёзиб чиқишнинг ёки тавсифлашнинг зарурати йўқ. Синфларлар сонини ва ҳар синф тўпламидаги иш ҳажмини билиш керак холос.
Кирувчи маълумотларнинг мумкин бўлган тўплами сони N нинг ошиши билан жуда катта бўлиши мумкин. Масалан, 10 та турли сонларни рўйхатга 3 628 800 усул билан жойлаштириш мумкин. Бу усулларнинг барчасини кўриб чиқишнинг имкони йўқ. Бунинг ўрнига биз рўйхатларни алгоритмнинг нима қилишига боғлиқ равишда синфларга ажратамиз. Юқорида кўрсатилган алгоритм учун ажратиш энг катта қийматнинг жойлашувига асосланади. Натижада 10 та турли синфлар ҳосил бўлади. Бошқа алгоритм учун, масалан, энг катта ва энг кичик қийматни топиш алгоритмида бизнинг ажратишлар энг катта ва энг кичик қийматнинг қаерда жойлашганлигига асосланиши мумкин. Бундай ажратишлар 90 синфни ташкил қилади. Биз синфларни ажратиб олгач, ҳар синфдаги бир тўпламда алгоритмнинг ҳолатини кўришимиз мумкин. Агар синфлар тўғри танланган бўлса, у ҳолда бир синфдаги барча кирувчи тўпламларда алгоритм бир хил сондаги амаллар бажаради, бошқа синфдаги тўпламларда эса бу амаллар сони бошқача бўлади.