أنا أتعلم دورة كورسيرا حول تعقيد الوقت. لقد واجهت هذا في مقطع فيديو وأعتقد أن هناك خطأ ما. “لذا لنفترض أن لدينا خوارزمية يتناسب وقت تشغيلها تقريبًا مع n ونريدها تشغيلها على جهاز يعمل بسرعة جيجاهيرتز تقريبًا. ما حجم المدخلات التي يمكننا التعامل معها بحيث ننهي الحساب في ثانية واحدة؟ ؟” (وحدة المعالجة المركزية بسرعة 1 جيجا هرتز (10^9 دورات في الثانية))
“حسنًا، إذا تم تشغيله بحجم n تقريبًا، فيمكنك التعامل مع حوالي مليار حجم من المدخلات، قبل أن يستغرق الأمر أكثر من ثانية” (10^9 / 10^9)
“إذا تم تشغيله مثل n تربيع، فسيكون الأمر أسوأ بكثير. يمكنك فقط التعامل مع مدخلات بحجم حوالي 30000 قبل أن تستغرق أكثر من ثانية.” ن = 30000، (30000) ^2/10^9 = 0.9 ثانية ~ 1 ثانية
“إذا كانت المدخلات بحجم 2 إلى n، فهذا أمر سيء للغاية، ولا يمكنك التعامل إلا مع مدخلات بحجم حوالي 30 في الثانية” 2^30/10^9 ~ 1.07 ثانية
مع تعقيد n log(n)، إذا كان حجم الإدخال n هو 10^9، فيجب أن يستغرق 10^9 * log(10^9) / 10^9 = 9 ثانية، أليس كذلك؟ بطريقة ما يظهر 30 ثانية في الفيديو. قيل أيضًا أنه إذا كانت n = 10^7.5 فإن وقت التشغيل هو ثانية واحدة، وهو خطأ أيضًا في حساباتي.
لقد قمت بحساب كل حالة مع تعقيد n، n^2، 2^n وكان كل شيء صحيحًا، فقط حالة nlog(n) هي التي أخطأت
وهنا الصورة لمزيد من التفاصيل: https://i.upanh.org/2022/04/11/nlogn.jpg[^]
رابط فيديو الدورة (3:40 إلى 5:00 هو الجزء): https://www.coursera.org/lecture/algorithmic-toolbox/asymptotic-notation-zI8dH[^]
لقد قمت بتحرير السؤال بحيث يشبه تمامًا مقطع الفيديو الذي شاهدته في الدورة التدريبية
ما حاولت:
I calculated every case with the n, n^2, 2^n complexity and everything was right, only nlog(n) case messed up
الحل 1
يقتبس:إذا كان حجم الإدخال n هو 10^9، فيجب أن يستغرق 10^9 * log(10^9) / 10^9 = 9 ثانية، أليس كذلك؟
لا ! لا يمكنك حساب وقت التشغيل من تدوين Big O، على الأقل ليس بمفرده.
يخبرك تدوين Big O بتعقيد فئة الخوارزمية، وليس وقت التشغيل، وليس بشكل مباشر.
عندما يكون لديك وقت تشغيل لحجم بيانات معين، فإن تعقيد Big O يسمح لك بتقييم وقت التشغيل لحجم بيانات آخر.
توقيتك لمدة ثانية واحدة للبيانات من 20 إلى 10 ^ 6 يعني أنك بحاجة إلى التبديل إلى توقيت بالميلي ثانية للحصول على توقيت ذي معنى.
الحل 2
الكبير O لا يعطي الوقت المحدد للتنفيذ. انظر مثلا تدوين كبير O – ويكيبيديا[^] (ملكيات أقسام, الضرب في ثابت).
الحل 3
للإضافة إلى ما يقوله الآخرون، لا يمكنك مساواة دورات الساعة مباشرة مع وقت التنفيذ على أي حال – بعض عمليات الآلة تستغرق n دورات للتنفيذ، والبعض الآخر قد يستغرق n * 2. للإضافة إلى ذلك، يتم توصيل المعالجات الحديثة – لذلك بعض التعليمات قد يبدأ أثناء تنفيذ التعليمات الأخرى أو تخزينها مؤقتًا – لذلك قد يعتمد وقت التنفيذ على المدة التي مضت منذ آخر مرة تم فيها تنفيذ التعليمات وما إذا كانت بياناتها متاحة في ذاكرة التخزين المؤقت L1 أو L2 أو L3، وتوافر النوى المجانية للتنفيذ، بالإضافة إلى مجموعة من التعليمات الأخرى تفاصيل.
لا يمكنك أن تقول فقط “سرعة ساعتي هي X، لذا فإن وقت التنفيذ الخاص بي هو X * Y” – هناك العديد من العوامل الأخرى التي ستؤثر على ذلك.
الحل 5
30 ثانية هي المدة الصحيحة إذا كانت سجلاً2(ن). سجل2(1000) ~= 10.
يحرر: غالبًا ما تقوم خوارزميات O(n log(n)) بتقسيم المشكلة إلى نصفين بشكل متكرر، وحل كل جزء على حدة، ثم دمج الحلول. هذا هو السبب في تسجيل الدخول2 عادة ما يكون ضمنيًا. يعد Mergesort مثالاً جيدًا.
الحل 6
يخبرك تدوين O الكبير فقط كيف سيكون وقت التنفيذ يتغير عندما يتغير “حجم” المشكلة، فإنه لا يوفر تقديرًا فعليًا لحالة معينة.
بمعنى آخر، هناك عامل غير معروف، على سبيل المثال O(n2) ربما يقصد
time_needed = constant * n * n
حيث لا أحد يقول ما هي قيمة الثابت، وبالتالي لا توجد قيمة محددة للوقت المطلوب.
يخبرك المثال فقط أن المشكلة التي يبلغ حجمها ضعف حجمها ستستغرق وقتًا أطول بأربعة أضعاف لحلها.
コメント