संक्षिप्त:
जब अकादमिक (कंप्यूटर विज्ञान) के कागजात कहते हैं "ओ (पोलिलोग (एन))", उनका क्या अर्थ है? मैं "बिग-ओह" नोटेशन से उलझन में नहीं हूं, जिसे मैं बहुत परिचित हूं, बल्कि फ़ंक्शन पोलिलोग (एन) द्वारा। वे जटिल विश्लेषण फ़ंक्शन Lis(Z) के बारे में बात नहीं कर रहे हैं। या क्या वे? शायद कुछ अलग हो सकता है?ओ (पोलिलोग (एन)) का क्या अर्थ है? विशेष रूप से, पोलिलोग (एन) कैसे परिभाषित किया जाता है?
अधिक विस्तार:
अधिकतर व्यक्तिगत हित के लिए, मैं हाल ही में संपीडित प्रत्यय सरणी, उदा पर विभिन्न अधिक पत्र के लिए देख रहा है Advantages of Backward Searching -- Efficient Secondary Memory and Distributed Implementation of Compressed Suffix Arrays। कम्प्यूटेशनल जटिलता अनुमानों में कभी-कभी पोलिलोग (एन) शामिल होता है, जो एक ऐसा कार्य है जिसे मैं परिचित नहीं हूं।
विकिपीडिया polylogs(z) की परिभाषा देता है जो मुख्य रूप से जटिल विश्लेषण और विश्लेषणात्मक संख्या सिद्धांत के बारे में प्रतीत होता है। मेरा संदेह यह है कि यह संपीड़न पत्रों में पोलिलोग (एन) से संबंधित नहीं है, हालांकि मुझे किसी और से अधिक जानकारियों से सुनना अच्छा लगेगा। यदि ऐसा है, तो सबस्क्राइब को छोड़ना उचित क्यों है?
मेरा एकमात्र अन्य अनुमान यह है कि शायद ओ (पोलिलोग (एन)) का अर्थ "लॉग (एन) के बहुपद कार्यों के लिए असम्पीटिक होना चाहिए।" लेकिन यह केवल एक अनुमान है: मेरे पास इसका कोई सबूत नहीं है, और यह बूट करने के लिए संकेत का दुरुपयोग होगा।
किसी भी मामले में, एक उचित आधिकारिक परिभाषा के लिए एक लिंक की सराहना की जाएगी! Re(n) = n
आपने इसे कहाँ देखा है? –
लिंक किए गए सार में, यह कहा गया है "... ओएस (एम) समय में सीएसए की खोज की जा सकती है जब भी ओ (पोलिलोग (एन))।" – Managu
ओह, शायद सदाकाने [सोडा 2002] का आपका निश्चित उत्तर है। –