ماذا o (سجل (سجل (n))) - يعني تنافسية؟

Question

كنت أذهب من خلال بعض هياكل البيانات ولاحظت هذا بمثابة تعقيد الوقت: o (سجل (سجل (n)))) - تنافسية.

قرأت هذا المنافسة المستمرة كانت نسبة الوقت المتوقع / الأمثل. ولكن ماذا يعني أن يكون لديك مجموعة تنافسية؟

Answer 1

الخوارزمية عبر الإنترنت هي واحدة لا تعرف مدخلاتها مسبقا، ويجب أن "رد فعل" (بمعنى) إلى مدخلات لا يمكن التنبؤ بها. في المقابل، خوارزميات غير متصلة بالإنترنت هي تلك التي تعرف كل مدخلاتها مقدما.

يقارن التحليل التنافسي أداء خوارزمية مثالية عبر الإنترنت إلى خوارزمية دون اتصال بالإنترنت الأمثل. وبالتالي، فإن K- تنافسية يعني وجود خوارزمية غير متصلة بالإنترنت والتي تنفذ معظم مرات K-Times أسوأ من خوارزمية عبر الإنترنت. لذلك، o (lglgn) تنافسية يعني أن الخوارزمية غير المتصلة بالإنترنت الأمثل تؤدي إلى معظم LGLGN (تايمز ثابتة) أسوأ من الخوارزمية الأمثل عبر الإنترنت.

---

يمكن التفكير في مصطلح "K-PEVEPTERY" بنفس الطريقة مثل مصطلح "K- تقريب". تعني تقريب K يعني أن خوارزمية التقريب تؤدي إلى معظم مرات K أسوأ من الخوارزمية المثلى.

Answer 2

هذه يمكن أن يلقي بعض الضوء على سؤالك.

من الرابط أعلاه:

اسمحوا أن تكون خوارزمية BST، وتحدد (ق) كتكلفة أداء التسلسل S والاختبار (S، إلى) كحد أدنى تكلفة لأداء تسلسل S. خوارزمية A هي T - تنافسية إذا لجميع التسلسلات الممكنة، (s) <= t * opt (s، to) + o (m، n).