मुझे पता है कि बिग ओ, थीटा और ओमेगा नोटेशन क्या हैं, लेकिन उदाहरण के लिए, यदि मेरा एल्गोरिदम एक के अंदर है, तो लूपिंग एन बार, मेरी जटिलता ओ (एन²) होगी, लेकिन ϴ के बजाय ओ (एन²) क्यों है (एन²)? चूंकि जटिलता वास्तव में ओ (एन²) और Ω (एन²) है, तो यह ϴ (एन²) भी होगी, और मुझे ओ (एन²) के बजाय ϴ (एन²) का उपयोग न करने का कोई कारण नहीं दिख रहा है, क्योंकि ϴ(n²) ओ (एन²) के मामले में न केवल ऊपरी, ऊपरी और निचले मूल्य के साथ मेरी जटिलता को प्रतिबंधित करता है।

4
Diego Vinicius 20 सितंबर 2020, 21:16

1 उत्तर

सबसे बढ़िया उत्तर

अगर f(n) = Θ(g(n)) तो f(n) = O(g(n))। ऐसा इसलिए है क्योंकि Θ(g(n)) ⊆ O (g(n)).

आपके विशिष्ट मामले में यदि लूप बिल्कुल n^2 समय पर चलता है तो समय जटिलता O(n^2) और Θ(n^2) दोनों में होती है।
बिग-ओ आम तौर पर पर्याप्त होने का मुख्य कारण यह है कि एल्गोरिदम के प्रदर्शन का विश्लेषण करते समय हम सबसे खराब स्थिति समय जटिलता में अधिक रुचि रखते हैं, और सबसे खराब स्थिति को जानना आमतौर पर पर्याप्त होता है। इसके अलावा, हमेशा एक तंग सीमा खोजना संभव नहीं है।

4
abc 20 सितंबर 2020, 21:42