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

Қадамларнинг самарадорликка таъсири

Шелл усули учун қадамлар кетма-кетлигини танлаш ҳал қилувчи таъсирни кўрсатиши мумкин, аммо оптимал қадамларни қидириш дастлабки натижага олиб келмади. Мумкин бўлган барча вариантлар ўрганилди ва уларнинг натижаси қуйида келтирилади.

Агар ўтишлар ҳаммаси иккита бўлса, у ҳолда биринчи ўтишда қийинликка ва иккинчи ўтишда қийинликка эга бўламиз.

Бошқа мумкин бўлган қадамлар тўплами барча j лар учун шаклга эга ва ҳолда. Бу қийматлар ва тенгликлар билан таъминланади, шунинг учун улардан энг каттасини аниқлаб қолганларини формула билан ҳисоблашимиз мумкин. бундай қадамлар кетма-кетлиги алгоритмга қийинлик беради.

Яна бир вариант рўйхат узунлигидан кичик бар ча қийматларини ҳисоблашни кўриб чиқишдир (ихтиёрий бутун i ва j да); қийматларни ҳисоблаш камайиш тартибида амалга оширилади. Масалан, N–40 да қадамларнинг қуйидаги кетма-кетлиги бўлади: 36(2²3²), 32(2⁵3⁰), 27(2⁰3³), 24(2³3²), 18(2¹3²), 16(2⁴3⁰), 12(2²3¹), 9(2⁰3²), 8(2³3⁰), 6(2¹3¹), 4(2²3⁰), 3(2⁰3¹), 2(2¹3⁰), 1(2⁰3⁰). Бундай кетма-кетлик ёрдамида Шелл усули қийинлиги O(N(logN))га қадар камаяди. Сезиш керакки, ўтишларнинг катта сони кераксиз сарфларни кўпайтиради, шунинг учун бу кетма-кетликларни кичик рўйхатларда қўллаш самара бермайди.

Шелл усули — бу саралашнинг умумий шакли бўлиб, параметрларни танлаш унинг самарадорлигига сезиларли таъсир кўрсатади.