एकाधिक चर के लिए बिग ओ effeciency

Question

मैं एक समारोह की दक्षता को रेट करने की कोशिश कर रहा हूं जहां इनपुट तारों की एक सरणी है। एल्गोरिदम हमेशा इस सरणी में प्रत्येक आइटम के माध्यम से पुनरावृत्त करता है। इस सरणी में निहित यह तार परिवर्तनीय लंबाई के हैं। इस प्रारंभिक लूप के लिए, प्रत्येक स्ट्रिंग पर फ़ंक्शन प्रतिस्थापन फ़ंक्शन कहा जाता है। मेरा मानना ​​है कि प्रतिस्थापन कार्य स्वयं ही होगा (एन) जहां एन स्ट्रिंग की लंबाई है।

तो मैं उलझन में हूं कि यहां बड़ी ओ दक्षता का मूल्यांकन कैसे किया जाए। यदि एन सरणी का आकार है, तो मुझे पता है कि यह कम से कम ओ (एन) होगा। लेकिन परिवर्तनीय स्ट्रिंग लंबाई के साथ, आप स्ट्रिंग प्रतिस्थापन के साथ समग्र दक्षता को कैसे रेट करेंगे? क्या आप कहते हैं कि एन सरणी का आकार है और प्रत्येक स्ट्रिंग के विभिन्न आकारों का प्रतिनिधित्व करने के लिए अन्य चर का उपयोग करें?

Answer 1

मुझे यह कहने के दो तरीके दिखाई देते हैं (कई संभव से बाहर)।

पहला यह कहना है कि यह O(N) है जहां N वर्णों की कुल संख्या है।

अन्य आप कह सकते हैं O(N*M) जहां N स्ट्रिंग्स की संख्या है और M प्रति स्ट्रिंग वर्णों की औसत संख्या है। ध्यान दें कि यह वास्तव में मेरे उपरोक्त उत्तर के समान है। आप M = k/N कह सकते हैं, इसलिए आपको O(N*k/N) या O(k) मिलते हैं जहां के सभी तारों में कुल वर्ण हैं।

Answer 2

व्यक्तिगत रूप से, मैं इनपुट डेटा के आकार के माध्यम से दक्षता व्यक्त करता हूं (सरणी की लंबाई के विपरीत)। इसलिए, यदि इनपुट t बाइट्स है, तो चलने का समय O(t) होगा। और t यहां सभी तारों की एक आम लंबाई भी है।