የረጅም ጊዜ ቀጣይ ውጤት ግንባታ (N log N)


የችግር ደረጃ ጠንካራ
ውስጥ በተደጋጋሚ ተጠየቀ አማዞን ባንክ ባዛር Paytm ሳምሰንግ
ሰልፍ የሁለትዮሽ ፍለጋ ተለዋዋጭ ፕሮግራም

የችግሩ መግለጫ

አንድ ተሰጥቶሃል ደርድር of ኢንቲጀሮች. ችግሩ “ረጅሙ እየጨመረ የመጣ ቀጣይ ግንባታ (N log N)” ረጅሙ እየጨመረ የመጣውን ቀጣይነት ለመገንባት ይጠይቃል።

ለምሳሌ

arr[]={1, 4, 7, 2, 9, 6, 12, 3 }
12, 9, 7, 4, 1 and the size of this longest increasing subsequence is 5.

ማስረጃ

በአንድ ድርድር ውስጥ እየጨመረ ያለውን ረጅሙን ተከታይ እናገኛለን።

የረጅም ጊዜ ቀጣይ ውጤት ግንባታ (N log N)

ረዘም ላለ ጊዜ የሚጨምር ቀጣይ ውጤት ለመገንባት አልጎሪዝም (N log N)

1. Create two arrays lastIndexes and firstIndexes of size n, and initialize both of the arrays with 0 and -1 respectively.
2. Traverse the array from 1 to n(length of the array).
  1. Check if the current array element is less than the arr[lastIndexes[0]], if true, then update lastIndexes[0]=1.
  2. Check if the arr[i] is greater than the arr[lastIndexes[leng-1]], do the following
    1. Set the firstIndexes[i] to lastIndexes[leng-1].
    2. lastIndexes[leng++] = i.
  3. Else get the position of arr[i] using binary search and do the following.
    1. Update the value at firstIndexes[i] to lastIndexes[position-1].
    2. Update the value of the lastIndexes[position] to i.
3. Print the array, by initializing the value of i to the firstIndexes[i].

ማስረጃ

ብዙ ቁጥር ያላቸውን ቁጥሮች ሰጥተናል እናም እንዲገነቡ ጠይቀናል ረጅሙ እየጨመረ የሚሄድ. ለዚህም ሁለት ድርድሮችን lastIndexes እና firstIndexes እየተጠቀምን በቅደም ተከተል በ 0 እና -1 እሴት እንሞላለን ፡፡ firstIndexes array as 1. ይጀምራል ምክንያቱም ይህ እንደ እሴቶች እንደ እሴቶች እሴቶችን ያከማቻል ፡፡ ድርድርን እያለፍን እሴቶቹን እናዘምነዋለን።

ድርድርን ከ 1 ወደ n እናቋርጣለን ፡፡ የድርድሩ ርዝመት n የት ነው። በሚጓዙበት ጊዜ ፣ ​​ድርድር lastIndexes እንደ ድርድር አቀማመጥ ወይም ማውጫ ሆኖ ያገለግላል። የአሁኑ የድርድር አካል ከ lastIndexes [leng-1] ድርድር ያነሰ መሆኑን የምናይባቸውን አንዳንድ ሁኔታዎችን እንፈትሻለን። ርዝመት መጀመሪያ ላይ እንደ 1 ይገለጻል ፣ ይህም ማለት ቢያንስ የርዝመቱን ቀጣይነት እናገኛለን ማለት ነው 1. ስለዚህ ከላይ ያለው ሁኔታ እውነት ከሆነ የመጨረሻውን ኢንዴክስስ [0] ወደ 1 ያዘምኑ ፡፡

አርአይ [i] ከ lastIndexes ስብስብ [n-1] የበለጠ መሆኑን ማረጋገጥ አለብን። ከዚያ ሁለቱን ድርድር ያዘምኑ ፣ firstIndexes [i] ን ወደ lastIndexes የመጨረሻ እሴት [n-1] እና lastIndexes [leng] ን ወደ እኔ ያቀናብሩ እና የብድር ዋጋን ይጨምሩ። ሌላ እኛ የአሁኑን የድርድር አካል አቀማመጥ መፈለግ አለብን ፡፡ ለዚህም ፣ የሁለትዮሽ ፍለጋን እንጠቀምበታለን እና ያንን መረጃ ጠቋሚ ወደ ቦታው እናመጣለን ፡፡ የ lastIndexes [position-1] ዋጋን ወደ firstIndexes [i] እና lastIndexes [position] ን ወደ i ያዘምኑ።

ከተሻገረን በኋላ ድርድርን ማተም ያስፈልገናል። ለዚህም ከመጨረሻው ወደ 0 እናልፋለንth እያንዳንዱን መረጃ ጠቋሚ ወደ እያንዳንዱ የመጀመሪያ ማውጫ (ኢንዴክስ) [i] አቀማመጥ እና ማስጀመር (እያንዳንዱን) ከተሻገረ በኋላ እያንዳንዱን ሊገኝ የሚችል የደረጃ እሴት ማተም ፡፡

