মূল বিষয়বস্তু
কম্পিউটার বিজ্ঞান
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 ( . The maximum number of times that the for-loop can run is , and this worst case occurs when the value being searched for is not present in the array.
array.length
) by Each time the for-loop iterates, it has to do several things:
- compare
guess
witharray.length
- compare
array[guess]
withtargetValue
- 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 times, then the time for all iterations is , where is the sum of the times for the computations in one loop iteration. Now, we cannot say here what the value of 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 , which is also a constant. Therefore, the total time for linear search in the worst case is .
guess
to 0) and possibly returning -1
at the end. Let's call the time for this overhead আমরা দেখেছি, ধ্রুবক এবং ছোট পদ চলার সময়ের বৃদ্ধির হার সম্পর্কে কোন কিছু নির্দেশ করে না। উল্লেখযোগ্য বিষয় হল, লিনিয়ার সার্চের ওরস্ট কেস চলার সময় অ্যারের আকার এর মত বৃদ্ধি পায়। এটির জন্য চিহ্ন ব্যবহার করা হয়। এটি হল গ্রিক অক্ষর "থেটা," এবং আমরা বলি " এর বড়-থেটা" অথবা শুধু " এর থেটা"।
চলার সময় হল , এটি বলতে মূলত বোঝানো হয় যে, যথেষ্ট বড় হলে, চলার সময় কমপক্ষে হবে এবং সর্বোচ্চ হবে যেখানে এবং হল ধ্রুবক। সম্পর্কে এভাবে চিন্তা করা যায়:
We are not restricted to just in big-Θ notation. We can use any function, such as , , or any other function of . Here's how to think of a running time that is for some function :
একবার যথেষ্ট বড় হলে, চলার সময় এবং এর মধ্যে হয়।
আসলে, আমরা ধ্রুবক এবং অন্যান্য ছোট পদ বাদ দেই। বড়-Θ ব্যবহার করার আরেকটি সুবিধা হল, সময়ের একক নিয়ে চিন্তা করতে হয় না। উদাহরণস্বরূপ, ধরি একটি চলার সময় হল মাইক্রোসেকেন্ড। অথবা এটি মিলিসেকেন্ডও হতে পারে। বড়-Θ চিহ্ন ব্যবহার করলে এটি বলার দরকার নেই। সহগ 6 এবং ছোট পদ বাদ দিয়ে বলা যায় যে, চলার সময় হল ।
বড়-Θ চিহ্ন ব্যবহারের সময়, আমরা বোঝাই যে চলার সময়ে অ্যাসিম্পটোটিক সীমানার মধ্যে আছে। "অ্যাসিম্পটোটিকালি" কারণ এটি শুধুমাত্র বড় মানের উপর নির্ভরশীল। "সীমানার মধ্যে" কারণ আমরা চলার সময়কে ধ্রুবকের মাঝামাঝি পর্যায়ে খুঁজে পেয়েছি।
এই বিষয়বস্তুটি Dartmouth Computer Science এর প্রফেসর Thomas Cormen এবং Devin Balkcom এর সহযোগিতায় এবং একই সাথে খান একাডেমির কম্পিউটিং শিক্ষাক্রম দলের একসাথে কাজ করার মাধ্যমে তৈরি করা হয়েছে। এই বিষয়বস্তু CC-BY-NC-SA দিয়ে লাইসেন্সকৃত।
আলোচনায় অংশ নিতে চাও?
কোন আলাপচারিতা নেই।