التدوين المقارب - هل يتم تبسيط n (log n) (log n)؟

Question

إذا كان لدي خوارزمية تأخذ خطوات n log n (على سبيل المثال.heapsort)، حيث تستغرق الخطوات وقت تسجيل n (على سبيل المثال.مقارنة/تبادل الأعداد الصحيحة "الكبيرة" في النطاق من 0 إلى n-1)، ما هو الحد المقارب للعملية بأكملها.

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

هل غريزتي خاطئة تمامًا في هذا؟

يحرر

يبدو أن المثال البسيط لتجنب تعقيد المشكلة قد أدى إلى تعقيد المشكلة.اوه حسناً.

السبب الحقيقي للسؤال هو أنني غالبًا ما يكون لدي خوارزمية قياسية ذات تعقيد معروف، ولكن يتم تنفيذها باستخدام حاويات أساسية مختلفة، بحيث تكون الخطوات الفردية هي O(log n) بدلاً من O(1).على سبيل المثال، خوارزمية تصغير Hopcrofts automaton هي O(n log n) - ولكن إذا بدأت في استخدام حاويات الشجرة الثنائية للحالات والانتقالات والنتائج الوسيطة، فإن الخطوات نفسها تصبح O(log n) - فإن O(n log n) هي لم يعد صالحًا لأن افتراض الوصول إلى O(1) غير صالح.

ومع ذلك، سيزعم الناس أن هناك حالات n وm انتقالات، لكن n وm يميلان إلى أن يكونا مرتبطين خطيًا بالأتمتة، على افتراض أن عدد التعليقات التوضيحية للانتقال ثابت وأن الآلات حتمية إلى حد ما.

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

يحرر

أنا أيضًا مقتنع بشكل متزايد بأن "n (log n) (log n)" خطأ.

إذا كان a هو O(b log b) حيث b هو O(log c)، فما هو a من حيث c؟

Answer 1

وإليك برهان التناقض:

لنفترض أن الدالة f(n) = n(log n)(log n).لنفترض أننا نعتقد أنها أيضًا ثيتا(n log n)، لذا بمعنى آخر يوجد a حيث f(n) <= a * n log n يحمل قيمة n كبيرة.

فكر الآن في f(2^(a+1)):

f(2^(a+1)) = 2^(a+1) * سجل(2^(a+1)) * سجل(2^(a+1)) = 2^(a+1) * سجل (2^(a+1)) * (a+1)، وهو أكبر بشكل واضح من * 2^(a+1) * log(2^(a+1)))، ولدينا تناقض.لذلك فإن f(n) ليست دالة n log n.

Answer 2

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

في تطبيق معين، على الأرجح، تتبع الأعداد الصحيحة الكبيرة توزيعًا محددًا.على سبيل المثال، قد يكون من المعروف أن جميعها أقل من 10^20.إذا كان الأمر كذلك، فإن عمليات المقارنة تستغرق وقتًا ثابتًا (يتم تحديده بواسطة حد أعلى قدره 10^20).بعد ذلك، السجل M ثابت أيضًا، والتعقيد بأكمله موجود في O(N log N).

Answer 3

لن تتمكن من التقليل n (log n) (log n) ل n (log n) ببساطة لأن هذا ليس تخفيضًا بعامل ثابت.

ما المشكلة في n (log n)2?

Answer 4

حسنًا، مقياس التعقيد العام للبرنامج هو كما يلي:

التعقيد O(f(n)) يعني وجوده c, ، بحيث لا يزيد عدد خطوات آلة تورينج المقابلة قبل أن تنتهي عن c*f(n)، حيث n هو طول الإدخال.

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

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

• قد يشبه العمل الفعلي لوحدة المعالجة المركزية، حيث كل إضافة عدد صحيح 32 بت هي في الواقع خطوة واحدة (وتوجد خوارزميات تسيء استخدامها بالفعل، على سبيل المثال."المسيطرون على ناقل البت").
• نقوم بمقارنة خوارزميات مختلفة في نفس المجال (على سبيل المثال، مقارنة فرز المصفوفات عن طريق قياس عدد المقارنات).

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

---

أما بالنسبة لتعديلك الثاني، فالوضع مختلف.دع الخوارزمية الخاصة بك تكون معقدة لـ O(nسجل ن).لكنك تعلم أن الإدخال يتكون من M أرقام، كل من log K أرقام، لذلك `N = O(Mسجل K) (نحن بحاجة إلى فواصل الحساب، الخ).من الصحيح رياضيًا أن نكتب التعقيد الإجمالي كـ O(M * log K * (log M + log log K)))، لذا لا توجد مشكلة هنا.ولكننا عادةً ما نقوم بتجريد التفاصيل غير الضرورية لإيجاد أساس مشترك لمقارنة الخوارزميات المختلفة.