ኮድ

ረዘም ላለ ጊዜ ለሚቀጥለው ውጤት ግንባታ C + ኮድ (N log N)

#include<iostream>
#include<vector>

using namespace std;

int GetPosition(int arr[], vector<int>& T, int left, int right,int key)
{
    while (right - left > 1)
    {
        int mid = left + (right - left) / 2;
        if (arr[T[mid]] >= key)
            right = mid;
        else
            left = mid;
    }
    return right;
}
int LongestIncreasingSubsequence(int arr[], int n)
{
    vector<int> lastIndexes(n, 0);
    vector<int> firstIndexes(n, -1);

    int len = 1;
    for (int i = 1; i < n; i++)
    {
        if (arr[i] < arr[lastIndexes[0]])
        {
            lastIndexes[0] = i;
        }
        else if (arr[i] > arr[lastIndexes[len - 1]])
        {
            firstIndexes[i] = lastIndexes[len - 1];
            lastIndexes[len++] = i;
        }
        else
        {
            int positon = GetPosition(arr, lastIndexes, -1, len - 1, arr[i]);
            firstIndexes[i] = lastIndexes[positon - 1];
            lastIndexes[positon] = i;
        }
    }
    cout << "Longest Increase Subsequence:" << endl;
    for (int i = lastIndexes[len - 1]; i >= 0; i = firstIndexes[i])
        cout << arr[i] << " ";
    cout << endl;

    cout<<"LIS size:\n";

    return len;
}
int main()
{
    int arr[] = { 1, 4, 7, 2, 9, 6, 12, 3 };
    int n = sizeof(arr) / sizeof(arr[0]);

    cout<< LongestIncreasingSubsequence(arr, n);

    return 0;
}
Longest Increase Subsequence:
12 9 7 4 1
LIS size:
5

የጃቫ ኮድ ረዘም ላለ ጊዜ እየጨመረ ለሚመጣው ግንባታ ግንባታ (N log N)

import java.util.Arrays;

class LongestIncreasingSubsequence
{
    public static int GetPosition(int arr[], int T[], int left, int right, int key)
    {
        while (right - left > 1)
        {
            int mid = left + (right - left) / 2;
            if (arr[T[mid]] >= key)
                right = mid;
            else
                left = mid;
        }
        return right;
    }
    public static int getSubsequence(int arr[], int n)
    {
        int lastIndexes[] = new int[n];

        Arrays.fill(lastIndexes, 0);

        int firstIndexes[] = new int[n];

        Arrays.fill(firstIndexes, -1);

        int len = 1;

        for (int i = 1; i < n; i++)
        {
            if (arr[i] < arr[lastIndexes[0]])
                lastIndexes[0] = i;
            else if (arr[i] > arr[lastIndexes[len - 1]])
            {
                firstIndexes[i] = lastIndexes[len - 1];
                lastIndexes[len++] = i;
            }
            else
            {
                int positon = GetPosition(arr, lastIndexes, -1, len - 1, arr[i]);
                firstIndexes[i] = lastIndexes[positon - 1];
                lastIndexes[positon] = i;
            }
        }
        System.out.println("Longest Increasing Subsequence of given input");
        for (int i = lastIndexes[len - 1]; i >= 0; i = firstIndexes[i])
            System.out.print(arr[i] + " ");

        System.out.println();

        return len;
    }
    public static void main(String[] args)
    {
        int arr[] = { 1, 4, 7, 2, 9, 6, 12, 3 };
        int n = arr.length;

        System.out.print("LIS size:\n" + getSubsequence(arr, n)+"\n");
    }
}
Longest Increasing Subsequence of given input
12 9 7 4 1
LIS size:
5

 

ውስብስብነት ትንተና

የጊዜ ውስብስብነት

ኦ (n log n) በድርድሩ ውስጥ “n” የንጥሎች ብዛት የት ነው? የሎጋሪዝም ንጥረ ነገር የሚሰጠንን የሁለትዮሽ ፍለጋን ስለተጠቀምን። ግን ለእያንዳንዱ መረጃ ጠቋሚ የሁለትዮሽ ፍለጋን መጥራት ቢኖርብን ፡፡ ከዚያ በጣም በከፋ ሁኔታ ውስጥ ፣ የጊዜ ውስብስብነት O (N log N) ይሆናል።

የቦታ ውስብስብነት

ሆይ (n) በድርድሩ ውስጥ “n” የንጥሎች ብዛት የት ነው? እኛ ሁለት ጊዜያዊ ድርድር firstIndexes እና lastIndexes እንደፈጠርን ፡፡ የቦታ ውስብስብነት ይሆናል ኦ (ኤን).