Big-O বর্ণনা করে যে একটি অ্যালগরিদমের চলার সময় বা মেমরি কীভাবে ইনপুট সাইজ n বৃদ্ধির সাথে বৃদ্ধি পায়। এটি সর্বনিম্ন অ্যাসিম্পটোটিক আচরণ ক্যাপচার করে, ধ্রুবক এবং নিম্ন-অর্ডার পদগুলি উপেক্ষা করে।
আমরা বৃদ্ধির হার সম্পর্কে যত্নশীল, সঠিক ধাপ সংখ্যা নয়। O(2n + 5) সহজভাবে O(n) কারণ n বড় হওয়ার সাথে সাথে, ধ্রুবক এবং ছোট পদগুলি আর গুরুত্বপূর্ণ থাকে না।
| Big-O | নাম | উদাহরণ |
|---|
| O(1) | ধ্রুবক | অ্যারে ইনডেক্স লুকআপ |
| O(log n) | লগারিদমিক | বাইনারি সার্চ |
| O(n) | রৈখিক | একটি তালিকা স্ক্যান করা |
| O(n log n) | লিনিয়ারিদমিক | মার্জ সর্ট |
| O(n²) | দ্বিঘাত | নেস্টেড লুপ |
| O(2ⁿ) | সূচকীয় | নিষ্কাশন সাবসেট |
def has_duplicate(nums):
for i in range(len(nums)): # outer loop: n
for j in range(i + 1, len(nums)): # inner loop: n
if nums[i] == nums[j]:
return True
return False
# nested loops -> O(n^2) time, O(1) space
Big-O ধ্রুবক লুকিয়ে রাখে: একটি বিশাল ধ্রুবক সহ O(n) অ্যালগরিদম ছোট ইনপুটে O(n log n) হারতে পারে। এছাড়াও স্থান জটিলতা ট্র্যাক করুন, শুধুমাত্র সময় নয়।
Big-O আপনাকে তাদের চালনা করতে বা হার্ডওয়্যার সম্পর্কে চিন্তা করতে ছাড়াই অ্যালগরিদম তুলনা করতে দেয়।
যখন ইনপুট শত থেকে মিলিয়নে বৃদ্ধি পায় তখন এটি পূর্বাভাস দেয় কোন সমাধানগুলি টিকে থাকে — একটি স্কেলযোগ্য বৈশিষ্ট্য এবং একটি যা সময়সীমা অতিক্রম করে তার মধ্যে পার্থক্য।
এটি এমন শব্দভান্ডার যা প্রতিটি ইঞ্জিনিয়ার কর্মক্ষমতা সম্পর্কে যুক্তি করতে ব্যবহার করে।