অ্যাসিম্পটোটিক নোটেশনস
অ্যাসিম্পটোটিক বিশ্লেষণের জন্য অ্যালগরিদমের জটিলতাগুলি উপস্থাপন করতে অ্যাসিম্পোটিক নোটেশন ব্যবহার করা হয়। এই স্বরলিপিগুলি জটিলতাগুলিকে উপস্থাপন করার জন্য গাণিতিক সরঞ্জাম। তিনটি স্বরলিপি রয়েছে যা সাধারণত ব্যবহৃত হয়৷
৷বিগ ওহ স্বরলিপি
বিগ-ওহ (ও) স্বরলিপি একটি ধ্রুবক ফ্যাক্টরের মধ্যে একটি ফাংশন f(n) এর জন্য একটি উপরের বাউন্ড দেয়।
আমরা লিখি f(n) =O(g(n)), যদি ধনাত্মক ধ্রুবক 0 এবং c থাকে যাতে n0 এর ডানদিকে f(n) সবসময় c*g(n) এর উপর বা নীচে থাকে।
O(g(n)) ={ f(n) :এখানে ধনাত্মক ধ্রুবক c এবং n0 বিদ্যমান যাতে 0 ≤ f(n) ≤ c g(n), সমস্ত n ≥ n0}
বিগ ওমেগা নোটেশন
বিগ-ওমেগা (Ω) স্বরলিপি একটি ধ্রুবক ফ্যাক্টরের মধ্যে একটি ফাংশন f(n) এর জন্য একটি নিম্ন সীমা দেয়।
আমরা লিখি f(n) =Ω(g(n)), যদি ধনাত্মক ধ্রুবক 0 এবং c থাকে যে, n0 এর ডানদিকে f(n) সবসময় c*g(n) বা উপরে থাকে।
Ω(g(n)) ={ f(n):এখানে ধনাত্মক ধ্রুবক c এবং n0 বিদ্যমান যাতে 0 ≤ c g(n) ≤ f(n), সমস্ত n ≥ n0}
বিগ থিটা নোটেশন
Big-Theta(Θ) নোটেশন একটি ফাংশন f(n) একটি ধ্রুবক ফ্যাক্টরের মধ্যে আবদ্ধ করে।
আমরা লিখি f(n) =Θ(g(n)), যদি ধনাত্মক ধ্রুবক 0 এবং c1 এবং c2 থাকে যাতে n0 এর ডানদিকে f(n) সবসময় c1*g(n) এবং c2*g এর মধ্যে থাকে (n) অন্তর্ভুক্ত।
Θ(g(n)) ={f(n):এখানে রয়েছে ধনাত্মক ধ্রুবক c1, c2 এবং n0 যেমন 0 ≤ c1 g(n) ≤ f(n) ≤ c2 g(n), সমস্ত n ≥ n0}
