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

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

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

একটি অনুমানের খেলা

Let's play a little game to give you an idea of how different algorithms for the same problem can have wildly different efficiencies. The computer is going to randomly select an integer from 1 to 16. You'll keep guessing numbers until you find the computer's number, and the computer will tell you each time if your guess was too high or too low:
Once you've found the number, reflect on what technique you used when deciding what number to guess next.
Maybe you guessed 1, then 2, then 3, then 4, and so on, until you guessed the right number. We call this approach linear search, because you guess all the numbers as if they were lined up in a row. It would work. But what is the highest number of guesses you could need? If the computer selects 16, you would need 16 guesses. Then again, you could be really lucky, which would be when the computer selects 1 and you get the number on your first guess. How about on average? If the computer is equally likely to select any number from 1 to 16, then on average you'll need 8 guesses.
But you could do something more efficient than just guessing 1, 2, 3, 4, …, right? Since the computer tells you whether a guess is too low, too high, or correct, you can start off by guessing 8. If the number that the computer selected is less than 8, then because you know that 8 is too high, you can eliminate all the numbers from 8 to 16 from further consideration. If the number selected by the computer is greater than 8, then you can eliminate 1 through 7. Either way, you can eliminate about half the numbers. On your next guess, eliminate half of the remaining numbers. Keep going, always eliminating half of the remaining numbers. We call this halving approach binary search, and no matter which number from 1 to 16 the computer has selected, you should be able to find the number in at most 4 guesses with this technique.
এখন 1 থেকে 300 এর মধ্যে একটি সংখ্যা নিয়ে চেষ্টা করা যাক। সংখ্যাটি 9 বারের বেশি অনুমান করা লাগবে না।
এইবার সঠিক সংখ্যাটি নির্ণয় করার জন্য কত বার অনুমান করতে হল? কেন 9 বারের বেশি অনুমান করতে হয়নি? (তুমি কি এর একটি গানিতিক ব্যাখ্যা চিন্তা করতে পার)?
আমরা আবার বাইনারি সার্চে ফিরে আসব এবং আমরা জাভাস্ক্রিপ্ট অ্যারেতে কোন কিছু খুঁজে বের করার জন্য কীভাবে এই বাইনারি সার্চ ব্যবহার করতে পারি তা দেখবো। কিন্তু প্রথমে আমরা অ্যালগোরিদম সম্পর্কিত বড় সমস্যাগুলো দেখবো।

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

আলোচনায় অংশ নিতে চাও?

কোন আলাপচারিতা নেই।
ইংরেজি জানো? খান একাডেমির ইংরেজি সাইটে আরো আলোচনা দেখতে এখানে ক্লিক কর।