JavaScript ալգորիթմներ և տվյալների կառուցվածքներ (մաս 4)

Գծային որոնում ընդդեմ Երկուական որոնումԱլգորիթմ

Գծային որոնում

Գծային որոնումն ամենապարզ մոտեցումն է, որն օգտագործվում է տվյալների հավաքածուում տարր որոնելու համար:

Խնդիր․Հաշվի առնելով «n» տարրերի զանգվածը և «t» թիրախային տարրը, գտե՛ք «t» ինդեքսը զանգվածում վերադարձնում է -1, եթե տարրի թիրախը չի գտնվել։

օրինակ՝ [-5,2,10,4,6], t=10 պետք է վերադարձնի 2

Այս խնդիրը կարելի է լուծել այս ֆունկցիայի միջոցով.

function linearSearch(array, target){
    for (let i = 0; i < array.length; i++) {
        if (Array[i] === target) {
            return i;
        }
    }
    return -1;
}

//Big O = O(n)

Բարդությունն այստեղ O(n) մակարդակի է, քանի որ մենք ունենք ընդամենը մեկ օղակ, որտեղ n-ի արժեքը նվազում է:

Երկուական որոնում

Երկուական որոնում, որը նաև հայտնի է որպես կես ինտերվալային որոնում, լոգարիթմական որոնումը որոնման ալգորիթմ է, որը գտնում է թիրախային արժեքի դիրքը տեսակավորված զանգվածում:

Երկուական որոնումըհամեմատում է թիրախային արժեքը զանգվածի միջին տարրի հետ: Եթե ​​դրանք հավասար չեն, ապա այն կեսը, որում թիրախը չի կարող պառկել, վերացվում է, և որոնումը շարունակվում է մնացած կեսի վրա՝ կրկին վերցնելով միջին տարրը՝ նպատակային արժեքի հետ համեմատելու համար և կրկնելով դա մինչև թիրախային արժեքը գտնվի: Եթե ​​որոնումն ավարտվում է մնացած կեսի դատարկությամբ, թիրախը զանգվածում չէ:

Խնդիր․ Հաշվի առնելով «n» տարրերի տեսակավորված զանգվածը և «t» նպատակային տարրը, գտեք «t» ինդեքսը զանգվածում վերադարձնում է -1, եթե տարրի թիրախը չի գտնվել։

Այս խնդիրը կարելի է լուծել DICHOTOMIC ալգորիթմի ներդրմամբ.

function Dichotomie(array, target){
    let leftIndex=0;
    let rightIndex=array.length-1;

    while (leftIndex <= rightIndex) {
        let middleIndex = Math.floor((leftIndex+rightIndex)/2);
        if (target === array[middleIndex]) {
            return middleIndex;
        }
        if (target < array[middleIndex]) {
            rightIndex = middleIndex - 1;       //At every iteration as here we reduce the value of n by two
        }
        else{
            leftIndex = middleIndex + 1;
        }
    }
    return -1;
}

//Big O = log(n) 

Բարդությունն այստեղ log(n) մակարդակի է, քանի որ մենք ունենք ինդեքսի արժեքը, որը յուրաքանչյուր անգամ բաժանվում է երկուսի:

Ո՞րն է իրական տարբերությունը Գծային որոնման և Երկուական որոնման ալգորիթմի միջև:

- Երկուական որոնումն աշխատում է միայն տեսակավորված զանգվածի վրա

-Գծային որոնումն ունի O(n) ժամանակային բարդություն

- Երկուական որոնումն ունի log(n) ժամանակային բարդություն

Շնորհակալություն դիտելու համար! Զգույշ եղեք, տղաներ: