3. Big O Notation
টাইম কমপ্লেক্সিটি রিপ্রেজেন্ট করার জন্য Big O Notation ব্যবহৃত হয়। এটি মূলত গাণিতিকভাবে দেখায় যে ইনপুট সাইজ বাড়লে অ্যালগরিদমের পারফরম্যান্স কেমন হবে।
এখানে প্রচলিত বিভিন্ন Big O কমপ্লেক্সিটি নিয়ে বিস্তারিত আলোচনা করা হলো:
1. O(1) - Constant Time
অ্যালগরিদমের রান টাইম ইনপুট সাইজের ওপর নির্ভর করে না। ইনপুট ১টি হোক বা ১ কোটি, অপারেশন সংখ্যা সবসময় একই থাকে।
- উদাহরণ: অ্যারের ইনডেক্স থেকে ভ্যালু এক্সেস করা, হাশ ম্যাপ থেকে ভ্যালু রিট্রিভ করা।
2. O(log n) - Logarithmic Time
টাইম ইনপুট সাইজের লগারিদমিক হারে বাড়ে। সাধারণত প্রতি স্টেপে ইনপুট দুই ভাগে ভাগ হয়ে গেলে এই কমপ্লেক্সিটি আসে।
- উদাহরণ: Binary Search. এটি অত্যন্ত দক্ষ (Efficient) সার্চিং মেথড।
3. O(n) - Linear Time
টাইম ইনপুট সাইজের সাথে সরাসরি সমানুপাতিক হারে বাড়ে। ইনপুট দ্বিগুণ হলে সময়ও দ্বিগুণ হয়।
- উদাহরণ: একক লুপ ব্যবহার করে একটি অ্যারের সব আইটেম প্রিন্ট করা।
4. O(n log n) - Linearithmic Time
এটি O(n) থেকে কিছুটা ধীর কিন্তু O(n^2) থেকে অনেক দ্রুত। এটি মূলত ডিভাইড অ্যান্ড কনকুয়ার (Divide and Conquer) অ্যালগরিদমে দেখা যায়।
- উদাহরণ: Merge Sort, Quick Sort.
5. O(n^2) - Quadratic Time
টাইম ইনপুট সাইজের বর্গের সাথে বাড়ে। সাধারণত নেস্টেড লুপ (লুপের ভেতর লুপ) থাকলে এটি ঘটে।
- উদাহরণ: Bubble Sort, Selection Sort.
6. O(n^3) - Cubic Time
তিনটি নেস্টেড লুপ থাকলে এই কমপ্লেক্সিটি আসে। এটি বেশ ধীর গতির সমাধান।
- উদাহরণ: ম্যাট্রিক্স মাল্টিপ্লিকেশন (বেসিক অ্যাপ্রোচ)।
7. O(2^n) - Exponential Time
টাইম ইনপুট বাড়ার সাথে সাথে দ্বিগুণ হারে বাড়ে। এটি খুবই ধীর এবং বড় ইনপুটের জন্য অকেজো।
- উদাহরণ: রিকার্সিভলি ফিবোনাচ্চি (Recursive Fibonacci) বের করা।
8. O(n!) - Factorial Time
এটিই সবচেয়ে ধীরগতির কমপ্লেক্সিটি। ইনপুট ছোট হলেও অপারেশন সংখ্যা বিশাল হয়ে যায়।
- উদাহরণ: Traveling Salesman Problem (Brute Force).
Comparing Complexities (পারফরম্যান্স তুলনা)
নিচে কমপ্লেক্সিটিগুলোকে দ্রুত থেকে ধীর (Fastest to Slowest) ক্রমে সাজানো হলো:
O(1) < O(log n) < O(n) < O(n log n) < O(n^2) < O(n^3) < O(2^n) < O(n!)
IMPORTANT
বাস্তবজীবনে আমরা সবসময় চেষ্টা করি O(n log n) বা এর চেয়ে ভালো কমপ্লেক্সিটির সমাধান বের করতে।
TIP
কোড লেখার সময় চেষ্টা করবেন নেস্টেড লুপ এড়িয়ে চলতে, কারণ এটি আপনার কোডকে O(n^2) বা তারও খারাপ করতে পারে।