मुझे यह समस्या है जहां कक्षा में मेरे प्रोफेसर ने कहा कि नीचे दिया गया कथन O(log(n)) है जहां मैंने सोचा था कि यह O(n) था। क्या कोई स्पष्टीकरण दे सकता है कि यह O(log(n)) कैसे है?बिग ओ नोटेशन और क्लास लेक्चर से कम नहीं है
Printing a number of magnitude n in binary. Assume that printing each bit requires constant time.
आप कुछ उदाहरण काम करना चाहिए। बाइनरी में कुछ संख्याएं लिखें। उदाहरण के लिए, 63, 255, और 511 में कितने बिट हैं? ध्यान दें कि बिट्स की संख्या लगभग संख्या जितनी जल्दी बढ़ती नहीं है।
यह ओ (लॉग (एन)) है क्योंकि आपको 0 या 1 मुद्रित करने के लिए हर बार 2 से विभाजित करना होगा। उदाहरण के लिए, बाइनरी में 256 प्रिंट करने के लिए, आपको 256 से 2 से विभाजित करना होगा और हर बार % 2 के परिणाम प्रिंट करना होगा।
256 % 2 -> 0
64% 2 -> 0
32 % 2 -> 0
16 % 2 -> 0
8 % 2 -> 0
4 % 2 -> 0
2 % 2 -> 0
1 % 2 -> 1
तो, परिमाण के एक नंबर के लिए आप 8 बार जो log 256 के बराबर है पुनरावृति करना होगा 256।
, यदि मैं बाइनरी में 7 करना चाहता था तो यह '7% 2 = 1' फिर 7 से 2 विभाजित करेगा और यह 3.5 होगा लेकिन एक पूर्णांक के रूप में इसके 3' ' 3% 2 = 1' '1% 2 = 1' इसलिए 7 बाइनरी में' 0111' है, क्या यह सही है? – Kayracer
आप सही हैं, प्रत्येक बिट को मुद्रित करने में 3 कदम उठाए गए हैं। तो, यह लगभग 'लॉग 7' है। – alayor
मीठे, धन्यवाद – Kayracer
ओ (लॉग (एन)) आधे से डेटा काटने के बारे में है। जब एक एल्गोरिदम का प्रत्येक चरण शेष इनपुट के अंश को बाहर करता है - उदा। आप हमेशा आधा, या तीसरे स्थान पर या पिछले चरण के 99/100 तक स्थान काटते हैं - कि एल्गोरिदम ओ (लॉग (एन)) समय में चलता है।
उम्मीद है कि यह
बाइनरी नोटेशन में लिखे गए नंबर 'एन' के कितने बिट्स हैं? यह छोटी संख्याओं के लिए कुछ उदाहरण करने में मदद कर सकता है। –
यह सवाल है और – Kayracer
को कोई अन्य जानकारी नहीं दी गई है तो कुछ उदाहरणों को तैयार करें। बाइनरी में 0 से 64 तक संख्याएं लिखें। नंबर की तुलना बिट्स की संख्या से करें। –