মূল বিষয়বস্তু
কম্পিউটার বিজ্ঞান
এ্যাসিম্প্টোটিক নোটেশান
এখন পর্যন্ত, আমরা প্রয়োজনীয় সর্বোচ্চ সংখ্যক অনুমিত সংখ্যার মাধ্যমে লিনিয়ার সার্চ এবং বাইনারি সার্চ বিশ্লেষণ করেছি। কিন্তু আমরা জানতে চাই এই অ্যালগোরিদমগুলো চলার জন্য কত সময় লাগবে। আমরা সময়ের বিষয়ে আগ্রহী, শুধুমাত্র অনুমানের উপর নয়। লিনিয়ার সার্চ এবং বাইনারি সার্চ চলার সময়কালের মধ্যে অনুমান এবং যাচাই করার সময়ও অন্তর্ভুক্ত থাকে, কিন্তু এই অ্যালগোরিদমে এটি ছাড়াও আরও অনেক বিষয় আছে।
একটি অ্যালগোরিদম চলার সময় নির্ভর করে কম্পিউটারের সেই অ্যালগোরিদমের কোড চালানোর সময়ের উপর—আর এটা সম্পূর্ণ কম্পিউটারের গতির উপর নির্ভরশীল, কারণ প্রোগ্রামিং ভাষা এবং কম্পাইলার যা প্রোগ্রামকে চলার জন্য কম্পউটারের ভাষায় বাইনারিতে অনুবাদ করে সেটি চলার সময়ের উপরই অ্যালগোরিদমের দ্রুততা নির্ভর করে। এছাড়াও অন্যান্য কারণও রয়েছে।
অ্যালগোরিদমের চলার সময় নিয়ে আরেকটু ভাবা যাক। আমরা উভয় ধারণার মধ্যে সমন্বয় করতে পারি প্রথমত, নির্ধারণ করতে হবে যে, ইনপুটের আকারের ভিত্তিতে অ্যালগোরিদমের কত সময় লাগবে। ধারণাটি সঠিক, তাই নয় কি? আমরা ইতোমধ্যেই দেখেছি লিনিয়ার সার্চ এবং বাইনারি সার্চের সর্বোচ্চ অনুমান সংখ্যা অ্যারে বৃদ্ধির সাথে সাথে বৃদ্ধি পায়। অথবা জিপিএস (GPS) সম্পর্কে চিন্তা কর। যদি এটি শুধুমাত্র হাইওয়ে রাস্তার সম্পর্কে জানে এবং সব ছোট রাস্তাগুলো সম্পর্কে না জানে, এটি তুলনামূলক কম সময়ে রাস্তা বের করতে পারবে, ঠিক নয় কি? আমরা অ্যালগোরিদমের সময়কালকে এটির ইনপুটের আকারের ফাংশন হিসেবে বিবেচনা করি।
দ্বিতীয় ধারণাটি হল ফাংশনটি কত দ্রুত ইনপুটের আকারের সাথে সাথে বৃদ্ধি পায়। আমরা এটিকে অ্যালগোরিদম চলার সময়ের বৃদ্ধির হার বলি। পরিচালনাধীন রাখার জন্য, আমরা ফাংশনকে সহজ করি যেন সবচেয়ে প্রয়োজনীয় অংশটি সংরক্ষিত থাকে এবং তুলনামূলক কম গুরুত্বপূর্ণ অংশটি সরিয়ে রাখা যায়। উদাহরণস্বরূপ, ধরা যাক একটি অ্যালগোরিদম, যার ইনপুটের আকার হল n, যা 6, n, squared, plus, 100, n, plus, 300 মেশিন ইন্সট্রাকশন নেয়। যখন n নির্দিষ্ট পরিমানে বড় হয় (এই ক্ষেত্রে 20 ), 6, n, squared পদটি অবশিষ্ট থাকে এবং অন্য পদ 100, n, plus, 300 হতে বড় হয়। এখানে একটি তালিকা দেওয়া আছে যা 0 থেকে 100 পর্যন্ত n এর জন্য 6, n, squared এবং 100, n, plus, 300 এর মান প্রদর্শন করে:
আমরা বলতে পারি যে, সহগ 6 এবং অবশিষ্ট পদ 100, n, plus, 300 বাদ দিলে এই অ্যালগোরিদম চলার সময় n, squared হিসেবে বৃদ্ধি পায়। আমরা কোন সহগ ব্যবহার করেছি সেটি কোন বিষয় নয়; যতক্ষণ পর্যন্ত সময়কাল হল a, n, squared, plus, b, n, plus, c, আর কিছু সংখ্যার জন্য a, is greater than, 0, b এবং c সবসময় n এর একটি মান থাকবে যার জন্য b, n, plus, c থেকে a, n, squared বড় হয় এবং এই পার্থক্য n এর সাথে বৃদ্ধির পেতে থাকে। উদাহরণস্বরূপ, এখানে একটি তালিকা আছে যা 0, point, 6, n, squared এবং 1000, n, plus, 3000 মান দেখায়, আমরা n, squared সহগের মান 10 গুণ হ্রাস করেছি এবং অন্য দুইটি ধ্রুবকের জন্য 10 গুণ মান বৃদ্ধি করেছিঃ
n এর যে মানের জন্য 1000, n, plus, 3000 থেকে 0, point, 6, n, squared বড় হয়, সেই মান বৃদ্ধি পেয়েছে এবং এটি কোন ধ্রুবকের উপর নির্ভরশীল নয়।
তুলনামূলক কম গুরুত্বপূর্ণ পদ এবং ধ্রুবক সহগগুলো বাদ দিয়ে, আমরা একটি অ্যালগোরিদমের গুরুত্বপূর্ণ অংশগুলোর দিকে লক্ষ্য করতে পারি, অ্যালগোরিদম চলার সময়—এটি বৃদ্ধির হার—যা বিস্তারিত বর্ণনায় না গিয়ে সহজভাবে বুঝতে সহায়তা করে। যখন আমরা ধ্রুবক সহগ এবং কম গুরুত্বপূর্ণ পদগুলোকে বাদ দেই, তখন আমরা ব্যবহার করি অ্যাসিম্পটোটিক নোটেশান। আমরা এটির তিনটি গঠন দেখবো: বড়-\Theta চিহ্ন, বড়-O চিহ্ন এবং বড়-\Omega চিহ্ন।
এই বিষয়বস্তুটি Dartmouth Computer Science এর প্রফেসর Thomas Cormen এবং Devin Balkcom এর সহযোগিতায় এবং একই সাথে খান একাডেমির কম্পিউটিং শিক্ষাক্রম দলের একসাথে কাজ করার মাধ্যমে তৈরি করা হয়েছে। এই বিষয়বস্তু CC-BY-NC-SA দিয়ে লাইসেন্সকৃত।
আলোচনায় অংশ নিতে চাও?
কোন আলাপচারিতা নেই।