O(N log N) التعقيد - مماثلة الخطي?

Question

لذلك أعتقد أنني ذاهب للحصول على دفن على السؤال تافهه مثل هذا السؤال ولكن أنا مرتبك قليلا عن شيء.

لقد نفذت فرز سريع في Java و C و كنت أقوم ببعض الأساسية comparissons.الرسم البياني خرج عن اثنين من خطوط مستقيمة ، مع ج كونها 4ms أسرع من جافا نظيره أكثر من 100 ، 000 عشوائية الاعداد الصحيحه.

رمز بلدي التجارب يمكن العثور عليها هنا ؛

الروبوت المرجعية

لم أكن متأكدا ما (n log n) خط ستبدو ولكن لم أكن أعتقد أنه سيكون مباشرة.أردت فقط أن تحقق من أن هذا هو النتيجة المتوقعة و التي يجب أن لا محاولة للعثور على خطأ في التعليمات البرمجية.

أنا عالقة الصيغة في excel و قاعدة 10 يبدو أن خط مستقيم مع شبك في البداية.هل هذا بسبب الفرق بين log(n) و log(n+1) يزيد خطيا?

شكرا

غاف

Answer 1

اجعل الرسم البياني أكبر وسترى أن O (N Logn) ليس خطا مستقيما تماما. ولكن نعم، إنه قريب جدا من السلوك الخطي. لمعرفة لماذا، فقط تأخذ لوغاريتم عدد أعداد كبيرة جدا.

على سبيل المثال (قاعدة 10):

log(1000000) = 6
log(1000000000) = 9
…

لذلك، لفرز 1،000،000 أرقام، يضيف الفرز O (N Logn) عاملا قياسيا 6 (أو أكثر قليلا لأن معظم خوارزميات الفرز ستعتمد على LOGARIMMS Base 2). ليس الكثير فظيعة.

في الواقع، هذا عامل السجل هو وبالتالي صغيرة بشكل غير عادي أنه بالنسبة لمعظم أوامر الحجم، أنشأت خوارزميات OR O (N LOGN) الخوارزميات الزمنية الخطية. مثال بارز هو إنشاء هيكل بيانات صفيف لاحقة.

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

Answer 2

لمعلوماتك, فرز سريع هو في الواقع O(n^2) ، ولكن مع متوسط حالة O(nlogn)

لمعلوماتك هناك فرق كبير جدا بين O(n) و O(nlogn).هذا هو السبب في أنه لا boundable بواسطة O(n) أي ثابت.

بالنسبة الرسومية مظاهرة انظر:

Answer 3

للحصول على مزيد من المتعة في الوريد مماثل، حاول التخطيط للوقت الذي اتخذته ن العمليات على المعيار فك تشفير هيكل البيانات. وبعد لقد ثبت أن تكون مقارب ن α(ن) حيث α (ن) هو معكوس وظيفة أكيرمان (على الرغم من أن كتاب الخوارزميات المعتادة الخاصة بك، فمن المحتمل أن تظهر كتابا فقط ن تسجيل الدخول ن أو ربما ن سجل* ن). لأي نوع من الأرقام التي من المحتمل أن تواجهها حجم الإدخال، α (ن) 5 (وسجل بالفعل *ن≤ 5)، على الرغم من أنها تقترب من ما لا نهاية لها مقاربة.

ما أفترض أنه يمكنك التعلم من هذا هو أنه في حين أن التعقيد المقارب هو أداة مفيدة للغاية للتفكير في الخوارزميات، إلا أنها ليست نفس الشيء ككفاءة عملية.

Answer 4

1. عادة ما تحتوي خوارزميات O (N * Log (N) على تطبيق لوغاريتمي 2-قاعدة.
2. ل n = 1024، سجل (1024) = 10، لذلك n * log (n) = 1024 * 10 = 10240 العمليات الحسابية، زيادة حسب ترتيب من حيث الحجم.

لذلك، فإن O (N * Log (n)) يشبه الخطي فقط مقابل كمية صغيرة من البيانات.

نصيحة: لا تنس أن QuickSort يتصرف بشكل جيد للغاية على بيانات عشوائية وأنه ليس خوارزمية O (N * LOG (N).

Answer 5

يمكن ترحيل أي بيانات على خط إذا تم اختيار المحاور بشكل صحيح :-)

يقول ويكيبيديا Big-O هو أسوأ الحالات (أي f (x) هو o (n) يعني f (x) "يحدها أعلاه" بواسطة n) https://en.wikipedia.org/wiki/big_o_notation.

فيما يلي مجموعة رائعة من الرسوم البيانية التي تصور الاختلافات بين الوظائف المشتركة المختلفة:http://science.slc.edu/~jmarshall/courses/2002/spring/cs50/bigo/

مشتق من السجل (X) هو 1 / س. هذه هي الطريقة التي يزيد تسجيلها بسرعة (x) كزود x. إنه ليس خطيا، على الرغم من أنه قد يبدو وكأنه خط مستقيم لأنه ينحني ببطء شديد. عند التفكير في O (Log (n))، أفكر في الأمر كما o (n ^ 0 +)، أي أصغر قوة ن ليس ثابتا، لأن أي قوة ثابتة إيجابية لن تتغلب عليها في النهاية. إنه ليس دقيقا بنسبة 100٪، لذلك سيغضب الأساتذة إليك إذا شرحت ذلك بهذه الطريقة.

الفرق بين سجلات اثنين من القواعد المختلفة هو مضاعف ثابت. ابحث عن الصيغة لتحويل السجلات بين قاعدتين: (تحت "تغيير القاعدة" هنا: https://en.wikipedia.org/wiki/logarithm.) الحيلة هي علاج K و B كما الثوابت.

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

Answer 6

سجل (n) هو (جدا) تقريبا عدد الأرقام في N. لذلك، بالنسبة للجزء الأكبر، هناك اختلاف بسيط بين السجل (N) وسجل (N + 1)

Answer 7

حاول التخطيط لخط خطي حقيقي فوقها وسترى الزيادة الصغيرة. لاحظ أن قيمة Y في 50،0000 أقل من قيمة 1/2 Y على 100،000.

هناك، لكنها صغيرة. وهذا هو السبب في O (NLOG (N)) جيد جدا!