كيف تعرف متى كبير يا لوغاريتمي؟

Question

سؤالي ينشأ من المنصب "تفسير اللغة الإنجليزية العادية ل Big O". وبعد لا أعرف المعنى الدقيق لتعقيد اللوغاريتمي. أعلم أنه يمكنني إجراء الانحدار بين الوقت وعدد العمليات وحساب قيمة X التربيعية، وتحديد ذلك التعقيد. ومع ذلك، أريد أن أعرف طريقة لتحديدها بسرعة على الورق.

كيف يمكنك تحديد تعقيد لوغاريتمي؟ هل هناك بعض المعايير الجيدة؟

Answer 1

لست متأكدا مما إذا كان هذا هو ما تقصده، ولكن ... تعقيد لوغاريتمي عادة عند العمل مع هيكل بيانات انتشار مثل شجرة ثنائية متوازنة، والذي يحتوي على عقدة واحدة في الجذر، 2 أطفال، 4 أحفاد، 8 أحفاد كبيرة، وما إلى ذلك أساسا في كل مستوى، يضاعف عدد العقد من قبل بعض العامل (2) ولكن لا يزال واحد فقط من تلك المشاركة في التكرار. أو كمثال آخر، حلقة يضاعف المؤشر في كل خطوة:

for (int i = 1; i < N; i *= 2) { ... }

أشياء مثل هذه هي توقيعات تعقيد لوغاريتمي.

Answer 2

ليست صارمة، ولكن لديك خوارزمية تقسيم العمل بشكل أساسي يجب القيام به بمقدار النصف في كل تكرار، ثم لديك تعقيد لوغاريتمي. المثال الكلاسيكي هو البحث الثنائي.

Answer 3

نظرية سيد عادة ما يعمل.

Answer 4

إذا كنت تريد فقط أن تعرف عن LOGARITMICMIC Big Oh، فستكون على مراقبة عندما يتم قطع بياناتك في نصف كل خطوة من خطوة تكرار.

هذا لأنه إذا كنت تقوم بمعالجة البيانات 1/2 كبيرة مثل الخطوة قبل ذلك، فهي سلسلة لا حصر لها.

Answer 5

وهنا طريقة أخرى لقولها.

لنفترض أن الخوارزمية خطية في عدد الأرقام في حجم المشكلة. لذلك، ربما لديك خوارزمية جديدة للعاملين بعدد كبير، يمكنك إظهار أن تكون خطيا في عدد الأرقام. يتطلب عدد العشرين من العاشرة من رقمين ضعف ذلك إلى العامل كرقم 10 أرقام باستخدام خوارزمية الخاص بك. سيكون هذا لديه تعقيد السجل. (وسيكون الأمر يستحق شيئا للمخترع.)

التهدئة له نفس السلوك. يستغرق ما يقرب من 10 خطوات التهدئة لخفض طول الفاصل الزمني بعامل 1024 = 2 ^ 10، ولكن 20 خطوة فقط ستقطع الفاصل الزمني لعامل 2 ^ 20.

لا يعني تسجيل التعقيد دائما خوارزمية سريعة في جميع المشاكل. قد يكون العامل الخطي أمام O (سجل (n)) كبيرا. لذلك قد تكون خوارزمية الخاص بك أمر فظيع عن مشاكل صغيرة، وليس من المفيد حتى أن حجم المشكلة كبير مراعاة أن الخوارزميات الأخرى موت وفاة أسية (أو متعددة الحدود).