If you're seeing this message, it means we're having trouble loading external resources on our website.

তোমার যদি কোন ওয়েব ফিল্টার দেওয়া থাকে, তাহলে দয়া করে নিশ্চিত কর যে *.kastatic.org এবং *.kasandbox.org ডোমেইনগুলো উন্মুক্ত।

মূল বিষয়বস্তু

ব্রেথ-ফার্স্ট সার্চ বিশ্লেষণ

ভার্টেক্স সেট V এবং এজ সেট E সহ একটি লেখচিত্র খুঁজতে, ব্রেথ-ফার্স্ট সার্চের কত সময় লাগবে? উত্তর হল, O, left parenthesis, V, plus, E, right parenthesis সময় লাগবে।
O, left parenthesis, V, plus, E, right parenthesis সময় অর্থ কি, তা এখন দেখা যাক। এখন, এই মুহূর্তের জন্য মনে করা যাক যে vertical bar, E, vertical bar, is greater than or equal to, vertical bar, V, vertical bar, বেশিরভাগ লেখচিত্রের ক্ষেত্রেই এটি প্রযোজ্য, বিশেষ ভাবে যে লেখচিত্রের জন্য আমরা ব্রেথ-ফার্স্ট সার্চ ব্যবহার করব। তাহলে, vertical bar, V, vertical bar, plus, vertical bar, E, vertical bar, is less than or equal to, vertical bar, E, vertical bar, plus, vertical bar, E, vertical bar, equals, 2, dot, vertical bar, E, vertical bar। কারণ আমরা অ্যাসিম্পটটিক নোটেশনে (asymptotic notation) ধ্রুবক গুণনীয়কগুলোকে উহ্য করি, সেকারণে আমরা যখন vertical bar, E, vertical bar, is greater than or equal to, vertical bar, V, vertical bar, O, left parenthesis, V, plus, E, right parenthesis দেখি, আসলে এটির অর্থ দাড়ায় O, left parenthesis, E, right parenthesis। এখন যদি আমাদের কাছে vertical bar, E, vertical bar, is less than, vertical bar, V, vertical bar থাকে, তাহলে vertical bar, V, vertical bar, plus, vertical bar, E, vertical bar, is less than or equal to, vertical bar, V, vertical bar, plus, vertical bar, V, vertical bar, equals, 2, dot, vertical bar, V, vertical bar এবং এটির O, left parenthesis, V, plus, E, right parenthesis মুলত অর্থ দাড়ায় O, left parenthesis, V, right parenthesis। আমরা উভকেই এভাবে বলতে পারি যে, O, left parenthesis, V, plus, E, right parenthesis এটি আসলে এই O, left parenthesis, \max, left parenthesis, V, comma, E, right parenthesis, right parenthesis অর্থটি প্রকাশ করে। সাধারনভাবে বলতে গেলে, আমাদের কাছে যদি x এবং y এর প্যারামিটার থাকে, তাহলে এই O, left parenthesis, x, plus, y, right parenthesis এর অর্থ দাঁড়াবে O, left parenthesis, \max, left parenthesis, x, comma, y, right parenthesis, right parenthesis
(এখান লক্ষ্য করলে দেখা যাবে যে, এখানে একটি লেখচিত্র সংযুক্ত থাকবে যদি প্রতিটি শীর্ষবিন্দু থেকে অন্যান্য যে উলম্বগুলো আছে তার প্রতিটিতে একটি করে পথ থাকে। একটি গ্রাফের সর্বনিম্ন যতসংখ্যক মান থাকতে পারবে এবং যতসংখ্যকবার সংযুক্ত থাকতে পারে সেটা হল vertical bar, V, vertical bar, minus, 1। একটি লেখচিত্র যেখানে vertical bar, E, vertical bar, equals, vertical bar, V, vertical bar, minus, 1 আর এটাকে বলা হয় একটি free tree।)
O, left parenthesis, V, plus, E, right parenthesis সময়ে ব্রেডথ-ফার্স্ট সার্চ কীভাবে রান করে? এখানে প্রতিটি শীর্ষবিন্দুর দূরত্ব রান করানোর জন্য O, left parenthesis, V, right parenthesis সময় প্রয়োজন হয় (\Theta, left parenthesis, V, right parenthesis সময়)। প্রতিটি শীর্ষবিন্দুতে সর্বোচ্চ একবার যাওয়া হবে, কারণ শুধুমাত্র প্রথমবারই এটা এর দূরত্বে পৌঁছাচ্ছে যেটা হল null এবং তাই প্রতিটি শীর্ষবিন্দু সর্বোচ্চ একবার সারি আকারে থাকছে। যেহেতু যখন আমরা এই শীর্ষবিন্দু থেকে চলে আসছি শুধুমাত্র তখনই শীর্ষবিন্দুগুলো পরীক্ষা করে দেখছি তাই প্রতিটি প্রান্তবিন্দু সর্বোচ্চ দুইবার আমরা পরীক্ষা করে দেখতে পারব, যে শীর্ষবিন্দুগুলোতে এই ঘটনাগুলো আছে তার প্রতিটির জন্য একবার করে। সুতরাং, ব্রেডথ-ফার্স্ট সার্চ শীর্ষবিন্দু খুঁজে বের করতে O, left parenthesis, V, plus, E, right parenthesis সময় ব্যয় করবে।

এই বিষয়বস্তুটি Dartmouth Computer Science এর প্রফেসর Thomas Cormen এবং Devin Balkcom এর সহযোগিতায় এবং একই সাথে খান একাডেমির কম্পিউটিং শিক্ষাক্রম দলের একসাথে কাজ করার মাধ্যমে তৈরি করা হয়েছে। এই বিষয়বস্তু CC-BY-NC-SA দিয়ে লাইসেন্সকৃত।