العودة إلى الدراسة

المحاضرة 3 من 10

30 دقيقة تقريبًا

Check Termination, Then Find the Maximum

Check whether code finishes, count the parts that actually run, and build a correct algorithm for the largest array element.

تصفّح الدفتر
Step 1 of 7 · Follow the example

What the code does is not its running time

Goal: Describe the intended result before calculating work.

Consider this task: if a > b, add the even values; otherwise add the odd values. This describes what the code is meant to compute. Even values are divisible by 2; odd values are not.

To analyze time, we need more information: how many values are processed, and how much work is done for each one?

Suppose the first branch processes n values, the second processes m values, and each value takes constant work. Only one branch runs. If either branch is possible, the worst-case time is O(max⁡(n,m))O(\max(n,m)) as the sizes grow.

Read incomplete pseudocode carefully
الكود أو الخطوات
if a > b
    for (i 0 → n)
        Sum(even)
else
    for (i 0 → m)
        Sum(odd)

This is shorthand, not a complete executable program. It does not fully define Sum or the exact loop bounds. We cannot use it alone to prove an exact number of operations.

The analysis above explicitly assumes n or m iterations and constant work per iteration. If Sum scans a whole list on every call, that call has its own cost and we must include it.

When asked for the code's purpose, describe its result. Repeating the words “if” and “for,” or writing only a complexity expression, does not explain what it computes.

Remember: Purpose and running time are two separate questions.

موضعك محفوظ تلقائيًا
مصادر الدرس وملاحظات المراجعة

يعتمد ترتيب الموضوعات والأمثلة على صفحات 15–19 من الدفتر. نسبة الدفتر إلى الدكتور غير مؤكدة. الشرح والتفاعلات التعليمية صياغة مساعدة، وليست نقلًا حرفيًا.

شرح عربي مساعد يعتمد ترتيب الموضوعات والأمثلة في الدفتر المستلم. المصدر الأصلي محفوظ، وتفاصيل التصحيحات والإضافات في ملاحظات المراجعة. لا يوجد دليل يؤكد اسم الدكتور أو مطابقة محاضرات الدفتر للتسجيلين.

نسبة الدفتر إلى الدكتور غير مؤكدة. من تصحيحات القراءة: while دون تحديث counter وfor بلا شرط قد لا تنتهيان؛ لا نعطيهما حدًا منتهيًا. القيمة الثابتة في المثال هي m=10000. حساب Max يميّز بين عدد المقارنات وعدد فحوص loop. الأنشطة تعليمية إضافية.

تصفّح صفحات هذا الدرس من الدفتر
خطوة صغيرة. فهم أعمق.ألجولاب · دفتر شخصي للدراسة