Big O Notation: A-Level CS কী প্রত্যাশা করে

Big O notation প্রতিটি প্রধান A-level কম্পিউটার বিজ্ঞান স্পেসিফিকেশনে (AQA, OCR, Edexcel) দেখা যায় এবং এটি অনেক ছাত্রকে বিভ্রান্ত করে শুধুমাত্র এই কারণে যে গণিত কঠিন নয়, বরং তারা এটি কখনও প্রকৃত কোডের সাথে যুক্ত দেখে না। এটি একটি ব্যবহারিক বিবরণ যা আপনার জানা দরকার এবং কীভাবে পরীক্ষার প্রশ্নের উত্তর দিতে হয় তা জানা দরকার অপ্রয়োজনীয় কথা ছাড়াই।

Big O আসলে কী পরিমাপ করে

Big O বর্ণনা করে যে কীভাবে একটি অ্যালগরিদমের চালু হওয়ার সময় (বা মেমরি ব্যবহার) বৃদ্ধি পায় যখন ইনপুট সাইজ, সাধারণত n বলা হয়, বড় হয়। এটি সেকেন্ডে স্টপওয়াচ পরিমাপ নয়। এটি বৃদ্ধির হার বর্ণনা করার একটি উপায় যাতে আপনি হার্ডওয়্যার থেকে স্বাধীনভাবে অ্যালগরিদম তুলনা করতে পারেন।

যখন আপনি O(n) লেখেন, আপনি বলছেন: যদি আমি ইনপুট দ্বিগুণ করি, কাজ মোটামুটি দ্বিগুণ হয়। O(n²) মানে ইনপুট দ্বিগুণ করলে কাজ মোটামুটি চতুর্গুণ হয়। এই সম্পর্কই পরীক্ষকরা আপনাকে চিহ্নিত করতে চায়, সঠিক অপারেশনের সংখ্যা নয়।

যে জটিলতাগুলি আপনার জানা আবশ্যক

A-level-এর জন্য, এগুলি বারবার আসে:

• O(1) – constant time। Array উপাদান ইন্ডেক্স দ্বারা অ্যাক্সেস করা: arr[5]। Array কতো বড় তা কোনো গুরুত্ব রাখে না।
• O(log n) – logarithmic। একটি সাজানো তালিকায় binary search। প্রতিটি ধাপ অবশিষ্ট search space অর্ধেক করে।
• O(n) – linear। একটি তালিকার মাধ্যমে একটি একক loop, যেমন একটি linear search যা প্রতিটি আইটেম একবার চেক করে।
• O(n log n) – linearithmic। Merge sort এবং quicksort (average case) এখানে পড়ে।
• O(n²) – quadratic। একই ডেটার উপর nested loops, যা ঠিক যা bubble sort, insertion sort এবং selection sort করে।
• O(2ⁿ) – exponential। Memoisation ছাড়া naive recursive Fibonacci। দ্রুত খারাপ হয়।

আপনার pseudocode দেখে এর মধ্যে কোনটি তা সঙ্গে সঙ্গে বলতে পারা উচিত, কারণ এটি মূলত যা পরীক্ষা করা হয়।

জটিলতার জন্য কোড পড়া

যে পদ্ধতি সর্বদা কাজ করে: loops গণনা করুন এবং দেখুন তারা n-এর সাথে কীভাবে সম্পর্কিত।

# O(n) - একটি loop, একটি pass
for i in range(n):
    print(i)

# O(n^2) - nested loop, উভয়ই n-এর সাথে যুক্ত
for i in range(n):
    for j in range(n):
        print(i, j)

# O(log n) - search space প্রতিটি iteration-এ অর্ধেক হয়
low, high = 0, n - 1
while low <= high:
    mid = (low + high) // 2
    if target == arr[mid]:
        break
    elif target < arr[mid]:
        high = mid - 1
    else:
        low = mid + 1

একটি nested loop যেখানে inner loop-এর range n-এর উপর নির্ভর করে তা এখনও O(n²), এমনকি যদি এটি সামান্য ভিন্ন দেখায় (যেমন for j in range(i) for j in range(n) এর পরিবর্তে — এটি এখনও সামগ্রিকভাবে quadratic, শুধু একটি constant factor পার্থক্য সহ)।

Loops সম্পর্কে সাবধান যা n-এর উপর নির্ভর করে না। একটি loop যা ইনপুট সাইজ নির্বিশেষে সর্বদা 10 বার চলে তা O(1), যদিও একটি loop উপস্থিত আছে। পরীক্ষকরা এটি লুকিয়ে রাখতে পছন্দ করেন।

সাধারণ sorting অ্যালগরিদম এবং তাদের Big O

এটি একটি প্রিয় পরীক্ষার বিষয় কারণ এটি দুটি specs একত্রিত করে: sorting অ্যালগরিদম এবং জটিলতা।

Algorithm	Best case	Worst case
Bubble sort	O(n)	O(n²)
Insertion sort	O(n)	O(n²)
Merge sort	O(n log n)	O(n log n)
Binary search	O(1)	O(log n)
Linear search	O(1)	O(n)

Merge sort-এর consistency (best এবং worst case-এ একই জটিলতা) স্পষ্টভাবে উল্লেখ করার যোগ্য যদি একটি প্রশ্ন বড় ডেটাসেটের জন্য এটি bubble sort-এর উপর কেন বেছে নিতেন তা জিজ্ঞাসা করে। Bubble sort-এর best case O(n) শুধু একটি early-exit অপটিমাইজেশনের সাথে প্রযোজ্য যখন কোনো pass-এ সোয়াপ হয় না — এই বিবরণ উল্লেখ করুন যদি আপনি এটি নিয়ে আসেন, কারণ কিছু পরীক্ষা বোর্ড এটি আশা করে।

যেখানে ছাত্রছাত্রীরা নম্বর হারায়

সবচেয়ে বড়টি: লেখা