ஒரு வழிமுறையைச் (algorithm) செயல்படுத்தும்போது, O(N), O(log N) போன்ற தொடர்களைக் கேள்விப்பட்டிருப்போம். இவற்றின் பொருளென்ன, அதன் முக்கியத்துவமென்ன என்பதைப்பற்றி இப்பதிவில் அறிந்துகொள்ள முயல்வோம்.
ஒரு வழிமுறையின் பேரளவாக்கத்தன்மை (scalability) இக்குறியீட்டால் அளவிடப்படுகிறது. வழிமுறைக்குக் கொடுக்கப்படும் உள்ளீட்டின் அளவு வேறுபடும்போது, அதன் வெளியீட்டிற்கு, எவ்வளவு அதிக உழைப்பு தேவைப்படுகிறது என்பதையே இக்குறியீடு உணர்த்துகிறது.
எடுத்துக்காட்டாக, ஒரு வேலையைச்செய்ய ஒரு வழிமுறையில், ஐந்து நிமிடங்கள் எடுக்கிறது என வைத்துக்கொள்வோம். அதன் உள்ளீட்டின் எண்ணிக்கையை இரட்டிப்பாக்கும்போது, நாம் கூடுதலாகச் செய்யவேண்டிய வேலையின் அளவென்ன? அதுவும் இரட்டிப்பாகிறதா? நூறுமடங்கு அதிகரிக்கிறதா? அல்லது ஓரிரு படிகள் மட்டும் அதிகரிக்கின்றதா? இக்கேள்விகளுக்கான விடை Big O குறியீட்டில் அடங்கியிருக்கிறது.
சில வழிமுறைகளின் பேரளவாக்கத்தை ஒரு வரைபடமாக்குவதாக வைத்துக்கொள்வோம். அதன் X அச்சாக, உள்ளீட்டின் எண்ணிக்கையையும், Y அச்சாக செய்யவேண்டிய வேலையையும் எடுத்துக்கொண்டால், பின்வரும் வரைபடத்தைப்போல அமையலாம்.
இவ்வரைபடங்களின் வடிவத்தைக்கொண்டு, அதன் வளர்ச்சி ஒழுங்கைப் (order of growth) பிரித்தறியலாம். வரைபடத்தின் கோணத்தைப்பற்றியோ, இடத்தைப்பற்றியோ கவலைப்படத்தேவையில்லை. அவற்றின் வடிவம் மட்டுமே முக்கியமானது. மேற்கண்ட படத்திலுள்ள ஒவ்வொரு வரைபடத்தைப்பற்றியும் எடுத்துக்காட்டுகளுடன் கீழே விரிவாகப்பார்க்கலாம்.
நான் ஒரு மாநாட்டை நடத்துகிறேன். அதில் பங்கேற்பவர்களை வரவேற்பதற்காக வெவ்வேறு வழிமுறைகளைப் பரிசீலிக்கிறேன். ஒவ்வொரு வழிமுறையாக அலசிப்பார்க்கலாம்.
கை குலுக்கல்:
மாநாட்டிற்கு வரும் ஒவ்வொருவரையும் நேரில் சந்தித்து கைகுலுக்கி வரவேற்கவேண்டுமென்று முடிவெடுக்கிறேன். இதை ஒரு வழிமுறையாக வைத்துக்கொண்டால், அதன் திறனை விளக்கும் வரைபடம் கீழ்கண்டவாறு அமையும்.
நான் செய்யவேண்டிய வேலையின் அளவு, நான் சந்திக்கும் பங்கேற்பாளர்களின் அளவுக்குச் சமமாக இருக்கும். நூறு பேரைச்சந்திக்கும்போது நூறுமுறை கைகுலுக்கவேண்டியிருக்கிறது. இதை நிரலில் எழுதும்போது ஒரு எளிய for loop ஆக இருக்கும்.
[code lang=”ruby”]
person.each do |person|
greet(person)
end
[/code]
ஒவ்வொருவரையும் சந்திக்கும்போது, வெறுமனே கைகுலுக்குவதுடன் நிறுத்திவிடாமல், ஒருசில நொடிகள் செலவிட்டு அவர்களுடன் உரையாடி, அவர்களைப்பற்றி கேட்டறிந்து, அவர்கள் கேள்விகளுக்கு விடையளிக்கிறேன் என வைத்துக்கொள்வோம். இந்த வழிமுறையின் வரைபடம் கீழ்கண்டவாறு இருக்கும். முந்தைய படத்தைப்போலவே இதுவும் நேர்கோடு தான். ஆனால், இதன் சாய்வு, முந்தைய கோட்டைவிட அதிகமாக இருக்கிறது. ஒவ்வொரு நபரிடமும் அதிகநேரம் செலவழிப்பதை இது காட்டுகிறது. வழிமுறையில் நாம் செய்த மாற்றம் வரைபடத்தில் கோணத்தின் மாற்றமாக வெளிப்பட்டுள்ளது.
மாறாக, நமது பழைய கைகுலுக்கும் வழிமுறைக்கே சென்றுவிடுவோம். ஆனால், என்னுடைய தயக்க சுபாவத்தின் காரணமாக கைகுலுக்கத்தொடங்குவதற்குமுன் என்னைத் தயார் செய்துகொள்வதற்கு எனக்கு சிறிதுநேரம் தேவைப்படுகிறது என வைத்துக்கொள்வோம். இதன் திறனை விளக்கும் வரைபடம் கீழ்கண்டவாறு அமையும்.
இக்கோட்டின் சாய்வும், முதல் கோட்டின் சாய்வும் ஒன்றாகவே இருக்கிறது. ஆனால், வேலையைத்தொடங்குவதற்கு சில முன்னேற்பாடுகள் செய்யவேண்டியிருப்பதால், கோட்டின் தொடக்கப்புள்ளி மாறுபட்டிருக்கிறது.
உண்மையில் பார்த்தால், ஒவ்வொரு கைகுலுக்கும் வழிமுறையும் வெவ்வேறானதே. ஆனால் Big O குறியீட்டின்படி இவையனைத்தும் ஒன்றாகவே கருதப்படுகின்றன. அதாவது, ஒவ்வொரு புதிய உள்ளீட்டிற்கும் நாம் புதிதாகச் செய்யவேண்டியவேலையின் அளவில் மாற்றம் இருப்பதில்லை. பத்துபேருடன் கைகுலுக்கும்போது நான் பத்து அலகுகள் வேலைசெய்கிறேன். பதினோராவது நபருடன் கைகுலுக்கும் போது ஒரு அலகு வேலை அதிகமாகச் செய்யவேண்டியுள்ளது. பனிரெண்டாவது நபருக்கும் அதே ஒரு அலகு வேலை அதிகரிக்கிறது. இதனை O(N) என குறிப்பிடுகிறோம். இவ்வரைபடங்களின் கோணத்தைப்பற்றியோ, இடத்தைப்பற்றியோ கவலைப்படத்தேவையில்லை. இவையனைத்தும் பூச்சியமல்லாத சாய்வையுடைய நேர்கோடுகளே.
அறிமுகங்கள்:
கைகுலுக்கும்போது மாநாட்டிற்குவந்த அனைவரையும் சந்திக்கும் வாய்ப்பு எனக்குக் கிடைக்கிறது. அதேபோல, அவர்கள் ஒருவர் மற்றொருவரைச்சந்திக்கும் வாய்ப்பையும் ஏற்படுத்திக்கொடுக்கவேண்டுமென விரும்புகிறேன். எனவே, ஒவ்வொருவரையும், மற்றொருவருக்கு அறிமுகப்படுத்த முடிவெடுக்கிறேன். இதற்கான நிரலில் இரண்டு for loop ஐப்பயன்படுத்தவேண்டியிருக்கும்.
[code lang=”ruby”]
people.each do |person|
people.each do |another_person|
introduce(person, another_person)
end
end
[/code]
கீழே இதற்கான வரைபடத்தைக்காணலாம்.
நமக்குக்கிடைத்திருப்பது ஒரு நேர்கோடல்ல. இவ்வரைபடம் மேல்நோக்கி வளைந்து ஏறத்தாழ செங்குத்தாகச் செல்கிறது. ஏனென்றால், ஒவ்வொரு புதிய விருந்தினருக்கும், நாம் பழைய விருந்தினர்கள் அனைவரையும் அறிமுகம் செய்துவைக்கவேண்டும். ஒவ்வொரு புதிய விருந்தினருக்கும் நாம் செய்யவேண்டியவேலை, முந்தைய புதிய விருந்தினருக்குச்செய்யவேண்டியவேலையைவிட அதிகமானதாக இருக்கிறது..
எடுத்துக்காட்டாக, ஓர் அறையில் ஏற்கனவே பத்துபேர் இருப்பதாக வைத்துக்கொள்ளலாம். இப்போது புதிதாக ஒருநபர் வந்தால், அவருக்கு அறையிலுள்ள பத்து பேரை அறிமுகம் செய்துவைக்கவேண்டும். ஒவ்வொரு அறிமுகத்தையும் ஒரு அலகு வேலையாகக்கொண்டால், நாம் பத்து அலகுகள் வேலைசெய்யவேண்டும். அதேபோல, நூறாவது நபருக்கு மீதியுள்ள தொண்ணூற்றொன்பது பேரையும் அறிமுகம்செய்யவேண்டும்.
ஒவ்வொரு புதிய உள்ளீடும், பழைய உள்ளீட்டிற்கான வேலையைவிட கூடுதலான வேலையைச் செய்யவைக்கிறது. இவ்வகை படிமுறையை O(N^2) என வகைப்படுத்துகிறோம்.
வரவேற்புரையாற்றுதல்:
நமது மாநாட்டிற்குப்பெருந்திரளான மக்களை நாம் எதிர்பார்க்கிறோம். வந்திருக்கும் ஒவ்வொருவரையும் நேரில் சந்திப்பதற்கோ, ஒருவருக்கொருவரை அறிமுகம்செய்துவைப்பதற்கோ நமக்கு நேரமில்லை. எனவே, பொதுவாக மேடையிலேறி, ஒரு வரவேற்புரையை வாசித்துவிட்டு அமர்கிறோம்.
இதனை நிரலில் எழுதும்போது நமக்கு loop எதுவும் தேவைப்படவில்லை.
[code lang=”ruby”]
greet(people)
[/code]
இவ்வழிமுறையில், உள்ளீட்டைப்பொருத்து நமது வேலை மாறுபடுவதில்லை. இதற்கான வரைபடம் ஒரு கிடைமட்டக்கோடாக இருக்கிறது.
இவ்வகை படிமுறைகளை O(1) என வகைப்படுத்துகிறோம். உள்ளீட்டைக்குறிக்கப் பயன்படுத்தும் N என்பது இக்குறியீட்டில் இடம்பெறவில்லையென்பதை கவனிக்கவேண்டும். வந்திருப்பது பத்துபேராக இருந்தாலும், பத்தாயிரம் பேராக இருந்தாலும் நமது வேலையில் மாற்றமில்லை.
இதுபோன்ற வழிமுறைகளில் உள்ளீட்டின் அளவை எவ்வளவு அதிகரித்தாலும் வழிமுறைக்கு அதனால் பாதிப்பில்லை. பேரளவாக்கத்திற்கு மிகவும் பொருத்தமான வழிமுறைகள் இவ்வகையைச் சார்ந்தவையே.
மூலம்: Nathan Long எழுதிய Understanding Big O Notation என்ற கட்டுரையின் சுருக்கம். அவரது அனுமதியோடு மொழிபெயர்க்கப்பட்டு படங்களும் பயன்படுத்தப்பட்டுள்ளது.