|
Ózbekstan respublikasí sanli texnologiyalar ministrligi muhammed al-xorezmiy atindaǵÍ tashkent informaciyalíq texnologiyalarí universiteti nókis filialí telekommunikaciya texnologiyalari hám kásiplik tálim fakulteti «Informaciyalıq
|
| bet | 4/5 | | Sana | 01.11.2023 | | Hajmi | 264.17 Kb. | | #92450 |
Bog'liq Usnatdinov Islam Magliwmatlar strukturasi oz betinshe Faza va nol farqi, zazemleniya, anatatsiya, Yo\'l-yo\'l, Usnatdinov Islam Magliwmatlar strukturasi oz betinshe, Reja Mehnat unumdorligi va uning ahamiyati, Saliev mag.str word, essay, Qiziqarli fizika. PhysicsUzb , Atom yadro fizikasidan laboratoriya ishlari qo\'lanmasi, Nazirov Jamshid, 11-mavzu, Xf6v40aysSs CaTyRQfdkRubDxQNpheG (1), 26003769, 2-mavzu Sahna.Eń jaman jaǵday analizi
Joqarıda kórgenimizdey, dizimniń qalǵan bólimlerinde barlıq ótiwde ekiniń dárejeleri birge azayadı. Taǵı cikldıń aqırǵı iteratsiyasi qalǵan bólim ólshemi 1 ge teń bolǵanda atqarıladı. Bul bolsa j=1(yaǵnıy 21-1=1) da orınlanadı. Bul sonı korsetedi, N=2k-1 da otiwler sania k dan aspaydı. Aqırǵı teńlikden eń jaman jaǵdayda otiwler sanı k=log2(N+1) ǵa teńligin tabamız.Analizde izlew procesi ushın sheshim teregi de járdem beriwi múmkin. Sheshim teregi túyinlerinde uyqas ótiwde tekseriletuǵın elementler turadı. Jeti elementten ibarat dizim ushın sheshim teregi 2-suwretde keltirilgen. Ulıwma halda terekke salıstırǵanda balanslastırılgan, yaǵnıy biz mudamı dizim túrli bólimleriniń ortasın tańlaymiz. Sol sebepli salıstırıwlar sanın sanaw ushın binar terekler ushın keltirilgen formulalardan paydalanamız.Biz N=2k-1 dep oylar ekenbiz mas keliwshi sheshim teregi hár dayım tolıq boladı. Onda k dáreje, yaǵnıy k=log2(N+1) boladı. Biz har qaysı dárejede birewden salıstırıp atırmız, sonıń ushın salıstırıwlar ulıwma sanı log2(N+1) dan aspaydı.
2-suwret. Jeti elementli dizimde izlew ushın sheshim teregi
Ortasha jaǵday analizi
Tap izbe-iz izlew algoritmındaǵı sıyaqlı analizde eki jaǵdaydı qaraymız. Birinshisi izlengen mánis dizimde anıq ámeldegi jaǵday hám ekinshisi ol ulıwma joq jaǵday. Birinshi jaǵdayda izlengen mánis ushın múmkin bolǵan jaǵdaylar sanı N hám olar teń itimallı hám de olardıń hár biri 1/N ga teń. Eger izlew procesin xarakteristikalawshı binar terekti qaraytuǵın bolsaq, ol halda 1 dárejede terek túbir elementinen izlew ushın bir salıstırıw, ekinshi dárejedegi túyinler elementlerinen izlew ushın eki salıstırıw hám úshinshi dárejede úsh salıstırıw talap etiledi. Ulıwma i dárejedegi elementlerden izlew ushın i salıstırıw talab etiledi. i dárejede 2i-1 ta túyin bar hám N=2k-1 da terekte k dáreje bar. Bul mınada, barlıq múmkin bolǵan hallar ushın tolıq salıstırıwlar sanın hár qaysı dárejedegi salıstırıwlardı túyinler sanına kóbeymeleriniń jıyındısın esaplap tabıw múmkin. Nátiyjede ortasha jaǵday analizi tómendegin beredi: ( ushın)
Endi izlenip atırǵan mánis dizimde ámeldegi bolmaǵan jaǵdaydı qaraymız. Elementtiń múmkin bolǵan jaǵdayları sanı N ga teń, biraq bul jaǵdayda taǵı N + 1 izlenip atırǵan mánis dizimde joq ekenligi ushın múmkinshilikler bar. Múmkinshilikler sanı N + 1 ge teń, yaǵnıy izlengen mánis dizimdegi birinshi elementten kishi, birinshiden úlken ekinshiden kishi, ekinshiden úlken úshinshiden kishi hám t.b. izlengen mánis N elementten úlken bolıwı múmkin. Hár qaysı bul elementler joq ekenligi jaǵdaylar k salıstırıwda atqarıladı. Hámmesi bolıp esaplawda 2 N + 1 múmkinshilikler qatnasadı. Aqır-aqıbetde, payda etemiz: uchun.
Joqarıdaǵı kibi almastırıwlar tómendegini beredi:
ushın.
Aqırǵı teńlik element dizimde bar bolǵan jaǵdayda nátiyjeni parqsız asıradı. Mısalı 2020 -1=1 048 575 elementten ibarat dizim ushın birinshi halda 19 ǵa jaqın nátiyjege, ekinshi halda 19. 5 ke jaqın nátiyjege iye bolamız.
|
|
Bosh sahifa
Aloqalar
Bosh sahifa
Ózbekstan respublikasí sanli texnologiyalar ministrligi muhammed al-xorezmiy atindaǵÍ tashkent informaciyalíq texnologiyalarí universiteti nókis filialí telekommunikaciya texnologiyalari hám kásiplik tálim fakulteti «Informaciyalıq
|
