هل تفرض Big-Oh قسما أمرا على مجموعة الوظائف "المعتادة"؟

Question

المثال في > هذه الإجابة تثبت حقيقة مألوفة لطلاب CS - أن "Big-O" هو ليس طلب إجمالي. ومع ذلك، فإن معظم خوارزمية تشغيل الأوقات التي تم تحليلها باستخدام تدوين كبير لا يتم التعبير عنها في شكل موصول مثل هذا المثال. في الواقع، معظم الخوارزميات التي أكنت على دراية بها وقت قيد التشغيل معبرا عنها من حيث متعدد الحدود والأسئلة والسجلات.

النظر في فئة الوظائف المعرفة بشكل متكرر والتي تتضمن $ f (n)= c $ لأي $ c $ ، $ f (n)= n $ ، وأي وظائف من النموذج $ f + g، f \ cdot g، \ log (f)، \ exp (f) $ حيث $ f، g $ موجودة في الفصل. هل $ O $ فرض تقسيم أمر على هذه الفئة من الوظائف؟ الوظائف ذات نفس الطبقة الكبيرة="حاوية الرياضيات"> $ O $ النمو في نفس الجزء.

هنا هي أفكاري:

لاحظ أن تحديد $ f \ cdot g $ هو في الواقع زائدة عن الحاجة، لأن $ f \ cdot g=exp ( \ Log (f) + \ log (g)) $ . نظرا لأن الوظائف محددة محوس، فربما يوجد دليل حثي.

Answer 1

أظهر ذلك من قبل هاردي في مجزول له أوامر اللانهاية .