Sqrt (သို့မဟုတ် Square Root) ပြိုကွဲခြင်းနည်းပညာ


ခက်ခဲအဆင့် ခိုင်မာသော
မကြာခဏမေးတယ် Cadence အိန္ဒိယ PayPal က Qualtrics Roblox Twilio
အခင်းအကျင်း ပြeryနာပြ.နာ

သငျသညျအကွာအဝေး၏မေးမြန်းမှုတစ်ခုကိန်းပေးထားကြသည် အခင်းအကျင်း။ ပေးထားသောစုံစမ်းမှုအကွာအဝေးတွင်ရှိသောနံပါတ်များအားလုံး၏ပေါင်းလဒ်ကိုဆုံးဖြတ်ရန်သင့်အားမေးမြန်းလိမ့်မည်။ ပေးထားသောစုံစမ်းမှုသည်အမျိုးအစားနှစ်မျိုးဖြစ်သည်။

Update: (index, value) ကို query အနေနဲ့ပေးထားတယ်။ နေရာမှာ index နေရာမှာ array ရဲ့ value ကို 'value' နဲ့ update ဖို့လိုတယ်။

Sum: (ဘယ်၊ ညာ) ကိုစုံစမ်းမှုတစ်ခုပေးထားပြီးအကွာအဝေးတွင်ရှိသောနံပါတ်များအားလုံးကိုစုပေါင်းဖော်ပြသည်။

နမူနာ

input

arr [] = {2,4,7,1,5,8,9,10,3,6}

စုစုပေါင်းမေးမြန်းမှု (0, 3)

စုစုပေါင်းမေးမြန်းမှု (4, 9)

အသစ်ပြောင်းခြင်း (၅၊ ၈)

စုစုပေါင်းမေးမြန်းမှု (3, 7)

output

14 0 နှင့် 3 အတွင်းရှိနံပါတ်များသည် 14 (2 + 4 + 7 + 1) ဖြစ်ပါသည်။

41 အကွာအဝေး 4 နှင့် 9 အတွင်းရှိနံပါတ်များ၏ပေါင်းလဒ်, 41 (5 + 8 + 9 + 10 + 3 + 6)

တန်ဖိုးကို array အဖြစ် [5] တွင်မွမ်းမံခြင်း။

33 0 နှင့် 3 အတွင်းရှိနံပါတ်များသည် ၁၄ (၁ + ၅ + ၈ + ၉ + ၁၀) ဖြစ်သည်။

algorithm

  1. n ၏နှစ်ထပ်ကိန်းရင်းတန်ဖိုးကို blockize အဖြစ်ရယူပြီးခင်းကျင်းပါလိမ့်မည်။
  2. input array ၏တန်ဖိုးကိုကျွန်ုပ်တို့ဖန်တီးထားသော array ထဲသို့ကူးယူပါ။ ထို့နောက် blockindex ၏တန်ဖိုးကို 1 တိုးပြီး arrind [i] ၏တန်ဖိုးကို blockindex ရှိ blockArray သို့ထပ်ထည့်ပါက indexes တစ်ခုခုကို blocksize အားဖြင့်စားလို့ရနိုင်လားစစ်ဆေးပါ။
  3. ပေးထားသောအကွာအဝေးအတွင်းရှိတန်ဖိုးကိုပေါင်းရန် sum ၏တန်ဖိုးကို ၀ သို့သတ်မှတ်ပါ။
  4. while loops သုံးခုကိုလိုက်နာပါ။ ဘယ်ဘက်သည်ညာဘက်တန်ဖိုးထက်လျော့နည်းသည်အထိ၊ ဘယ်ဘက်သည်သုညမဖြစ်သင့်၊ ဘယ်ဘက်သည်ပိတ်ဆို့မှု၏ထောင့်အိတ်မဖြစ်သင့်ပါ၊ ထို့နောက် array [left] ကိုပေါင်းလဒ်သို့ပေါင်းထည့်ပြီး ဘယ်ဘက်၏တန်ဖိုး။
  5. ဒီနေရာမှာ left plus blocksize သည်ညာဘက်ထက်နည်းသင့်သည်။ ထို့နောက် indexA ၏ left မှာ blockArray ၏တန်ဖိုးကို left နှင့် blocksize အဖြစ်နှင့် leftize ၏တန်ဖိုးကိုဘယ်ဘက်သို့ထည့်ပါ။
  6. ဒီမှာ left ဟာညာဘက်ထက်နည်းတယ်။ array [left] ကိုပေါင်းခြင်းနှင့် left ၏တန်ဖိုးကို 1 တိုးခြင်း, ပေါင်းလဒ်၏တန်ဖိုးကိုပြန်ပေးပါ။
  7. မည်သည့် update update မဆိုအတွက် index of division နှင့် blocksize ကိုယူပြီး array [index] ကို update လုပ်ရန်နှင့်နုတ်ရန်ပေးသောတန်ဖိုးကိုထည့်ပါ။ နောက်ဆုံးတွင် array [index] ရှိ 'value' ကို update လုပ်ပါ။

