ما معنى O(polylog(n))؟على وجه الخصوص، كيف يتم تعريف polylog(n)؟

Question

مختصر:
عندما تقول الأوراق الأكاديمية (علوم الكمبيوتر) "O(polylog(n))"، ماذا تعني؟لست في حيرة من أمري من خلال تدوين "Big-Oh"، الذي أعرفه جيدًا، ولكن من خلال الدالة polylog(n).إنهم لا يتحدثون عن وظيفة التحليل المعقدة لي_س(ض) أظن.او انهم؟شيء مختلف تماما ربما؟

تفاصيل اكثر:
في الغالب من أجل المصلحة الشخصية، لقد قمت مؤخرًا بالبحث في العديد من الأوراق البحثية حول مصفوفات اللاحقة المضغوطة، على سبيل المثال. مزايا البحث العكسي - ذاكرة ثانوية فعالة والتنفيذ الموزع لمصفوفات اللاحقة المضغوطة.تتضمن تقديرات التعقيد الحسابي المذكورة أحيانًا polylog(n)، وهي وظيفة لست على دراية بها.

ويكيبيديا تعطي تعريفا polylog_س(ض) والذي يبدو أنه يتعلق بشكل أساسي بالتحليل المعقد ونظرية الأعداد التحليلية.أشك في أن الأمر لا يتعلق بـ polylog(n) الموجود في أوراق الضغط، على الرغم من أنني أحب أن أسمع خلاف ذلك من شخص أكثر دراية.إذا كان الأمر كذلك، فلماذا يعتبر من المعقول حذف الحرف المنخفض؟

تخميني الوحيد هو أنه ربما يعني O (polylog (n)) "مقاربًا لوظيفة متعدد الحدود للسجل (N)." لكن هذا مجرد تخمين:ليس لدي أي دليل على ذلك، وسيكون إساءة استخدام التدوين للتمهيد.

على أية حال، سيكون موضع تقدير كبير وجود رابط لتعريف موثوق إلى حد معقول!

Answer 1

إساءة استخدام التدوين أم لا، polylog(n) يعني "بعض كثيرات الحدود في log(n)"، تمامًا كما يمكن أن يعني "poly(n)" "بعض كثيرات الحدود في n".لذا فإن O(polylog(n)) تعني "O((log n)"^ك) لبعض ك".(يرى ويكيبيديا:متعدد اللوغاريتمي, ، أو لنرى ذلك في السياق، البروفيسور.مدونة سكوت آرونسون: معدلات النمو المفضلة لدي.)

النقطة المهمة هي أنه مثلما لا نهتم في كثير من الأحيان بالعوامل الثابتة، فإنه غالبًا ما يكون من المناسب تجاهل قوى اللوغاريتمات.في بعض الأحيان يتم تجاهل "عوامل السجل" بالكامل وقد ترى "Õ(f(n))" — O مع علامة التلدة فوقها - والتي وسائل "O(f(n) polylog(f(n)))"، أي "O(f(n) (log f(n))"^ك) لبعض ك".

Answer 2

طريقة استخدامه في هذه الورقة يبدو أنه يصف شيئًا ما على النحو التالي:

يا (سجل ^ ص ن)

Answer 3

Polylog(n) هو مجرد "متعدد الحدود في سجل n". ويكيبيديا

Answer 4

مختلف مقال بوليلوج.تخمينك قريب جدًا.

Answer 5

أنا متأكد من أنهم يقصدون فقط المحور الحقيقي للعدد الصحيح الموجب: Re(n) = n

Answer 6

يمنحك ولفرام اختيار, ، منها متعدد اللوغاريتم الصفحة تبدو واعدة للغاية.