অ্যালগরিদম বিশ্লেষণ কেন জরুরি
এই পাঠে যা শিখবেন
- M8 মডিউল জুড়ে (L36-L43) কী কী কভার হবে তার একটি সংক্ষিপ্ত মানচিত্র
- কেন "সঠিক" এবং "দ্রুত" দুটি স্বাধীন মাপকাঠি
- linear search ও binary search-এর মধ্যে একটি নাটকীয় সংখ্যাগত তুলনা
- কেন এক্সাক্ট রানটাইমের বদলে growth rate পরিমাপ করাই সঠিক পদ্ধতি
১ · সঠিকতা ও দক্ষতা — দুটি আলাদা প্রশ্ন
একটি অ্যালগরিদম "সঠিক" মানে এটি সব বৈধ ইনপুটে সঠিক আউটপুট দেয়। কিন্তু দুটি সমান সঠিক অ্যালগরিদম ইনপুট আকার বাড়ার সাথে সাথে সম্পূর্ণ ভিন্ন গতিতে চলতে পারে। অ্যালগরিদম বিশ্লেষণ (Algorithm Analysis)Algorithm Analysisএকটি অ্যালগরিদম ইনপুট আকার বাড়ার সাথে সাথে কতটা দ্রুত/ধীরে চলে তা গাণিতিকভাবে পরিমাপ করার পদ্ধতি — সঠিকতা যাচাই থেকে সম্পূর্ণ আলাদা একটি প্রশ্ন। এই দ্বিতীয় প্রশ্নটির উত্তর দেয় — "কতটা দ্রুত?"
২ · একটি নাটকীয় উদাহরণ — Linear Search বনাম Binary Search
ধরুন একটি সর্টেড (sorted) অ্যারেতে ১০ লক্ষ (1,000,000) উপাদান আছে, এবং আমরা একটি নির্দিষ্ট মান খুঁজছি।
একটি একটি করে প্রতিটি উপাদান পরীক্ষা করে — সবচেয়ে খারাপ ক্ষেত্রে (মান শেষে বা অনুপস্থিত) সর্বোচ্চ ১০ লক্ষ তুলনা লাগতে পারে।
প্রতি ধাপে অনুসন্ধান-এলাকা অর্ধেক করে ফেলে — সর্বোচ্চ মাত্র $\log_2(1{,}000{,}000) \approx 19.9$, অর্থাৎ ~২০ তুলনা লাগে।
উভয় অ্যালগরিদমই সঠিক — দুটোই সঠিক উত্তর দেবে (যদি সাজানো থাকে)। কিন্তু ১০ লক্ষ ধাপ বনাম ২০ ধাপ — এটি প্রায় ৫০,০০০ গুণ পার্থক্য! ইনপুট আরও বড় হলে (যেমন ১ বিলিয়ন), linear search-এর ধাপ সরাসরি বাড়ে, কিন্তু binary search-এর ধাপ মাত্র কয়েকটি বাড়ে ($\log_2(10^9) \approx 30$)। এই পার্থক্যই "growth rate" কেন গুরুত্বপূর্ণ তার সবচেয়ে ভালো প্রমাণ।
৩ · কেন growth rate মাপি, সেকেন্ড নয়
একটি অ্যালগরিদমের এক্সাক্ট রানটাইম (সেকেন্ডে) নির্ভর করে প্রসেসরের গতি, প্রোগ্রামিং ভাষা, কম্পাইলার অপটিমাইজেশন, এমনকি সেদিনের সিস্টেম লোডের উপর — এগুলো হার্ডওয়্যার/পরিবেশ-নির্ভর, অ্যালগরিদমের নিজস্ব বৈশিষ্ট্য নয়। কিন্তু ইনপুট আকার $n \to \infty$ হওয়ার সাথে সাথে ধাপের সংখ্যা কীভাবে বাড়ে (growth rate) — এটি সম্পূর্ণভাবে অ্যালগরিদমের নিজস্ব, গাণিতিক, হার্ডওয়্যার-স্বাধীন একটি বৈশিষ্ট্য। এই কারণেই L37-L38-এ আমরা সেকেন্ড নয়, Big-O/Ω/Θ নোটেশন দিয়ে growth rate পরিমাপ করা শিখব।
৪ · M6-এর সাথে সেতুবন্ধন
M6-এ (L29-L32) আমরা রিকারেন্স রিলেশন সমাধান করা শিখেছি — যেমন $T(n) = T(n-1) + 1$ বা $T(n) = 2T(n/2) + n$। এই পুরো গণিতটাই ছিল, বাস্তবে, একটি recursive অ্যালগরিদমের ধাপ-সংখ্যা গণনা করার প্রস্তুতি। L41-এ আমরা সরাসরি দেখব কীভাবে merge sort, binary search এবং naive recursive Fibonacci-র রানটাইম ঠিক M6-এর টেকনিক (characteristic equation, Master Theorem) দিয়ে বের করা যায়।
def linear_search(lst, target):
comparisons = 0
for x in lst:
comparisons += 1
if x == target:
return comparisons
return comparisons
def binary_search(lst, target):
lo, hi = 0, len(lst) - 1
comparisons = 0
while lo <= hi:
comparisons += 1
mid = (lo + hi) // 2
if lst[mid] == target:
return comparisons
elif lst[mid] < target:
lo = mid + 1
else:
hi = mid - 1
return comparisons
n = 1000
sorted_list = list(range(n))
absent_target = -1 # লিস্টে নেই -- worst case (সবচেয়ে খারাপ ক্ষেত্র)
print("লিনিয়ার সার্চে লাগা তুলনা:", linear_search(sorted_list, absent_target))
print("বাইনারি সার্চে লাগা তুলনা:", binary_search(sorted_list, absent_target))এই মডিউলের (M8) মূল বার্তা: দুটি সঠিক অ্যালগরিদমের মধ্যে পার্থক্য শুধু "স্বাদের" ব্যাপার নয় — এটি বাস্তব, গণনাযোগ্য এবং কখনো কখনো ব্যবহারযোগ্যতা বনাম অব্যবহারযোগ্যতার পার্থক্য তৈরি করে। L37 থেকে আমরা এই "কতটা দ্রুত" প্রশ্নের উত্তর দেওয়ার আনুষ্ঠানিক গাণিতিক ভাষা (Big-O/Ω/Θ) শিখব।
ভাবনার প্রশ্ন
প্রতিটি প্রশ্ন নিজে কিছুক্ষণ ভাবুন — তারপর "→ উত্তর" চাপুন।
প্র ০১ যদি একটি সুপার-দ্রুত কম্পিউটার (বর্তমানের চেয়ে ১০০০ গুণ দ্রুত) থাকত, তাহলে কি linear search বনাম binary search-এর growth rate তুলনা করার প্রয়োজন থাকত?
হ্যাঁ, তবুও প্রয়োজন থাকত। একটি ১০০০ গুণ দ্রুত কম্পিউটার প্রতিটি তুলনাকে ১০০০ গুণ দ্রুত করে দেবে — কিন্তু এটি linear search-এর ধাপ সংখ্যা কমাবে না, শুধু প্রতিটি ধাপ দ্রুততর করবে। ইনপুট আকার যথেষ্ট বড় হলে (যেমন ১ ট্রিলিয়ন উপাদান), linear search-এর ধাপ সংখ্যা এখনো লিনিয়ারলি বাড়বে, আর binary search-এর ধাপ সংখ্যা এখনো লগারিদমিকভাবে — শুধু ধ্রুবক ফ্যাক্টর (constant factor) পরিবর্তিত হবে, growth rate-এর গুণগত পার্থক্য অপরিবর্তিত থাকবে।
এটাই মূল অন্তর্দৃষ্টি: হার্ডওয়্যার উন্নতি একটি ধ্রুবক গুণক (constant factor) উন্নতি দেয়, কিন্তু একটি খারাপ growth rate-এর অ্যালগরিদমকে ভালো growth rate-এর অ্যালগরিদমে পরিণত করতে পারে না। যথেষ্ট বড় ইনপুটে, অ্যালগরিদমের গুণগত পার্থক্যই জিতবে, হার্ডওয়্যারের ধ্রুবক-ফ্যাক্টর সুবিধা নয়।
প্র ০২ Binary search কেন শুধু সর্টেড (sorted) অ্যারেতে কাজ করে, unsorted অ্যারেতে নয়?
Binary search-এর মূল কৌশল হলো মাঝের উপাদানের সাথে টার্গেট তুলনা করে সিদ্ধান্ত নেওয়া যে টার্গেট বাম অর্ধেকে নাকি ডান অর্ধেকে থাকতে পারে — এবং এই সিদ্ধান্ত সঠিক হওয়ার জন্য অ্যারে সাজানো (sorted) থাকা আবশ্যক। যদি অ্যারে সাজানো না থাকে, মাঝের উপাদানের চেয়ে বড় বা ছোট হওয়ার অর্থ কিছুই বলে না — টার্গেট যেকোনো অর্ধেকে থাকতে পারে, তাই search space অর্ধেক করে ফেলা অসম্ভব।
এখানেই একটি গুরুত্বপূর্ণ trade-off আছে: unsorted ডেটা সাজাতে নিজেই সময় লাগে (সাধারণত $\Theta(n \log n)$, যা M8-এর পরের পাঠগুলোয় দেখব)। তাই যদি শুধু একবার সার্চ করতে হয়, সাজানো + binary search করা linear search-এর চেয়ে ধীর হতে পারে — কিন্তু বারবার সার্চ করলে একবার সাজিয়ে নেওয়ার খরচ পুষিয়ে যায়।
প্র ০৩ এই পাঠ বলছে M8 জুড়ে "growth rate" মাপা হবে সেকেন্ড নয়। কিন্তু বাস্তব সফটওয়্যার ইঞ্জিনিয়ারিং-এ তো সেকেন্ডই আসল মেট্রিক — তাহলে growth rate কি শুধু একটি একাডেমিক ধারণা?
না — growth rate এবং এক্সাক্ট সেকেন্ড দুটোই গুরুত্বপূর্ণ, তবে ভিন্ন পরিস্থিতিতে। Growth rate আপনাকে বলে দেয় ইনপুট আকার বাড়লে অ্যালগরিদম কেমন আচরণ করবে — যা একটি এক্সাক্ট বেঞ্চমার্ক (যা নির্দিষ্ট হার্ডওয়্যার ও নির্দিষ্ট ইনপুট আকারে চালানো হয়) কখনো নিশ্চিতভাবে বলতে পারে না।
বাস্তবে ভালো ইঞ্জিনিয়াররা দুটোই ব্যবহার করেন: প্রথমে growth rate দিয়ে বুঝে নেন কোন অ্যালগরিদম বড় স্কেলে ব্যবহারযোগ্য থাকবে (যেমন $O(n^2)$ বনাম $O(n \log n)$), তারপর প্রকৃত হার্ডওয়্যারে বেঞ্চমার্ক করে দেখেন ছোট/মাঝারি ইনপুটে কোনটি বাস্তবে দ্রুত (L43-এ এই দুই পদ্ধতির মিলন দেখব)। শুধু একটি ব্যবহার করে সিদ্ধান্ত নেওয়া বিপজ্জনক — theory ও measurement দুটোই দরকার।
অনুশীলন
-
হিসাব করুন: একটি সর্টেড অ্যারেতে ১ বিলিয়ন (10^9) উপাদান থাকলে binary search-এর সর্বোচ্চ ধাপ সংখ্যা কত হবে ($\log_2(10^9)$ হিসাব করুন)? Linear search-এর সাথে তুলনা করুন।
$\log_2(10^9) \approx 29.9$, তাই binary search-এর সর্বোচ্চ ধাপ প্রয়োজন প্রায় ৩০। Linear search-এর সর্বোচ্চ ধাপ প্রয়োজন ১ বিলিয়ন। পার্থক্যটি এখন প্রায় ৩ কোটি গুণ — ১০ লক্ষ উপাদানের তুলনায় (৫০ হাজার গুণ পার্থক্য) এই পার্থক্য আরও নাটকীয়ভাবে বেড়েছে, যা দেখায় ইনপুট আকার বাড়ার সাথে সাথে growth rate-এর পার্থক্য কেন আরও গুরুত্বপূর্ণ হয়ে ওঠে।
-
কোড পরীক্ষা করুন: উপরের কোড সেলে
n = 1000-এর বদলেn = 100000বসিয়ে চালান — linear ও binary search-এর তুলনা সংখ্যা কেমন বদলায় লক্ষ করুন।n = 100000-এ linear search ১,০০,০০০ তুলনা নেবে (n-এর সমান, লিনিয়ার গ্রোথ), কিন্তু binary search মাত্র ১৭টি তুলনা নেবে ($\log_2(100000) \approx 16.6$, রাউন্ড আপ করে ১৭)। লক্ষ করুন n ১০০ গুণ বাড়লেও binary search-এর ধাপ মাত্র কয়েকটি বেড়েছে — এটিই লগারিদমিক growth-এর বৈশিষ্ট্য।
আরও পড়ুন · ABCL TECH-এ আপনার পরবর্তী পদক্ষেপ
- কোর্সের সম্পূর্ণ সিলেবাস দেখুন ৪৪টি পাঠ পরবর্তী পাঠ — Big-O নোটেশনের আনুষ্ঠানিক সংজ্ঞা ও প্রথম worked প্রমাণ।
- Data Structures & Algorithms কোর্স সঙ্গী কোর্স linear ও binary search-এর প্রকৃত কোড বাস্তবায়ন ও আরও অ্যালগরিদম দেখতে DSA কোর্সটিও দেখুন।
- সব Courses দেখুন ABCL TECH C, C++, Python, Java, JavaScript, DSA, DBMS, HTML & CSS ও Discrete Mathematics — সব এক জায়গায়।