সাধারণ জটিলতা ক্লাস — O(1) থেকে O(2ⁿ)
এই পাঠে যা শিখবেন
- সাধারণ জটিলতা ক্লাসগুলোর সম্পূর্ণ, ক্রমানুসারে তালিকা — প্রতিটির একটি বাস্তব অ্যালগরিদম উদাহরণসহ
- n=৫, ১০, ১৫, ২০-এ n², 2ⁿ, n! -এর প্রকৃত সাংখ্যিক মান গণনা করে ব্যবধান চোখে দেখা
- কেন এই ক্লাসিফিকেশন "ক্রম" ধরনের — একটি ক্লাস সবসময় পরের ক্লাসের চেয়ে ধীর, n যথেষ্ট বড় হলে
- Python কোডে n=২০ পর্যন্ত এই তুলনা লাইভ গণনা করে দেখা
১ · জটিলতা ক্লাসের সম্পূর্ণ ক্রম
L37-এ আমরা দেখেছি Big-O একটি উপরের সীমা (upper bound) বর্ণনা করে, এবং L38-এ Big-Θ একটি টাইট (tight) সীমা দেয়। বাস্তবে অ্যালগরিদমের বিশ্লেষণ করার সময় আমরা প্রায়ই একটি নির্দিষ্ট গ্রোথ রেটের বদলে কয়েকটি সুপরিচিত "ক্লাসের" ভাষায় কথা বলি — নিচে দ্রুততম থেকে ধীরতম ক্রমে সেগুলো দেওয়া হলো।
ইনপুট সাইজ যাই হোক, একই সংখ্যক ধাপ। উদাহরণ: array-এর ইনডেক্স দিয়ে সরাসরি একটি এলিমেন্ট অ্যাক্সেস করা।
প্রতি ধাপে সমস্যার আকার অর্ধেক হয়ে যায়। উদাহরণ: binary search (L36-এ দেখা)।
প্রতিটি এলিমেন্ট একবার করে দেখতে হয়। উদাহরণ: linear search, একটি array-এর সবচেয়ে বড় মান খোঁজা।
n-বার একটি log n খরচের কাজ। উদাহরণ: merge sort, heap sort (efficient sorting-এর সীমা)।
প্রতিটি এলিমেন্টের সাথে প্রতিটি এলিমেন্ট তুলনা। উদাহরণ: bubble sort, একটি array-এর সব জোড়া চেক করা (nested loop)।
তিনটি nested loop। উদাহরণ: দুটি n×n ম্যাট্রিক্সের naive (সরল) গুণন।
প্রতিটি এলিমেন্টের জন্য দুটি সিদ্ধান্ত (নাও/নাও-না)। উদাহরণ: নেইভ (স্মরণ ছাড়া) রিকার্সিভ ফিবোনাচি, একটি সেটের সব subset তৈরি করা।
সব সম্ভাব্য ক্রমবিন্যাস। উদাহরণ: brute-force Traveling Salesman (সব রুট চেষ্টা করা — L44-এ ফিরে আসবে)।
এই ক্রমটি সবসময়ের জন্য সত্য, n যথেষ্ট বড় হলে — অর্থাৎ একটি O(n²) অ্যালগরিদম সবসময়, একটি নির্দিষ্ট বিন্দুর পর, যেকোনো O(n³) অ্যালগরিদমের চেয়ে দ্রুত চলবে। এই ক্রমটাই এখন থেকে আমাদের "কোনটা ভালো" বলার ভাষা।
২ · n=২০-এ বাস্তব সংখ্যায় ব্যবধান
এই ক্লাসগুলো বিমূর্ত মনে হতে পারে, কিন্তু n-এর মান বসালেই ব্যবধান ভয়ংকরভাবে স্পষ্ট হয়ে যায়। নিচের টেবিলে n = ৫, ১০, ১৫, ২০-এর জন্য $n^2$, $2^n$, ও $n!$-এর প্রকৃত মান দেখানো হলো:
| n | n² | 2ⁿ | n! |
|---|---|---|---|
| ৫ | 25 | 32 | 120 |
| ১০ | 100 | 1,024 | 3,628,800 |
| ১৫ | 225 | 32,768 | 1,307,674,368,000 |
| ২০ | 400 | 1,048,576 | 2,432,902,008,176,640,000 |
n=২০-তে $n^2=400$ — একটি ছোট সংখ্যা। $2^n \approx 10.5$ লক্ষ — এখনো একটি আধুনিক কম্পিউটারের জন্য মুহূর্তের ব্যাপার। কিন্তু $n! \approx 2.43 \times 10^{18}$ — এটি প্রায় ২৪৩ কোটি কোটি! একটি সাধারণ কম্পিউটার প্রতি সেকেন্ডে কোটি কোটি অপারেশন করতে পারলেও, এই সংখ্যক ধাপ শেষ করতে বছরের পর বছর লেগে যাবে — শুধুমাত্র n=২০-এর জন্য।
import math
print(f"{'n':>4} | {'n^2':>10} | {'2^n':>15} | {'n!':>25}")
for n in [5, 10, 15, 20]:
print(f"{n:>4} | {n**2:>10,} | {2**n:>15,} | {math.factorial(n):>25,}")ভাবনার প্রশ্ন
প্রতিটি প্রশ্ন নিজে কিছুক্ষণ ভাবুন — তারপর "→ উত্তর" চাপুন।
প্র ০১ O(n log n) কেন ঠিক O(n) ও O(n²)-এর মাঝামাঝি বসে — এটি এই দুটোর "গড়" নয় তো?
না, এটি গাণিতিক গড় নয় — এটি একটি গ্রোথ রেট যা $n$-এর সরল গুণিতক (linear factor) এবং $\log n$-এর গুণফল। merge sort-এ (L31/L41-এ দেখা $T(n)=2T(n/2)+n$) প্রতিটি স্তরে $O(n)$ কাজ হয়, এবং ঠিক $\log n$টি স্তর থাকে (কারণ প্রতি স্তরে সমস্যা অর্ধেক হয়) — তাই মোট কাজ $n \cdot \log n$। যেহেতু $\log n$ সবসময় $n$-এর চেয়ে অনেক ধীরে বাড়ে, $O(n\log n)$ প্রায় $O(n)$-এর কাছাকাছি থাকে, $O(n^2)$-এর চেয়ে অনেক দ্রুত।
প্র ০২ একটি অ্যালগরিদম যদি O(n²) হয়, তাহলে কি এটি টেকনিক্যালি O(n³)-ও বলা যায়?
হ্যাঁ — L37-এ দেখা Big-O-এর সংজ্ঞা মনে করুন: এটি শুধু একটি উপরের সীমা। যদি $f(n)=O(n^2)$ হয়, তাহলে অবশ্যই $f(n)=O(n^3)$-ও (এবং $O(n^{100})$-ও) — কারণ $n^2 \le n^3$ যেকোনো $n\ge1$-এর জন্য। তবে ব্যবহারিকভাবে আমরা সবসময় সবচেয়ে টাইট ক্লাসটি উল্লেখ করি — একটি O(n²) অ্যালগরিদমকে "O(n³)" বলা টেকনিক্যালি সঠিক কিন্তু বিভ্রান্তিকর ও অনুপযোগী তথ্য।
প্র ০৩ O(2ⁿ) বা O(n!) জটিলতার অ্যালগরিদম কি কখনো ব্যবহারযোগ্য — নাকি এগুলো সবসময় এড়িয়ে চলা উচিত?
n খুব ছোট হলে (যেমন n≤১০-১৫) এই অ্যালগরিদমগুলো সম্পূর্ণ ব্যবহারযোগ্য এবং প্রায়ই দ্রুততম বাস্তব সমাধান — কারণ এদের কনস্ট্যান্ট ফ্যাক্টর প্রায়ই খুব ছোট এবং কোড লেখা সহজ। সমস্যা হয় শুধু যখন n বড় হতে শুরু করে — তখনই এই ক্লাসগুলো ব্যবহারিকভাবে অসম্ভব হয়ে যায় (L42-এ P বনাম NP আলোচনায় এই সীমারেখাটাই কেন্দ্রীয় বিষয়)।
অনুশীলন
-
গণনা করুন: উপরের কোড সেলে তালিকায় n=25 যোগ করুন এবং Run চাপুন। n² ও 2ⁿ-এর তুলনায় n! কতটা দ্রুত আরও বেড়ে যায় লক্ষ করুন।
n=25-এ n²=625, 2ⁿ=33,554,432, কিন্তু n!≈1.55×10²⁵ — এখন n! ইতিমধ্যে 2ⁿ-এর চেয়ে প্রায় ৫০ কোটি গুণ বড়! ব্যবধান n বাড়ার সাথে সাথে আরও দ্রুত বাড়তে থাকে — এটাই "সুপার-এক্সপোনেনশিয়াল" গ্রোথের বৈশিষ্ট্য।
-
যাচাই করুন: কোড সেলে একটি O(n³) কলাম যোগ করুন (n**3) এবং n=5,10,15,20-এর জন্য এর মান n²-এর সাথে তুলনা করুন।
n=20-এ n³=8,000, যেখানে n²=400 — অর্থাৎ n³, n²-এর চেয়ে ২০ গুণ বড় (ঠিক n-এর সমান গুণিতকে, কারণ $n^3 = n \cdot n^2$)। এটি O(2ⁿ) বা O(n!)-এর তুলনায় অনেক শান্ত বৃদ্ধি — বহুপদী (polynomial) ক্লাসগুলো একে অপরের থেকে "গুণিতক হারে" পার্থক্য করে, এক্সপোনেনশিয়াল/ফ্যাক্টোরিয়াল ক্লাস "ধাপ পরিবর্তনের হারে"।
আরও পড়ুন · ABCL TECH-এ আপনার পরবর্তী পদক্ষেপ
- কোর্সের সম্পূর্ণ সিলেবাস দেখুন ৪৪টি পাঠ পরবর্তী পাঠ — সেরা/গড়/খারাপ কেস বিশ্লেষণ — এই ক্লাসগুলোকে আরও গভীরভাবে ব্যবহার করে।
- পরবর্তী পাঠ L40 সেরা, গড় ও সবচেয়ে খারাপ কেস বিশ্লেষণ — একটি অ্যালগরিদম বিভিন্ন ইনপুটে কেমন আচরণ করে।
- Data Structures & Algorithms কোর্স সঙ্গী কোর্স এই ক্লাসগুলোর বাস্তব বাস্তবায়ন — merge sort, বাইনারি সার্চ ও আরও অনেক কিছু — দেখতে DSA কোর্সটিও দেখুন।