2. Algorithm Analysis Basics
একটি অ্যালগরিদম কতটা ভালো তা বিচার করার জন্য অ্যালগরিদম অ্যানালাইসিস করা হয়। এটি মূলত দুটি জিনিসের ওপর ভিত্তি করে করা হয়: Time Complexity এবং Space Complexity।
Time Complexity কি?
টাইম কমপ্লেক্সিটি হলো একটি অ্যালগরিদম রান হতে কতটুকু সময় নেয় তার একটি গাণিতিক প্রকাশ। এটি সেকেন্ড বা মিনিটে মাপা হয় না বরং ইনপুট সাইজ (n) বাড়লে অ্যালগরিদমের অপারেশন সংখ্যা কতটুকু বাড়ে, তা পরিমাপ করা হয়।
Space Complexity কি?
একটি অ্যালগরিদম চলতে গিয়ে মেমরিতে (RAM) অতিরিক্ত কতটুকু জায়গা দখল করে, তাকে স্পেস কমপ্লেক্সিটি বলে। ইনপুট সাইজ বাড়লে মেমরি ব্যবহারের হার কেমন হয়, তা-ই এখানে দেখা হয়।
Big O Notation
অ্যালগরিদমের পারফরম্যান্স প্রকাশ করার সবচেয়ে জনপ্রিয় মাধ্যম হলো Big O Notation। এটি মূলত অ্যালগরিদমের Worst Case বা সবচেয়ে খারাপ পরিস্থিতিতে পারফরম্যান্স কেমন হবে তা নির্দেশ করে।
| Notation | Name | Insight |
|---|---|---|
| O(1) | Constant Time | ইনপুট সাইজ যাই হোক, সময় একই লাগে। |
| O(log n) | Logarithmic Time | প্রতি স্টেপে সমস্যাটি অর্ধেক হয়ে যায় (Binary Search)। |
| O(n) | Linear Time | ইনপুট সাইজ বাড়লে সময় সমানুপাতিকভাবে বাড়ে। |
| O(n^2) | Quadratic Time | নেস্টেড লুপ থাকলে সাধারণত এটি ঘটে (Bubble Sort)। |
Cases in Algorithm Analysis
- Best Case (Omega - Ω): অ্যালগরিদমটি সবচেয়ে দ্রুত যখন কাজ শেষ করে।
- Average Case (Theta - Θ): গড়পড়তা কত সময় লাগে।
- Worst Case (Big O - O): সবচেয়ে বেশি কত সময় লাগতে পারে (এটিই সবচেয়ে বেশি গুরুত্বপূর্ণ)।
Why we analyze algorithms?
- Performance Measurement: কোনটি দ্রুত কাজ করবে তা বুঝতে।
- Efficiency: রিসোর্সের সঠিক ব্যবহার নিশ্চিত করতে।
- Reliability: বড় ডেটাসেটে কোডটি ফেইল করবে কিনা তা আগেভাগেই বুঝতে।
Trade-offs: Time vs Space
কখনো কখনো কোড দ্রুত চালানোর জন্য আমরা বেশি মেমরি ব্যবহার করি (যেমন: Caching, Memoization)। আবার মেমরি বাঁচাতে গেলে কোড কিছুটা ধীর হতে পারে। এই ভারসাম্য বজায় রাখাই হলো একজন দক্ষ ইঞ্জিনিয়ারের কাজ।
TIP
কোডিং ইন্টারভিউতে "Can we optimize this further?" মানে হলো আপনি কি এর Time বা Space Complexity কমাতে পারবেন?