ရှင်းလင်းချက်

Square root ပြိုကွဲခြင်းသည် sqrt (n) ၏စတုရန်းအမြစ်၏စည်းကမ်းချက်များအရရှုပ်ထွေးမှုကိုလျှော့ချရန်မေးခွန်းများကိုဖြေရှင်းရန်နည်းလမ်းဖြစ်သည်။ ဒေတာတစ်ခုစီ၏ပေးထားသောအကွာအဝေးနှင့်နံပါတ်တစ်ခု၏စုစုပေါင်းအရေအတွက်ကိုရှာဖွေရန်ခင်းကျင်းခြင်းနှင့်ရှာဖွေမှုအကွာအဝေးကိုပေးထားခြင်းနှင့်အခြားလုပ်ငန်းတစ်ခုသည်ပေးထားသောအညွှန်းတွင်တန်ဖိုးကိုအသစ်ပြောင်းခြင်းဖြစ်သည်။ ဒါကြောင့်ဒီကိစ္စမှာကျွန်ုပ်တို့ကိုမေးခွန်းအချို့ပေးထားပြီး၎င်းကိုဖြေရှင်းဖို့လိုတယ်၊ နင့်နုံပါတဲ့ချဉ်းကပ်နည်းကိုသုံးပြီးဖြေရှင်းနိုင်တယ်။ ထိုချဉ်းကပ်မှုတွင်ကျွန်ုပ်တို့သည်လက်ဝဲနှင့်လက်ဝဲဘက်ရှိအကွာအဝေးအတွင်းရှိ array အတွင်းရှိ element တစ်ခုချင်းစီကိုထပ်ကာထပ်ကာ itterating ဖြင့်ဖြေရှင်းနိုင်ပြီးအကွာအဝေးရှိတန်ဖိုးအားလုံးကိုစုစည်းနိုင်သည်။ သို့သော်ဤချဉ်းကပ်မှုအတွက်ချဉ်းကပ်မှုတစ်ခုစီအတွက်အချိန်ရှုပ်ထွေးမှုသည် O (n) ဖြစ်လိမ့်မည်။ ။

ထို့ကြောင့်စုံစမ်းမှုများကိုအမြင့်ဆုံးထိရောက်စွာမြှင့်တင်ရန်ကျွန်ုပ်တို့သည်အချိန်ရှုပ်ထွေးမှုကိုလျှော့ချရန်ကျွန်ုပ်တို့အားကူညီခြင်းဖြင့်စတုရန်းအမြစ်ပြိုကွဲခြင်းကိုအသုံးပြုလိမ့်မည်။ ကျနော်တို့ n အရွယ်အစား n ပါဝင်သည်အရွယ်အစား n ၏ခင်းကျင်းယူဆနိုင်ပါတယ်။ ကျနော်တို့ခင်းကျင်းထားတဲ့ခင်းကျင်းမှုအပိုင်းကို sqrt (n) အတုံးအပိုင်းအစငယ်များသို့မဟုတ်အပိုင်းအစများအဖြစ်ခွဲမယ်။ စုံလင်သောစတုရန်းတိုင်းကိုနံပါတ်တစ်ခုအနေဖြင့်ကျွန်ုပ်တို့သည် sqrt (n) အတုံးများတိတိကျကျရှိလိမ့်မည်။ ဒီ array ရဲ့ဒီပြိုကွဲခြင်းနဲ့အတူ sqrt (n) လုပ်ကွက်များနှင့်တစ်ခုချင်းစီတွင်ရှိလိမ့်မည်။ n သည်ပြီးပြည့်စုံသောစတုရန်းဖြစ်လျှင် sqrt (n) element များရှိလိမ့်မည်။ n သည်ခင်းကျင်း၏အရွယ်အစားဖြစ်သည်။

