অ্যালগরিদম কী এবং কেন ডিজাইন ও অ্যানালাইসিস গুরুত্বপূর্ণ
এই পাঠে যা শিখবেন
- অ্যালগরিদমের প্রকৃত সংজ্ঞা এবং এর পাঁচটি মৌলিক বৈশিষ্ট্য
- "অ্যালগরিদম ডিজাইন" ও "অ্যালগরিদম অ্যানালাইসিস" — এই দুটি শব্দের মধ্যে সুনির্দিষ্ট পার্থক্য
- এই কোর্স ঠিক কী কভার করে, কীভাবে সাজানো হয়েছে, এবং DSA/Theory of Computation কোর্স থেকে কীভাবে আলাদা
- একটি সত্যিকারের, চলমান ডেমো — একই সমস্যার দুটি সঠিক সমাধানের মধ্যে অ্যানালাইসিস কীভাবে সম্পূর্ণ ভিন্ন চিত্র তুলে ধরে
১ · অ্যালগরিদম কী
অ্যালগরিদমAlgorithmএকটি সুনির্দিষ্ট, সসীম সংখ্যক গণনামূলক ধাপের ক্রম যা যেকোনো বৈধ ইনপুট নিয়ে, সসীম সময়ের মধ্যে, সঠিক আউটপুট তৈরি করে। এই সংজ্ঞার প্রতিটি শব্দ গুরুত্বপূর্ণ। একটি প্রকৃত অ্যালগরিদমের পাঁচটি মৌলিক বৈশিষ্ট্য থাকতে হয়:
অ্যালগরিদমকে অবশ্যই সসীম সংখ্যক ধাপের পর থেমে যেতে হবে — অসীম লুপ অ্যালগরিদম নয়।
প্রতিটি ধাপ স্পষ্টভাবে, দ্ব্যর্থহীনভাবে সংজ্ঞায়িত হতে হবে — "মোটামুটি সাজান" নয়, বরং ঠিক কীভাবে তা বলা থাকতে হবে।
শূন্য বা তার বেশি নির্দিষ্ট ধরনের ইনপুট নেয়, একটি নির্দিষ্ট ডোমেইন থেকে।
এক বা একাধিক আউটপুট তৈরি করে, যা ইনপুটের সাথে একটি নির্দিষ্ট সম্পর্ক রাখে।
প্রতিটি ধাপ যথেষ্ট সরল হতে হবে যে তা নীতিগতভাবে হাতে-কলমে, সসীম সময়ে সম্পন্ন করা যায়।
লক্ষ্য করুন — এই সংজ্ঞাটি কোনো নির্দিষ্ট প্রোগ্রামিং ভাষার উপর নির্ভর করে না। সিউডোকোডে লেখা একটি অ্যালগরিদম Python, C++, বা হাতে কাগজে-কলমেও একইভাবে সঠিক থাকে — অ্যালগরিদম হলো ধারণা, বাস্তবায়ন (implementation) হলো সেই ধারণাকে একটি নির্দিষ্ট ভাষায় প্রকাশ করা। M1/L02-এ সিউডোকোড লেখার কনভেনশন নিয়ে বিস্তারিত আলোচনা হবে।
২ · ডিজাইন বনাম অ্যানালাইসিস — দুটি ভিন্ন দক্ষতা
এই কোর্সের নামেই দুটি শব্দ আছে — ডিজাইন এবং অ্যানালাইসিস — এবং এরা সত্যিই দুটি আলাদা, স্বতন্ত্র দক্ষতা:
একটি সমস্যা সমাধানের কৌশল/পদ্ধতি তৈরি করা — ডিভাইড অ্যান্ড কনকার, গ্রিডি, ডাইনামিক প্রোগ্রামিং ইত্যাদি প্যারাডাইম ব্যবহার করে (M4-M8-এ বিস্তারিত)। এটি অনেকটাই সৃজনশীল কাজ।
একটি ডিজাইন করা অ্যালগরিদম সবসময় সঠিক উত্তর দেয় তা প্রমাণ করা (M1/L03), এবং এটি ইনপুট বড় হলে কত দ্রুত বা ধীর হয় তা গাণিতিকভাবে নির্ণয় করা (M2-M3)। এটি রিগোরাস, প্রমাণ-ভিত্তিক কাজ।
Data Structures & Algorithms কোর্সে ইতিমধ্যে সর্টিং, সার্চিং, গ্রাফ ট্রাভার্সাল, গ্রিডি, DP, ব্যাকট্র্যাকিং-এর মতো অ্যালগরিদমগুলো কীভাবে কাজ করে এবং কীভাবে ইমপ্লিমেন্ট করতে হয় তা শেখানো হয়েছে। এই কোর্স সেই পরিচিতি ধরে নিয়ে সরাসরি গভীরে যায় — প্রতিটি অ্যালগরিদমের রিগোরাস সঠিকতা প্রমাণ এবং সম্পূর্ণ অ্যাসিম্পটোটিক ডেরিভেশন (রিকারেন্স সমাধান, মাস্টার থিওরেম), পাশাপাশি অ্যামর্টাইজড অ্যানালাইসিস ও ইনট্র্যাক্টেবিলিটির মুখোমুখি হলে কী করণীয় (অ্যাপ্রক্সিমেশন, র্যান্ডোমাইজেশন) — এমন বিষয় যা DSA কভার করে না। NP-কমপ্লিটনেসের আনুষ্ঠানিক প্রমাণ ও P vs NP তত্ত্ব ইতিমধ্যে Theory of Computation কোর্সে গভীরভাবে কভার করা হয়েছে — M11-এ আমরা শুধু একজন অ্যালগরিদম ডিজাইনারের দৃষ্টিকোণ থেকে এর ব্যবহারিক প্রভাব নিয়ে সংক্ষেপে আলোচনা করব।
৩ · একটি সত্যিকারের ডেমো — একই সমস্যা, দুটি সঠিক সমাধান
ধরা যাক সমস্যাটি হলো: একটি লিস্টে কোনো ডুপ্লিকেট এলিমেন্ট আছে কি না তা বের করা। নিচে দুটি সম্পূর্ণ সঠিক সমাধান আছে — একটি নেইভ (প্রতিটি জোড়া তুলনা করে), আরেকটি স্মার্ট (একটি হ্যাশ সেট ব্যবহার করে)। দুটোই সঠিক উত্তর দেয় (ডিজাইন ঠিক আছে) — কিন্তু ইনপুট বড় হলে কী ঘটে তা দেখতে আমরা প্রতিটি সমাধানের প্রকৃত তুলনার সংখ্যা গুনে দেখব (এটাই অ্যানালাইসিস)।
import random
def has_duplicate_naive(arr):
# নেইভ পদ্ধতি: প্রতিটি জোড়া (i, j) তুলনা করা
n = len(arr)
comparisons = 0
for i in range(n):
for j in range(i + 1, n):
comparisons += 1
if arr[i] == arr[j]:
return True, comparisons
return False, comparisons
def has_duplicate_smart(arr):
# স্মার্ট পদ্ধতি: একটি হ্যাশ সেটে দেখা এলিমেন্টগুলো রাখা
seen = set()
comparisons = 0
for x in arr:
comparisons += 1
if x in seen:
return True, comparisons
seen.add(x)
return False, comparisons
random.seed(42)
sizes = [10, 20, 40, 80]
results = []
for n in sizes:
arr = list(range(n)) # কোনো ডুপ্লিকেট নেই -- ওয়ার্স্ট কেস, পুরো অ্যারে স্ক্যান করতে হবে
random.shuffle(arr)
_, c_naive = has_duplicate_naive(arr)
_, c_smart = has_duplicate_smart(arr)
results.append((n, c_naive, c_smart))
print(f"{'n':>5} | {'নেইভ (তুলনা)':>15} | {'স্মার্ট (তুলনা)':>15}")
for n, c_naive, c_smart in results:
print(f"{n:>5} | {c_naive:>15} | {c_smart:>15}")
print("\nn দ্বিগুণ হলে তুলনার সংখ্যা কত গুণ বাড়ে:")
for i in range(1, len(results)):
n_prev, cn_prev, cs_prev = results[i - 1]
n_cur, cn_cur, cs_cur = results[i]
print(f"n={n_prev}->{n_cur}: নেইভ {cn_cur / cn_prev:.2f}x বেড়েছে, স্মার্ট {cs_cur / cs_prev:.2f}x বেড়েছে")n দ্বিগুণ হলে স্মার্ট সমাধানের তুলনার সংখ্যাও ঠিক
দ্বিগুণ হয় (২.০০x), কারণ এটি $O(n)$। কিন্তু নেইভ সমাধানের তুলনার সংখ্যা প্রায় চারগুণ
হয় (~৪.০৫–৪.২২x, ক্রমে $4$-এর কাছাকাছি), কারণ এটি $O(n^2)$ — এবং $n$ দ্বিগুণ হলে $n^2$ চারগুণ হওয়ারই কথা।
দুটো সমাধানই সমান সঠিক — কিন্তু $n = 10{,}000$ হলে নেইভ সমাধান স্মার্ট সমাধানের চেয়ে প্রায়
৫,০০০ গুণ বেশি কাজ করবে। এই "গ্রোথ রেট" প্রকৃতপক্ষে গণনা করে বের করাই অ্যানালাইসিসের কাজ — M2-এ আমরা এই
$O(n)$ ও $O(n^2)$ নোটেশন ঠিক কী বোঝায় তা আনুষ্ঠানিকভাবে সংজ্ঞায়িত করব।
একটি অ্যালগরিদম "কাজ করছে" জানাই যথেষ্ট নয় — একজন প্রকৃত অ্যালগরিদম ডিজাইনার জানেন এটি কেন সবসময় সঠিক (একটি প্রমাণ দিয়ে) এবং এটি ইনপুট বড় হলে ঠিক কতটা ধীর হবে (একটি গাণিতিক বিশ্লেষণ দিয়ে)। এই কোর্স ধাপে ধাপে — অ্যাসিম্পটোটিক নোটেশন থেকে রিকারেন্স, গ্রিডি/DP প্রমাণ, গ্রাফ অ্যালগরিদম, এবং ইনট্র্যাক্টেবিলিটির মুখোমুখি হলে কী করণীয় পর্যন্ত — এই রিগোরাস দক্ষতার সম্পূর্ণ টুলকিট শেখাবে।
ভাবনার প্রশ্ন
প্রতিটি প্রশ্ন নিজে কিছুক্ষণ ভাবুন — তারপর "→ উত্তর" চাপুন।
প্র ০১ দুটো সমাধানই "সঠিক" — তাহলে কেন শুধু নেইভ সমাধানটি ব্যবহার করা যথেষ্ট নয়?
"সঠিক" মানে শুধু এটাই যে এটি সব বৈধ ইনপুটে সঠিক আউটপুট দেয় — এটি বলে না যে এটি ব্যবহারযোগ্য গতিতে তা করে। ছোট ইনপুটে (যেমন উপরের ডেমোতে $n=10$) নেইভ সমাধান হয়তো চোখে পড়ার মতো ধীর নয়, কিন্তু বাস্তব-জীবনের ডেটাসেটে ($n$ লক্ষ বা কোটি) $O(n^2)$ সমাধান ব্যবহারিকভাবে অচল হয়ে যায় — যেখানে $O(n)$ সমাধান তখনও দ্রুত চলে। এই পার্থক্যটি ছোট ইনপুটে দেখা যায় না, কিন্তু অ্যানালাইসিস আগেভাগেই ভবিষ্যদ্বাণী করে দেয়।
প্র ০২
উপরের ডেমোতে প্রতিবার random.shuffle(arr) ব্যবহার করার আগে random.seed(42)
সেট করা হয়েছে কেন?
random.seed(42) ছাড়া প্রতিবার কোড চালালে shuffle ভিন্ন ভিন্ন ক্রম তৈরি করবে,
তাই আউটপুটের সংখ্যাগুলো (যদিও এই নির্দিষ্ট ডেমোতে ওয়ার্স্ট-কেস তুলনার সংখ্যা shuffle-নির্বিশেষে একই
থাকে, কারণ কোনো ডুপ্লিকেট না থাকায় উভয় ফাংশনই পুরো অ্যারে স্ক্যান করতে বাধ্য) প্রতিবার একই থাকবে তা
নিশ্চিত করা যায় না। একটি নির্দিষ্ট seed ব্যবহার করলে ফলাফল পুনরুৎপাদনযোগ্য (reproducible)
হয় — এই কোর্সের পরবর্তী পাঠগুলোতে (বিশেষ করে M12-এ র্যান্ডোমাইজড অ্যালগরিদম নিয়ে) এটি একটি গুরুত্বপূর্ণ
অভ্যাস হিসেবে বারবার ব্যবহৃত হবে।
প্র ০৩ যদি ইনপুট অ্যারেতে ডুপ্লিকেট এলিমেন্ট প্রথম দিকেই থাকত (যেমন প্রথম দুটো এলিমেন্ট একই), তাহলে কি উপরের তুলনার সংখ্যার প্যাটার্ন একই থাকত?
না — যদি ডুপ্লিকেট প্রথম দিকেই পাওয়া যেত, তাহলে উভয় ফাংশনই দ্রুত (মাত্র কয়েকটি তুলনার পরই)
return করে থেমে যেত, তুলনার সংখ্যাও অনেক কম হতো। এই ডেমোতে ইচ্ছাকৃতভাবে কোনো
ডুপ্লিকেট নেই এমন একটি অ্যারে ব্যবহার করা হয়েছে — এটিই এই সমস্যার ওয়ার্স্ট কেস
(উভয় ফাংশনকেই পুরো অ্যারে স্ক্যান করতে বাধ্য করে)। "গ্রোথ রেট" নিয়ে কথা বলার সময় সাধারণত ওয়ার্স্ট-কেস
ইনপুট নিয়েই আলোচনা করা হয় — M2/L08-এ বেস্ট/ওয়ার্স্ট/অ্যাভারেজ কেসের পার্থক্য বিস্তারিত আসবে।
অনুশীলন
-
চিন্তা করুন: উপরের ডেমোতে
sizesলিস্টে160যোগ করলে নেইভ ও স্মার্ট সমাধানের তুলনার সংখ্যা কত হবে বলে আপনার ধারণা? (হিন্ট: প্যাটার্নটি প্রয়োগ করুন।)স্মার্ট সমাধানে ঠিক
160টি তুলনা হবে (সবসময় $n$-এর সমান)। নেইভ সমাধানে $160 \times 159 / 2 = 12{,}720$টি তুলনা হবে — আগের মান3160-এর প্রায় ৪.০২৫ গুণ, যা প্যাটার্নের সাথে মিলে যায় (৪-এর আরও কাছাকাছি, কারণ $n$ যত বড় হয়, $\frac{n(n-1)/2}{(n/2)((n/2)-1)/2}$ অনুপাতটি ঠিক $4$-এর দিকে অগ্রসর হয়)। -
পরীক্ষা করুন: উপরের কোড সেলে
sizesলিস্টে160যোগ করে (অর্থাৎsizes = [10, 20, 40, 80, 160]) Run চেপে আপনার অনুমান যাচাই করুন।আউটপুটে দেখা যাবে
n=160-এ নেইভ সমাধানের তুলনার সংখ্যা12720এবং স্মার্ট সমাধানের160— ঠিক যেমনটা গণনা করা হয়েছিল। "n দ্বিগুণ হলে..." অংশে নতুন একটি লাইন যোগ হবে যা দেখাবে নেইভ অনুপাত আরও একটু $4$-এর কাছাকাছি পৌঁছেছে এবং স্মার্ট অনুপাত এখনও ঠিক2.00x।
আরও পড়ুন · ABCL TECH-এ আপনার পরবর্তী পদক্ষেপ
- কোর্সের সম্পূর্ণ সিলেবাস দেখুন ৫৭টি পাঠ অ্যাসিম্পটোটিক অ্যানালাইসিস, রিকারেন্স, ডিভাইড অ্যান্ড কনকার, গ্রিডি, DP, গ্রাফ অ্যালগরিদম, ব্যাকট্র্যাকিং, স্ট্রিং অ্যালগরিদম, অ্যামর্টাইজড অ্যানালাইসিস, NP-কমপ্লিটনেস ও অ্যাপ্রক্সিমেশন — বাকি পাঠগুলো শীঘ্রই যুক্ত হবে।
- Data Structures & Algorithms কোর্স সহোদর কোর্স অ্যালগরিদমগুলো কীভাবে কাজ করে ও ইমপ্লিমেন্ট করতে হয় তার ভিত্তি সেই কোর্সেই তৈরি হয়েছে — এই কোর্স সঠিকতা প্রমাণ ও অ্যানালাইসিসে গভীরে যায়।
- সব Courses দেখুন ABCL TECH C, C++, Python, Java, JavaScript, DSA, DBMS, Discrete Mathematics, System Design, Cybersecurity, Cloud Computing & DevOps, Computer Networks, Operating Systems, Computer Architecture, Programming Languages & Compiler Design, Software Engineering & Git, Theory of Computation, Engineering Economics, Full-Stack Web Frameworks, Mobile App Development, Ethics in Computing & AI Safety, Software Testing & Quality Assurance ও Design and Analysis of Algorithms — সব এক জায়গায়।