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

কম্পিউটার বিজ্ঞান

কোর্স: কম্পিউটার বিজ্ঞান > অধ্যায় 1

পাঠ 3: এ্যাসিম্প্টোটিক নোটেশান

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

c_{1} \cdot n

, where

c_{1}

is the sum of the times for the computations in one loop iteration. Now, we cannot say here what the value of

c_{1}

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

c_{2}

, which is also a constant. Therefore, the total time for linear search in the worst case is

c_{1} \cdot n + c_{2}

আমরা দেখেছি, ধ্রুবক

c_{1}

এবং ছোট পদ

c_{2}

চলার সময়ের বৃদ্ধির হার সম্পর্কে কোন কিছু নির্দেশ করে না। উল্লেখযোগ্য বিষয় হল, লিনিয়ার সার্চের ওরস্ট কেস চলার সময় অ্যারের আকার

n

এর মত বৃদ্ধি পায়। এটির জন্য

Θ (n)

চিহ্ন ব্যবহার করা হয়। এটি হল গ্রিক অক্ষর "থেটা," এবং আমরা বলি "

n

এর বড়-থেটা" অথবা শুধু "

n

এর থেটা"।

চলার সময় হল

Θ (n)

, এটি বলতে মূলত বোঝানো হয় যে,

n

যথেষ্ট বড় হলে, চলার সময় কমপক্ষে

k_{1} \cdot n

হবে এবং সর্বোচ্চ

k_{2} \cdot n

হবে যেখানে

k_{1}

এবং

k_{2}

হল ধ্রুবক।

Θ (n)

সম্পর্কে এভাবে চিন্তা করা যায়:

n

ছোট মানের জন্য, চলার সময়কে

k_{1} \cdot n

অথবা

k_{2} \cdot n

এর সাথে তুলনা করার দরকার নেই। কিন্তু

n

যথেষ্ট বড় হলে—দাগ কাটা লাইনের উপরে বা ডানে যেদিকেই থাকুক—চলার সময়

k_{1} \cdot n

এবং

k_{2} \cdot n

এর মাঝামাঝি পর্যায়ে হবে।

k_{1}

এবং

k_{2}

ধ্রুবক থাকা পর্যন্ত, আমরা বলতে পারি চলার সময় হল

Θ (n)

।

We are not restricted to just

n

in big-Θ notation. We can use any function, such as

n^{2}

n \log_{2} n

, 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

যথেষ্ট বড় হলে, চলার সময়

k_{1} \cdot f (n)

এবং

k_{2} \cdot f (n)

এর মধ্যে হয়।

আসলে, আমরা ধ্রুবক এবং অন্যান্য ছোট পদ বাদ দেই। বড়-Θ ব্যবহার করার আরেকটি সুবিধা হল, সময়ের একক নিয়ে চিন্তা করতে হয় না। উদাহরণস্বরূপ, ধরি একটি চলার সময় হল

6 n^{2} + 100 n + 300

মাইক্রোসেকেন্ড। অথবা এটি মিলিসেকেন্ডও হতে পারে। বড়-Θ চিহ্ন ব্যবহার করলে এটি বলার দরকার নেই। সহগ 6 এবং ছোট পদ

100 n + 300

বাদ দিয়ে বলা যায় যে, চলার সময় হল

Θ (n^{2})

।

বড়-Θ চিহ্ন ব্যবহারের সময়, আমরা বোঝাই যে চলার সময়ে অ্যাসিম্পটোটিক সীমানার মধ্যে আছে। "অ্যাসিম্পটোটিকালি" কারণ এটি শুধুমাত্র বড়

n

মানের উপর নির্ভরশীল। "সীমানার মধ্যে" কারণ আমরা চলার সময়কে ধ্রুবকের মাঝামাঝি পর্যায়ে খুঁজে পেয়েছি।

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

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

প্রবেশ কর

সাজানো আছেঃ

কোন আলাপচারিতা নেই।

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