၁၆ သည်ပြီးပြည့်စုံသောစတုရန်းတစ်ခုဖြစ်သောကြောင့်ကျွန်ုပ်တို့တွင် sqrt (16) လုပ်ကွက်များရှိသည်ဆိုပါစို့။ ကျွန်တော်တို့မှာလုပ်ကွက် ၄ ခုအတိအကျရှိမှာဖြစ်ပြီးတစ်ခုချင်းစီမှာ element ၄ ခုအတိအကျပါလိမ့်မယ်။ ပိတ်ပင်တားဆီးမှုတစ်ခုစီတွင်ကျွန်ုပ်တို့သည်တစ်ခုချင်းစီတွင်ရှိသောအရာအားလုံး၏ပေါင်းလဒ်ကိုရရှိလိမ့်မည်။ ဒါကြောင့်ကျနော်တို့မဆိုအကွာအဝေးမေးမြန်းမှု၏ပေါင်းလဒ်ထွက်ရှာတွေ့မှမေးလျှင်။ ကျွန်ုပ်တို့သည် sum ကို block များအသုံးပြုခြင်းအားဖြင့်အလွယ်တကူရှာနိုင်သည်။

Sqrt (သို့မဟုတ် Square Root) Decomposition နည်းစနစ်အတွက် C ++ ဖြင့်အကောင်အထည်ဖော်ခြင်း

#include<iostream>
#include<math.h>

using namespace std;


int arr[10000];
int blockArray[100];
int blockSize;

void buildArray(int input[], int n)
{
    int blockIndex = -1;

    blockSize = sqrt(n);

    for (int i=0; i<n; i++)
    {
        arr[i] = input[i];
        if (i%blockSize == 0)
        {
            blockIndex++;
        }
        blockArray[blockIndex] += arr[i];
    }
}

void update(int index, int value)
{
    int blockNumber = index / blockSize;
    blockArray[blockNumber] += value - arr[index];
    arr[index] = value;
}

int solveQuery(int left, int right)
{
    int sum = 0;
    while (left<right and left%blockSize!=0 and left!=0)
    {
        sum += arr[left];
        left++;
    }
    while (left+blockSize <= right)
    {
        sum += blockArray[left/blockSize];
        left += blockSize;
    }
    while (left<=right)
    {
        sum += arr[left];
        left++;
    }
    return sum;
}

int main()
{
    int inputArray[] = {2,4,7,1,5,8,9,10,3,6};
    int n = sizeof(inputArray)/sizeof(inputArray[0]);

    buildArray(inputArray, n);

    cout << "first Query : " << solveQuery(0, 3) << endl;
    cout << "second Query : " << solveQuery(4, 9) << endl;
    update(5, 8);
    cout << "third Query : " << solveQuery(3, 7) << endl;
    return 0;
}
first Query : 14
second Query : 41
third Query : 33

Sqrt (သို့မဟုတ် Square Root) Decomposition နည်းစနစ်အတွက် Java တွင်အကောင်အထည်ဖော်ခြင်း

class SquareRootDecomposition
{

    static int []arr = new int[10000];
    static int []blockArray = new int[100];
    static int blockSize;

    static void buildArray(int input[], int n)
    {
        int blockIndex = -1;

        blockSize = (int) Math.sqrt(n);

        for (int i = 0; i < n; i++)
        {
            arr[i] = input[i];
            if (i % blockSize == 0)
            {
                blockIndex++;
            }
            blockArray[blockIndex] += arr[i];
        }
    }

    static void update(int idx, int val)
    {
        int blockNumber = idx / blockSize;
        blockArray[blockNumber] += val - arr[idx];
        arr[idx] = val;
    }

    static int solveQuery(int left, int right)
    {
        int sum = 0;
        while (left<right && left%blockSize!=0 && left!=0)
        {
            sum += arr[left];
            left++;
        }
        while (left+blockSize <= right)
        {
            sum += blockArray[left/blockSize];
            left += blockSize;
        }
        while (left<=right)
        {
            sum += arr[left];
            left++;
        }
        return sum;
    }

    public static void main(String[] args)
    {
        int input[] = {2,4,7,1,5,8,9,10,3,6};
        int n = input.length;

        buildArray(input, n);

        System.out.println("first Query: " + solveQuery(0, 3));
        System.out.println("second Query : " + solveQuery(4, 9));
        update(5, 8);
        System.out.println("third Query : " + solveQuery(3, 7));
    }
}
first Query: 14
second Query : 41
third Query : 33

Sqrt (သို့မဟုတ် Square Root) ပြိုကွဲခြင်းနည်းပညာအတွက်ရှုပ်ထွေးမှုအားသုံးသပ်ခြင်း

အချိန်ရှုပ်ထွေး

အို (sqrt (n)) ဘယ်မှာ “ n” သည် array အတွင်းရှိ element အရေအတွက်ဖြစ်သည်။

အာကာသရှုပ်ထွေးမှု

အို (sqrt (n)) ဘယ်မှာ “ n” သည် array အတွင်းရှိ element အရေအတွက်ဖြစ်သည်။