நெறிமுறையின் யுக்திகள் - Formula Sheet

முக்கியக் குறியீடுகள் மற்றும் சூத்திரங்கள்

1. அசிம்ப்டோடிக் குறியீடுகள் (Asymptotic Notations)

நெறிமுறைகளின் சிக்கல்களை விவரிக்கப் பயன்படும் குறியீடுகள்:

• மேல் எல்லை (Worst Case): \(T(n) = O(f(n))\) - நெறிமுறை எடுத்துக்கொள்ளும் அதிகபட்ச படிநிலைகள்.
• கீழ் எல்லை (Best Case): \(T(n) = \\Omega(g(n))\) - நெறிமுறை எடுத்துக்கொள்ளும் குறைந்தபட்ச படிநிலைகள்.
• சராசரி எல்லை (Average Case): \(T(n) = \\Theta(h(n))\) - நெறிமுறையின் மிதமான எல்லை.

2. நேரியல் தேடலில் சராசரி ஒப்பீடுகளின் எண்ணிக்கை

பட்டியலில் உள்ள உறுப்புகளின் எண்ணிக்கை \(n\) எனில், சராசரி ஒப்பீடுகளைக் கண்டறியும் சூத்திரம்:

\(Average = \\frac{n + 1}{2}\)

3. இருமத் தேடலில் மைய உறுப்பு கண்டறிதல் (Mid-point Calculation)

தேடல் பகுதியின் தொடக்கச் சுட்டு \(low\) மற்றும் இறுதிச் சுட்டு \(high\) எனில், மையச் சுட்டைக் காணும் சூத்திரம்:

\(mid = low + \\frac{high - low}{2}\)

குறிப்பு: மிதப்புப் புள்ளியைத் தவிர்க்க இதன் முழு எண் மதிப்பு மட்டுமே எடுத்துக்கொள்ளப்பட வேண்டும்.

4. பிபனோசி தொடர் சுழற்சி நிபந்தனை (Fibonacci Recurrence Relation)

முந்தைய இரு எண்களின் கூட்டுத்தொகையைக் கொண்டு அடுத்த எண்ணைக் கண்டறியும் சூத்திரம்:

\(Fib_n = Fib_{n-1} + Fib_{n-2}\)

இங்கு தொடக்க மதிப்புகள்: \(Fib_0 = 0\), \(Fib_1 = 1\) மற்றும் \(n \\ge 2\) ஆகும்.