Algorithm এর আপার এবং লোয়ার বাউন্ড বলতে কি বোঝানো হয়? কোন উদাহরণ দিয়ে কি বিস্তারিত আলোচনা করা যেতে পারে ? ধন্যবাদ।

asked 18 Jul '16, 07:31

shuddha7435's gravatar image

shuddha7435
349


ধরি আপনার নিচের মত একটা এরে আছে,

int myints[] = {10, 10, 10, 20, 20, 20, 30, 30};

এখন আপনি যদি ১০ এর জন্য lower bound বের করেন তবে সেটা হবে ১০ যেখান থেকে শুরু হইছে তার starting index এই ক্ষেত্রে ১০ আর starting index = 0 ।

যদি ১০ এর জন্য upper bound বের করেন, তবে সেটা হবে ১০ যেখান থেকে শেষ হইছে তার ইনডেক্স + ১ । এই ক্ষেত্রে ১০ এর ending index = 2 + 1 = 3 .

একই ভাবে ২০ এর জন্য lower bound = 3, upper bound = 6 হবে । অর্থাৎ আমরা বলতে পারি ,

lower_bound = starting index of a given value .

upper_bound = ending index of a given value + 1.

এখন আমরা একটি কোড দেখি,

#include < iostream >
#include < algorithm >
#include < vector >
using namespace std;
int main ()
{
    int myints[] = {10, 10, 10, 20, 20, 20, 30, 30};
    vector<int> v(myints,myints+8); // copy value of myinns to v

    vector<int> :: iterator low, up;

    low = lower_bound (v.begin(), v.end(), 20);
    up = upper_bound (v.begin(), v.end(), 20);

    cout << "lower_bound at position " << (low - v.begin()) << '\n';
    cout << "upper_bound at position " << (up - v.begin()) << '\n';

    return 0;
}

lower bound, upper bound বের করার আগে array কে অবশই সর্ট করে নিতে হবে । সেটা না করলে upper, lower bound বের করা যাবে না ।

ধন্যবাদ :)

permanent link

answered 18 Jul '16, 08:10

menon's gravatar image

menon
4.7k335

উত্তরটা ঠিক হয় নাই মনে হয়। অ্যালগরিদমের আপার বাউন্ড ও লোয়ার বাউন্ড-এর সাথে অ্যারের তো সম্পর্ক নাই। বরং কমপ্লেক্সিটির সম্পর্ক। সময় পেলে গুছিয়ে উত্তর দিবে পরে।

(02 Aug '16, 08:54) Tamim Shahriar Subeen ♦♦

আমি C++ STL #include < algorithm > এর upper_bound, lower_bound ধরে উত্তর দিয়েছি । আর আমার মনে হয় @shuddha7435 সেটাই জানতে চেয়েছে @Tamim Shahriar Subeen :) ধন্যবাদ ।

(02 Aug '16, 12:26) menon

অসাধারণ ভাইয়া। অনেক ধন্যবাদ।

permanent link

answered 02 Aug '16, 08:20

shuddha7435's gravatar image

shuddha7435
349

Your answer
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported

Question tags:

×37

question asked: 18 Jul '16, 07:31

question was seen: 888 times

last updated: 02 Aug '16, 12:26