Big O Notation: A-Level CS இல் எதை எதிர்பார்க்கிறார்கள்

A-level கணினி அறிவியலுக்கான Big O notation இன் நடைமுறை விளக்கம், வேலை செய்த உதாரணங்கள் மற்றும் தேர்வு-சார்ந்த টips உடன்.

Big O notation ஆனது ஒவ்வொரு முக்கிய A-level கணினி அறிவியல் spec இலும் (AQA, OCR, Edexcel) தோன்றுகிறது மற்றும் இது பல மாணவர்களை குழப்புகிறது, கணிதம் கடினமாக இருப்பதால் அல்ல, ஆனால் அவர்கள் அதை உண்மையான குறிப்புடன் இணைக்கப்பட்டதை பார்க்கவே இல்லை. இது நீங்கள் தெரிந்து கொள்ள வேண்டியது மற்றும் பேசாமல் தேர்வு கேள்விக்கு பதிலளிப்பது பற்றிய நடைமுறை விளக்கம்.

Big O உண்மையில் என்ன அளவிடுகிறது

Big O ஒரு அல்காரிதத்தின் இயங்கும் நேரம் (அல்லது நினைவக பயன்பாடு) எவ்வாறு வளர்கிறது என்பதை விவரிக்கிறது, வழக்கமாக n என்று அழைக்கப்படும் உள்ளீடு அளவு பெரிதாகிறது. இது விநாடிகளில் ஒரு ஸ்டপ்வாட்চ அளவீட்டு அல்ல. இது வளர்ச்சி விகிதத்தை விவரிப்பதற்கான ஒரு வழி, இதனால் நீங்கள் வன்பொருளைச் சுயாதீனமாக அல்காரிதங்களை ஒப்பிடலாம்.

நீங்கள் O(n) எழுதும்போது, நீங்கள் சொல்கிறீர்கள்: நான் உள்ளீட்டை இரட்டிப்பாக்கினால், வேலை தோராயமாக இரட்டிப்பாகிறது. O(n²) என்பது உள்ளீட்டை இரட்டிப்பாக்கினால் வேலை தோராயமாக நான்கு மடங்கு ஆகிறது. அந்த உறவு என்பது தேர்வாளர்கள் உங்களிடம் அடையாளம் காண விரும்புவது, சரியான செயல்பாடு எண்ணிக்கை அல்ல.

மூடப்பட்ட பொதுவான அட்சரங்கள்

A-level க்கு, இவை மீண்டும் மீண்டும் தோன்றுகின்றன:

O(1) – நிலையான நேரம். ஒரு array உপাদানை இंडेक்স மூலம் அணுகுதல்: arr[5]. Array எவ்வளவு பெரியது என்பது தொடர்பில்லை.
O(log n) – மடக்கை. வரிசைப்படுத்தப்பட்ட பட்டியலில் இரண்ட தேடல். ஒவ்வொரு நிலையும் மீதமுள்ள தேடல் இடத்தை பாதியாக்குகிறது.
O(n) – linear. ஒரு பட்டியலின் மூலம் ஒரு வளையம், ஒரு linear தேடல் ஒவ்வொரு உருப்படியை ஒரு முறை சரிபார்க்கிறது.
O(n log n) – linearithmic. Merge sort மற்றும் quicksort (சராசரி வழக்கு) இங்கே நிற்கின்றன.
O(n²) – quadratic. அதே தரவு மீது nested வளையங்கள், இது சரியாக bubble sort, insertion sort, மற்றும் selection sort செய்கிறது.
O(2ⁿ) – exponential. memoisation இல்லாமல்天真 recursive Fibonacci. வேகமாக கெட்டுவிடுகிறது.

நீங்கள் pseudocode ஐ பார்த்து இவற்றுள் எந்தது என்பதை உடனடியாக சொல்லலாம், ஏனென்றால் அது பெரும்பாலும் சோதிக்கப்படுவது.

பொதுவான தன்மையுடன் குறிப்பை படிக்கிறது

ஒவ்வொரு முறையும் வேலை செய்யும் முறை: வளையங்களை எண்ணி அவை n உடன் எவ்வாறு தொடர்புடையவை என்பதை பார்க்கவும்.

# O(n) - ஒரு வளையம், ஒரு பாஸ்
for i in range(n):
    print(i)

# O(n^2) - nested வளையம், இரண்டும் n உடன் பிணைக்கப்பட்டுள்ளன
for i in range(n):
    for j in range(n):
        print(i, j)

# O(log n) - தேடல் இடம் ஒவ்வொரு 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 வளையம் இதில் உள் வளையத்தின் வரம்பு n மீது சார்ந்துள்ளது இன்னும் O(n²) ஆகும், விஷயம் சற்று வேறுபட்டாலும் (like for j in range(i) என்பது for j in range(n) என்பதற்கு பதிலாக — அது இன்னும் quadratic ஒட்டுமொத்தமாக, ஒரு நிலையான காரணி வேறுபாடு உடன்).

வளையங்களிலிருந்து எச்சரிக்கையாக இருங்கள் அவை n மீது சார்ந்துவிட்டாகிறது. ஒரு வளையம் உள்ளீடு அளவைச் சார்ந்து எப்போதும் 10 முறை இயங்குகிறது O(1) ஆகும், ஒரு வளையம் இருந்தாலும் முன்னிலை உள்ளது. தேர்வாளர்கள் இதை வகர விரும்புகிறார்கள்.

பொதுவான வரிசைப்படுத்தல் algorithms மற்றும் அவற்றின் Big O

இது ஒரு பிரியமான தேர்வு topic ஆகும் ஏனென்றால் இது இரண்டு specs உடன் இணைகிறது: algorithms மற்றும் பொதுவான தன்மையை வரிசைப்படுத்துகிறது.

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 (அதே சிக்கல் சிறந்த மற்றும் மோசமான வழக்கு) ஒரு கேள்வி பெரிய datasets க்கு bubble sort மீது அதை தேர்ந்தெடுக்க ஏன் கேட்டால் வெளிப்படையாக குறிப்பிட்ட மதிப்பு உள்ளது. Bubble sort இன் சிறந்த வழக்கு O(n) ஐ மாத்திரம் early-exit অপ்டிமைசேশன உடன் பொருந்த போது — எந்த swaps செய்தாலும் ஒரு பாஸ் மீது கூறுகிறது — அந்த விவரம் குறிப்பிட்டால் அதை கொண்டுவந்தால், சில தேர்வு வாரியம் அதை பொருத்த.

AI உதவியுடன் எழுதப்பட்டது, Michal Pilch (CISSP), Korra Studio ஆல் மறுஆய்வு செய்யப்பட்டு வெளியிடப்பட்டது.