बड़े-ओ नोटेशन में O((log n)^k) = O(log n) है, जहां k कुछ स्थिर है (उदाहरण के लिए लूप के लिए लॉगरिदमिक की संख्या), सच है?बिग ओह नोटेशन ओ ((लॉग एन)^के) = ओ (लॉग एन)?
मुझे अपने प्रोफेसर ने बताया कि यह कथन सत्य था, हालांकि उन्होंने कहा कि यह बाद में पाठ्यक्रम में साबित होगा। मैं सोच रहा था कि आप में से कोई भी इसकी वैधता का प्रदर्शन कर सकता है या एक लिंक है जहां मैं पुष्टि कर सकता हूं कि यह सच है या नहीं।
(1) यह सच है कि ओ (लॉग (एन^के)) = ओ (लॉग एन)।
(2) यह गलत है कि ओ (लॉग^के (एन)) (ओ ओ (लॉग एन)^के) भी लिखा गया है) = ओ (लॉग एन)।
निरीक्षण: (1) nmjohn द्वारा सिद्ध किया गया है।
व्यायाम: साबित करें (2)। (संकेत: एफ (एन) = लॉग^2 एन ओ (लॉग^2 एन) है। क्या यह ओ (लॉग एन) है? पर्याप्त रूप से बड़ी स्थिर सी क्या है, सभी n n से अधिक n, c log n > लोग इन^2 n)
संपादित करें:
एक संबंधित नोट पर, जो इस सवाल उपयोगी पाता है किसी को भी और/या दिलचस्प नई 'कंप्यूटर विज्ञान "StackExchange साइट के लिए कुछ प्यार दिखाने जाना चाहिए। यहां एक लिंक है। इस नई जगह को एक वास्तविकता बनाओ!
+1। अच्छा सीएस साइट प्रचार :) – helios
क्या आप सुनिश्चित हैं कि उसका मतलब ओ (लॉग एन^के) नहीं है, क्योंकि यह ओ (के * लॉग एन) = के * ओ (लॉग एन) = ओ (लॉग एन) के बराबर है।
समस्या लूप के लिए 2 लॉगरिदमिक थी, और उन्होंने स्पष्ट रूप से ब्रैकेट्स को इंगित करने के लिए कहा कि k को पूरे लॉग – user1084113
ओ (लॉग एन) कार्यों का एक वर्ग है। आप^के जैसे कंप्यूटेशंस निष्पादित नहीं कर सकते हैं। इस प्रकार, शब्द ओ (लॉग एन)^के मुझे समझ में भी नहीं आता है।
लूप – user1084113
-1 के लिए नेस्टेड लॉगरिदमिक पर लागू किया गया है। यह एक टिप्पणी है, जवाब नहीं। – Patrick87
बेहतर http://math.stackexchange.com –
_k_ क्या है पर इस पूछना? निरंतर? समस्या का वर्णन करने वाला एक और पैरामीटर? यदि पूरे logarithm पर _k_ लागू किया गया है, तो क्या आप इसके बजाय ओ ((_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ –
किए गए परिवर्तन, के स्थिर है। – user1084113