Video: Որո՞նք են երկուական որոնման ծառի ամենավատ դեպքերը և դեպքերի միջին բարդությունը:
2024 Հեղինակ: Lynn Donovan | [email protected]. Վերջին փոփոխված: 2023-12-15 23:48
Երկուական որոնման ծառ
| Ալգորիթմ | Միջին | Վատագույն դեպքում |
|---|---|---|
| Տիեզերք | Վրա) | Վրա) |
| Որոնում | O (log n) | Վրա) |
| Տեղադրեք | O (log n) | Վրա) |
| Ջնջել | O (log n) | Վրա) |
Բացի այդ, ո՞րն է երկուական որոնման ծառի ամենավատ ժամանակային բարդությունը:
Ա–ի ռեկուրսիվ կառուցվածքը ԲՍՏ տալիս է ռեկուրսիվ ալգորիթմ: Որոնում մեջ ԲՍՏ ունի Օ (ը) ամենավատը - գործ գործարկման ժամանակը բարդություն , որտեղ h-ի բարձրությունն է ծառ . Քանի որ ս երկուական որոնման ծառ n հանգույցներով ունի նվազագույնը Օ (log n) մակարդակները, դա տեւում է առնվազն Օ (log n) համեմատություններ՝ որոշակի հանգույց գտնելու համար:
Երկրորդ, ո՞րն է կրկնակի որոնման ժամանակային բարդությունը: -ի կատարումը Երկուական որոնման ալգորիթմ : Հետևաբար, Երկուական որոնման ալգորիթմի ժամանակային բարդությունը O (log2ժդ) որը շատ արդյունավետ է: Նրա կողմից օգտագործվող օժանդակ տարածքը O(1) է կրկնվող իրականացում և O(log2ժդ) ռեկուրսիվ իրականացման համար՝ կապված զանգերի կույտի հետ:
Նաև հարցն այն է, թե որն է լինելու երկուական որոնման ծառում տարրը որոնելու վատագույն ժամանակային բարդությունը:
Ժամանակի բարդություն : The ամենավատ դեպքի ժամանակի բարդությունը -ից որոնում իսկ ներդիրի գործողությունները O(h) է, որտեղ h-ը բարձրությունն է Երկուական որոնման ծառ . Մեջ վատագույն դեպքում , մենք մայիս ունեն դեպի ճանապարհորդություն արմատից դեպի ամենախորը տերևային հանգույցը: Շեղվածի բարձրությունը ծառ կարող է դառնալ n և ժամանակի բարդություն -ից որոնում և տեղադրման գործողությունը մայիս դառնալ O(n):
Արդյո՞ք Big O-ն ամենավատ դեպքն է:
Այսպիսով, երկուական որոնման մեջ լավագույնը գործ է Օ (1), միջին և վատագույն դեպքում է Օ (մուտք): Մի խոսքով, տիպի հարաբերություններ չկան. մեծ Օ համար օգտագործվում է վատագույն դեպքում , Theta միջին գործ »: Բոլոր տեսակի նշումները կարող են օգտագործվել (և երբեմն օգտագործվում են) լավագույնի, միջինի կամ վատագույն դեպքում ալգորիթմի.
Խորհուրդ ենք տալիս:
Արդյո՞ք երկուական ծառի կույտ է:
Երկուական կույտը ամբողջական երկուական ծառ է, որը բավարարում է կույտ պատվիրելու հատկությունը: max-heap հատկությունը. յուրաքանչյուր հանգույցի արժեքը փոքր է կամ հավասար է իր մայրի արժեքին, իսկ արմատում առավելագույն արժեք ունեցող տարրը
Որոնք են որոնման համակարգերը, որոնք փնտրում են այլ որոնման համակարգեր:
Մեր որոնողական արկածը սկսելու համար եկեք դիտարկենք մի քանի ընդհանուր որոնման համակարգեր, որոնք դուրս են լավագույն երեքից: DuckDuckGo. Մտահոգվա՞ծ եք առցանց գաղտնիության համար: Որոնել գաղտնագրել: Փնտրու՞մ եք DuckDuckGo-ի այլընտրանք: Էկոզիա. Ուզու՞մ եք ծառեր տնկել, մինչ դուք փնտրում եք: Շան կույտ. Բլեկկո. ՎոլֆրամԱլֆա. Գիգաբլաստ. Facebook որոնում
Ինչպե՞ս գտնել երկուական որոնման կեսը:
Հաշվի առնելով տեսակավորված զանգվածը՝ մենք գտնում ենք ամենամիջին տարրը և ստեղնով ստուգում տարրը: Եթե ամենամիջին տարրը հավասար է բանալիին, մենք գտել ենք բանալին: Եթե ամենամիջին տարրը մեծ է բանալինից, մենք որոնում ենք ամենամիջին տարրի ձախ կեսում, հակառակ դեպքում՝ աջ կեսում:
Ինչպե՞ս եք իրականացնում երկուական որոնման ծառը Java-ում:
Երկուական որոնման ծառի (BST) ներդրում Java-ում Հանգույցի ձախ ենթածառը պարունակում է միայն հանգույցներ, որոնց բանալիները պակաս են, քան հանգույցի բանալին: Հանգույցի աջ ենթածառը պարունակում է միայն հանգույցներ, որոնց բանալիներն ավելի մեծ են, քան հանգույցի բանալին: Ձախ և աջ ենթածառը պետք է լինի նաև երկուական որոնման ծառ: Կրկնվող հանգույցներ չպետք է լինեն
Ո՞րն է երկուական որոնման մեծ O-ն:
Երկուական որոնումն ավելի արագ է, քան գծային, բացառությամբ փոքր զանգվածների: Երկուական որոնման ալգորիթմ. Երկուական որոնման ալգորիթմի պատկերացում, որտեղ 7-ը թիրախային արժեքն է Դասի որոնման ալգորիթմ Լավագույն դեպքի կատարումը O(1) Միջին կատարումը O(log n) Տարածության վատագույն բարդությունը O(1)