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

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

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

Big-θ (বড়-থেটা) প্রতীক

লিনিয়ার সার্চের সাধারণ একটি উদাহরণ দেখা যাক:
var doLinearSearch = function(array, targetValue) {
  for (var guess = 0; guess < array.length; guess++) {
    if (array[guess] === targetValue) { 
        return guess;  // found it!
    }
  }
  return -1;  // didn't find it
};
Let's denote the size of the array (array.length) by n. The maximum number of times that the for-loop can run is n, and this worst case occurs when the value being searched for is not present in the array.
Each time the for-loop iterates, it has to do several things:
  • compare guess with array.length
  • compare array[guess] with targetValue
  • possibly return the value of guess
  • increment guess.
Each of these little computations takes a constant amount of time each time it executes. If the for-loop iterates n times, then the time for all n iterations is c1n, where c1 is the sum of the times for the computations in one loop iteration. Now, we cannot say here what the value of c1 is, because it depends on the speed of the computer, the programming language used, the compiler or interpreter that translates the source program into runnable code, and other factors.
This code has a little bit of extra overhead, for setting up the for-loop (including initializing guess to 0) and possibly returning -1 at the end. Let's call the time for this overhead c2, which is also a constant. Therefore, the total time for linear search in the worst case is c1n+c2.
আমরা দেখেছি, ধ্রুবক c1 এবং ছোট পদ c2 চলার সময়ের বৃদ্ধির হার সম্পর্কে কোন কিছু নির্দেশ করে না। উল্লেখযোগ্য বিষয় হল, লিনিয়ার সার্চের ওরস্ট কেস চলার সময় অ্যারের আকার n এর মত বৃদ্ধি পায়। এটির জন্য Θ(n) চিহ্ন ব্যবহার করা হয়। এটি হল গ্রিক অক্ষর "থেটা," এবং আমরা বলি "n এর বড়-থেটা" অথবা শুধু "n এর থেটা"।
চলার সময় হল Θ(n), এটি বলতে মূলত বোঝানো হয় যে, n যথেষ্ট বড় হলে, চলার সময় কমপক্ষে k1n হবে এবং সর্বোচ্চ k2n হবে যেখানে k1 এবং k2 হল ধ্রুবক। Θ(n) সম্পর্কে এভাবে চিন্তা করা যায়:
n ছোট মানের জন্য, চলার সময়কে k1n অথবা k2n এর সাথে তুলনা করার দরকার নেই। কিন্তু n যথেষ্ট বড় হলে—দাগ কাটা লাইনের উপরে বা ডানে যেদিকেই থাকুক—চলার সময় k1n এবং k2n এর মাঝামাঝি পর্যায়ে হবে। k1 এবং k2 ধ্রুবক থাকা পর্যন্ত, আমরা বলতে পারি চলার সময় হল Θ(n)
We are not restricted to just n in big-Θ notation. We can use any function, such as n2, nlog2n, or any other function of n. Here's how to think of a running time that is Θ(f(n)) for some function f(n):
একবার n যথেষ্ট বড় হলে, চলার সময় k1f(n) এবং k2f(n) এর মধ্যে হয়।
আসলে, আমরা ধ্রুবক এবং অন্যান্য ছোট পদ বাদ দেই। বড়-Θ ব্যবহার করার আরেকটি সুবিধা হল, সময়ের একক নিয়ে চিন্তা করতে হয় না। উদাহরণস্বরূপ, ধরি একটি চলার সময় হল 6n2+100n+300 মাইক্রোসেকেন্ড। অথবা এটি মিলিসেকেন্ডও হতে পারে। বড়-Θ চিহ্ন ব্যবহার করলে এটি বলার দরকার নেই। সহগ 6 এবং ছোট পদ 100n+300 বাদ দিয়ে বলা যায় যে, চলার সময় হল Θ(n2)
বড়-Θ চিহ্ন ব্যবহারের সময়, আমরা বোঝাই যে চলার সময়ে অ্যাসিম্পটোটিক সীমানার মধ্যে আছে। "অ্যাসিম্পটোটিকালি" কারণ এটি শুধুমাত্র বড় n মানের উপর নির্ভরশীল। "সীমানার মধ্যে" কারণ আমরা চলার সময়কে ধ্রুবকের মাঝামাঝি পর্যায়ে খুঁজে পেয়েছি।

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

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

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