هياكل البيانات 101 تحليل زمن تشغيل القوائم المنفذة باستخدام مصفوفة

تضرب هذه المقالة عصفورين بحجرٍ واحدٍ، حيث سنحل فيها تمرين المقالة السابقة مدخل إلى تحليل الخوارزميات، وسنتطرق لوسيلة نصنّف من خلالها الخوارزميات باستخدام ما يسمّى التحليل بالتسديد amortized analysis.

تصنيف توابع الصنف MyArrayList

يُمكِننا تحديد ترتيب نمو order of growth غالبية التوابع بالنظر إلى شيفرتها. على سبيل المثال، انظر إلى تنفيذ التابع get المُعرَّف بالصنف MyArrayList:

    public E get(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException();
        }
        return array[index];
    }

تستغرِق كل تعليمةٍ من تعليمات التابع get زمنًا ثابتًا، وبناءً على ذلك يستغرِق التابع get في المجمل زمنًا ثابتًا.

الآن وقد صنّفنا التابع get، يمكننا بنفس الطريقة أن نصنّف التابع set الذي يَستخدِمه. انظر إلى تنفيذ التابع set من التمرين السابق الذي مرّ بنا في الفصل الثاني:

    public E set(int index, E element) {
        E old = get(index);
        array[index] = element;
        return old;
    }

ربما لاحظت أن التابع set لا يفحص نطاق المصفوفة صراحةً، فهو يعتمد في ذلك على استدعائه للتابع get الذي يُبلِّغ عن اعتراض exception عندما لا يكون الفهرس صالحًا.

تَستغرق كل تعليمة من تعليمات التابع set -بما في ذلك استدعاؤه للتابع get- زمنًا ثابتًا، وعليه يُعدّ التابع set ثابت الزمن أيضًا.

ولننتقل الآن إلى بعض التوابع الخطيّة. انظر مثلاً إلى تنفيذنا للتابع indexOf:

    public int indexOf(Object target) {
        for (int i = 0; i<size; i++) {
            if (equals(target, array[i])) {
                return i;
            }
        }
        return -1;
    }

يحتوي التابع indexOf على حلقة تكرارية كما نرى، وفي كل مرورٍ تكراريٍّ في تلك الحلقة يستدعي التابعَequals. علينا إذًا أن نُصنّف التابع equals أولًا لنتمكن من تصنيف التابعindexOf. لننظر إلى تعريف ذلك التابع:

    private boolean equals(Object target, Object element) {
        if (target == null) {
            return element == null;
        } else {
            return target.equals(element);
        }
    }

يستدعي التابعُ السابق التابعَ target.equals الذي يعتمد زمن تنفيذه على حجم المتغير target وelement، ولكنه لا يعتمد على حجم المصفوفة، ولذلك سنَعُدّه ثابت الزمن لكي نُكمِل تحليل التابع indexOf.

لنعُد الآنَ إلى التابع indexOf. تَستغرق كل تعليمة ضمن الحلقة زمنًا ثابتًا، مما يقودنا إلى السؤال التالي: كم عدد مرات تنفيذ الحلقة؟

إذا حالفنا الحظ، قد نجد الكائن المطلوب مباشرةً ونعود بعد اختبار عنصر واحد فقط؛ أما إذا لم نكن محظوظين، فقد نضطرّ لاختبار جميع العناصر. لنقلْ إننا سنحتاج وسطيًّا إلى اختبار نصف عدد العناصر، ومن ثم يمكن القول بأن هذا التابع يصنّف بأنه تابع خطّيٌ أيضًا باستثناء الحالة الأقل احتمالًا، والتي يكون فيها العنصر المطلوب هو أول عنصر في المصفوفة.

وهكذا يتشابه تحليل التابع remove مع التابع السابق. وفيما يلي تنفيذه:

    public E remove(int index) {
        E element = get(index);
        for (int i=index; i<size-1; i++) {
            array[i] = array[i+1];
        }
        size--;
        return element;
    }

يَستدعِي التابعُ السابق التابعَ get ذا الزمن الثابت، ثم يُمرّ عبر عناصر المصفوفة بدايةً من الفهرس index. وإذا حذفنا العنصر الموجود في نهاية القائمة، فلن يُنفِّذ التابع حلقة التكرار على الإطلاق، وسيستغرِق التابع عندئذٍ زمنًا ثابتًا. في المقابل، إذا حذفنا العنصر الأول فسيمرّ التابع عبر جميع العناصر المتبقية، وبالتالي سيستغرِق التابع زمنًا خطيًا. لذلك يُمكِننا أن نَعُدّ التابع خطيًا في المجمل، باستثناء الحالة الخاصة التي يكون خلالها العنصر المطلوب حذفه واقعًا في نهاية المصفوفة أو على بعد مسافةٍ ثابتةٍ من نهايتها.

تصنيف التابع add

تستقبل النسخة التالية من التابع add فهرسًا وعنصرًا كمعاملات parameters:

    public void add(int index, E element) {
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException();
        }
        // أضف عنصرًا للتأكّد من ضبط حجم المصفوفة
        add(element);
        
        // حرك العناصر الأخرى
        for (int i=size-1; i>index; i--) {
            array[i] = array[i-1];
        }
        // ضع العنصر الجديد في المكان الصحيح
        array[index] = element;
    }

تستدعي النسخةُ ذات المعاملين add(int, E)‎ النسخةَ ذات المعامل الواحد add(E)‎ أولًا لكي تضع العنصر الجديد في نهاية المصفوفة، وبعد ذلك تُحرِّك العناصر الأخرى إلى اليمين، وتضع العنصر الجديد في المكان الصحيح.

سنُحلّل أولًا زمن النسخة ذات المعامل الواحد add(E)‎ قبل أن ننتقل إلى تحليل النسخة ذات المعاملين add(int, E)‎:

    public boolean add(E element) {
        if (size >= array.length) {
            // أنشئ مصفوفة أكبر وانسخ العناصر إليها
            E[] bigger = (E[]) new Object[array.length * 2];
            System.arraycopy(array, 0, bigger, 0, array.length);
            array = bigger;
        } 
        array[size] = element;
        size++;
        return true;
    }

تتضح لنا هنا صعوبة تحليل زمن النسخة ذات المعامل الواحد؛ لأنه لو كانت هناك مساحة غير مُستخدَمةٍ في المصفوفة، فسيستغرِق التابع زمنًا ثابتًا؛ أما لو اضطرّرنا لإعادة ضبط حجم المصفوفة، فسيستغرِق التابع زمنًا خطيًا؛ لأن التابع System.arraycopy يستغرِق بدوره زمنًا يتناسب مع حجم المصفوفة.

إذاً فهل هذا التابع ثابت أم خطي؟ يُمكِننا أن نُصنِّفه بالتفكير في متوسط عدد العمليات التي تتطلَّبها عملية الإضافة خلال عدد من الإضافات مقداره n. وسنفترض للتبسيط بأن لدينا مصفوفةً بإمكانها تخزين عنصرين فقط.

• في المرة الأولى التي سنستدعي خلالها add، سيجد التابع مساحةً شاغرةً في المصفوفة، وسيُخزِّن عنصرًا واحدًا.
• في المرة الثانية، سيجد التابع مساحةً شاغرةً في المصفوفة، وسيُخزِّن عنصرًا واحدًا.
• في المرة الثالثة، سيعيد التابع ضبط حجم المصفوفة، وينسخ العنصرين السابقين، ثم يخزن العنصر الجديد وهو الثالث، وسيُصبِح بإمكان المصفوفة تخزين 4 عناصر في المجمل.
• ستخُزِّن المرة الرابعة عنصرًا واحدًا.
• ستعيد المرة الخامسة ضبط حجم المصفوفة، وتنسخ أربعة العناصر السابقة، وتخزّن عنصرًا جديدًا وهو الخامس، وسيكون في إمكان المصفوفة تخزين ثمانية عناصر إجمالًا.
• ستُخزِّن المرات الثلاث التالية ثلاثة عناصر.
• ستنسخ المرة التالية ثمانية العناصر السابقة وتُخزِّن عنصرًا جديدًا وهو التاسع، وسيُصبِح بإمكان المصفوفة تخزين ستة عشر عنصرًا.
• ستُخزِّن سبعُ المرات التالية سبعةَ عناصر. وهكذا دواليك.

وإذا أردنا أن نلخص ما سبق:

• فإننا بعد 4 إضافات، سنكون قد خزَّنا 4 عناصر ونسخنا عنصرين.
• بعد 8 إضافات، سنكون قد خزَّنا 8 عناصر ونسخنا 6 عناصر.
• بعد 16 إضافةً، سنكون قد خزَّنا 16 عنصرًا ونسخنا 14 عنصرًا.

يُفترَض أن تكون قد استقرأت سير العملية وحصلت على ما يلي: لكي نُضيف عدد مقداره n من العناصر، سنضطرّ إلى تخزين عدد n من العناصر ونسخ عدد n-2 من العناصر، وبالتالي يكون عدد العمليات الإجمالي هو n+n-2 أي 2n-2.

لكي نحسب متوسط عدد العمليات المطلوبة لعملية الإضافة، ينبغي أن نقسِّم العدد الكلي للعمليات على عدد الإضافات n، وبذلك ستكون النتيجة هي 2‎-2/n. لاحِظ أنه كلما ازدادت قيمة n، ستقل قيمة الجزء الثاني 2‎/n. ونظراً لأن ما يهمنا هنا هو الأسّ الأكبر للأساس n، فيُمكِننا أن نَعُدّ التابع add ثابت الزمن.

قد يبدو من الغريب لخوارزمية تحتاج إلى زمن خطي أحيانًا أن تكون ثابتة الزمن في المتوسط. والفكرة هي أننا نضاعف طول المصفوفة في كل مرة نضطرّ فيها إلى إعادة ضبط حجمها. يُقلِّل ذلك عدد المرات التي نَنَسَخ خلالها جميع العناصر، أما لو كنا نضيف مقدارًا ثابتًا إلى طول المصفوفة بدلًا من مضاعفتها بمقدارٍ ثابت، فإنّ هذا التحليل لا يصلح.

يُطلَق على تصنيف الخوارزميات وفقًا لتلك الطريقة -أي بحساب متوسط الزمن الذي تستغرقه متتالية من الاستدعاءات- باسم التحليل بالتسديد. الآن وقد عرفنا أنّ التابع add(E)‎ ثابت الزمن، ماذا عن التابع add(int, E)‎؟ يُنفِّذ التابع add(int, E)‎ -بعد استدعائه للتابع add(E)‎- حلقةً تمُرّ عبر جزءٍ من عناصر المصفوفة وتُحرِّكها. تستغرِق تلك الحلقة زمنًا خطيًا باستثناء الحالة التي نضيف خلالها عنصرًا إلى نهاية المصفوفة، وعليه يكون التابع add(int, E)‎ بدوره خطيًا.

حجم المشكلة

ولننتقل الآن إلى المثال الأخير في هذا المقال. انظر فيما يلي إلى تنفيذ التابع removeAll ضمن الصنف MyArrayList:

    public boolean removeAll(Collection<?> collection) {
        boolean flag = true;
        for (Object obj: collection) {
            flag &= remove(obj);
        }
        return flag;
    }

يستدعِي التابع removeAll في كلّ تكرارٍ ضمن الحلقة التابعَ remove الذي يستغرِق زمنًا خطّيًّا. قد يدفعك ذلك إلى الظن بأنّ التابعَ removeAll تربيعي، ولكن ليس بالضرورة أن يكون كذلك.

يُنفِّذ التابع removeAll الحلقة مرةً واحدةً لكل عنصر في المتغير collection. فإذا كان المتغير يحتوي على عدد m من العناصر، وكانت القائمة التي نحذِف منها العنصر مكوَّنةً من عدد n من العناصر، فإن هذا التابع ينتمي إلى المجموعة O(nm)‎. لو افترضنا أن حجم collection ثابت، فسيكون التابع removeAll خطيًا بالنسبة لـ n، ولكن إذا كان حجم collection متناسبًا مع n، فسيكون التابع removeAll تربيعيًا. على سبيل المثال، إذا كان collection يحتوي دائمًا على 100 عنصر أو أقل، فإن التابع removeAll يستغرِق زمنًا خطيًا؛ أما إذا كان collection يحتوي في العموم على 1% من عناصر القائمة، فإن التابع removeAll يستغرِق زمنًا تربيعيًا.

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

هياكل البيانات المترابطة linked data structures

سنقدم في التمرين التالي تنفيذًا جزئيًا للواجهة List. يَستخدِم هذا التنفيذ قائمةً متصلةً linked list لتخزين العناصر.

يُعدّ هيكل البيانات مترابطًا إذا كان مُؤلفًا من كائنات يُطلَق عليها عادةً اسم عُقد nodes، حيث تحتوي العقد على مراجع references تشير إلى عقد أخرى. وفي القوائم المترابطة، تحتوي كل عقدة على مرجع إلى العقدة التالية في القائمة. قد تحتوي العقد في أنواعٍ أخرى من هياكل البيانات المترابطة على مراجع تشير إلى عدة عقد، مثل الأشجار trees والشُعب graphs.

تعرض الشيفرة التالية تنفيذًا بسيطًا لصنف عقدة:

public class ListNode {

    public Object data;
    public ListNode next;

    public ListNode() {
        this.data = null;
        this.next = null;
    }

    public ListNode(Object data) {
        this.data = data;
        this.next = null;
    }

    public ListNode(Object data, ListNode next) {
        this.data = data;
        this.next = next;
    }

    public String toString() {
        return "ListNode(" + data.toString() + ")";
    }
}

يتضمَّن الصنف ListNode متغيري نسخة هما: data وnext. يحتوي data على مرجعٍ يشير إلى كائن ما من النوع Object، بينما يحتوي next على مرجع يشير إلى العقدة التالية في القائمة. ويحتوي next في العقدة الأخيرة من القائمة على القيمة الفارغة null كما هو متعارف عليه.

يُعرِّف الصنف ListNode مجموعةً من البواني constructors التي تُمكِّنك من تمرير قيمٍ مبدئيةٍ للمتغيرين data وnext، أو تمكّنك من مجرد تهيئتهما إلى القيمة الافتراضية null. ويُمكِنك أن تُفكِر في عقدةٍ واحدةٍ من النوع ListNode كما لو أنها قائمةٌ مُكوَّنةٌ من عنصرٍ واحدٍ، ولكن على العموم، يُمكِن لأي قائمة أن تحتوي على أي عدد من العقد.

هناك الكثير من الطرق المستخدمة لإنشاء قائمة جديدة، وتتكوَّن إحداها من إنشاء مجموعة من كائنات الصنف ListNode على النحو التالي:

        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(3);

ثم ربطها ببعض:

        node1.next = node2;
        node2.next = node3;
        node3.next = null;

وهناك طريقة أخرى هي أن تُنشِئ عقدةً وتربطها في نفس الوقت. على سبيل المثال، إذا أردت أن تضيف عقدةً جديدةً إلى بداية قائمة، يُمكِنك كتابة ما يلي:

        ListNode node0 = new ListNode(0، node1);

والآن، بعد تنفيذ سلسلة التعليمات السابقة، أصبح لدينا أربعةُ عقدٍ تحتوي على الأعداد الصحيحة 0 و1 و2 و3 مثل بيانات، ومربوطةٌ معًا بترتيب تصاعدي. لاحِظ أن قيمة next في العقدة الأخيرة تحتوي على القيمة الفارغة null.

الرسمة التوضيحية السابقة هي رسم بيانيٌّ لكائنٍ يُوضِّح المتغيرات والكائنات التي تشير إليها تلك المتغيرات. تَظهَر المتغيرات بهيئة أسماءٍ داخل صناديقَ مع أسهمٍ تُوضِّح ما تشير إليه المتغيرات، بينما تَظهَر الكائنات بهيئة صناديق تَجِد خارجها النوع الذي تنتمي إليه (مثل ListNode وInteger)، وداخلها متغيرات النسخ المُعرَّفة بها.

تمرين 3

ستجد ملفات الشيفرة المطلوبة لهذا التمرين في مستودع الكتاب.

• MyLinkedList.java: يحتوي على تنفيذ جزئي للواجهة List، ويَستخدِم قائمةً مترابطةً لتخزين العناصر.
• MyLinkedListTest.java: يحتوي على اختبارات JUnit للصنف MyLinkedList.

نفِّذ الأمر ant MyArrayList لتشغيل MyArrayList.java الذي يحتوي على عدة اختبارات بسيطة.

ثم نفِّذ ant MyArrayListTest لتشغيل اختبارات JUnit التي سيفشل البعض منها. إذا نظرت إلى الشيفرة، ستجد ثلاثة تعليقات TODO للإشارة إلى التوابع التي ينبغي عليك إكمالها.

لننظر إلى بعض أجزاء الشيفرة قبل أن تبدأ. انظر إلى المتغيرات والبواني المُعرَّفة في الصنف MyLinkedList:

public class MyLinkedList<E> implements List<E> {

    private int size;            // احتفظ بعدد العناصر
    private Node head;           // مرجع إلى العقدة الأولى

    public MyLinkedList() {
        head = null;
        size = 0;
    }
}

يحتفظ المتغير size -كما يُوضِّح التعليق- بعدد العناصر التي يَحمِلها كائن من النوع MyLinkedList، بينما يشير المتغير head إلى العقدة الأولى في القائمة أو يحمل القيمة الفارغة null إذا كانت القائمة فارغة.

ليس من الضروري تخزين عدد العناصر. ولا يُعدّ الاحتفاظ بمعلوماتٍ إضافية في العموم أمرًا جيدًا؛ والسبب هو أن المعلومات الإضافية تحمّلنا عبء التحديث المستمر لها، ما قد يتسبَّب في وقوع أخطاء، كما أنها تحتل حيزًا إضافيًا من الذاكرة.

لكننا لو خزَّنا size صراحةً، فإننا سنتمكَّن من كتابة تنفيذٍ للتابع size، بحيث يَستغرِق تنفيذه زمنًا ثابتًا؛ أما لو لم نفعل ذلك، فسنضطرّ إلى المرور عبر القائمة وعدّ عناصرها في كل مرة، وهذا يتطلَّب زمنًا خطيًا.

من جهة أخرى، نظرًا لأننا نُخزِّن size صراحةً، فإننا سنضطرّ إلى تحديثه في كل مرة نضيف فيها عنصرًا إلى القائمة أو نحذفه منها. يؤدي ذلك إلى إبطاء تلك التوابع نوعًا ما، ولكنه لن يُؤثر على ترتيب النمو الخاص بها، ولذلك فلربما الأمر يستحق.

يضبُط الباني قيمة head إلى null، مما يشير إلى كون القائمة فارغة، كما يضبُط size إلى صفر، ويَستخدِم هذا الصنف معامل نوع type parameter اسمه E لتخصيص نوع العناصر. ويَظهَر معامل النوع أيضًا بتعريف الصنف Node المُضمَّن داخل الصنف MyLinkedList. انظر تعريفه:

    private class Node {
        public E data;
        public Node next;

        public Node(E data, Node next) {
            this.data = data;
            this.next = next;
        }
    }

أضف إلى هذا أن الصنف Node مشابهٌ تمامًا للصنف ListNode في الأعلى.

والآن، انظر إلى تنفيذ التابع add:

    public boolean add(E element) {
        if (head == null) {
            head = new Node(element);
        } else {
            Node node = head;
            // نفذ الحلقة حتى تصل إلى العقدة الأخيرة
            for ( ; node.next != null; node = node.next) {}
            node.next = new Node(element);
        }
        size++;
        return true;
    }

يُوضِّح هذا المثال نمطين ستحتاج لمعرفتهما لإكمال حل التمرين:

1. في كثير من التوابع، عادةً ما نضطرّ إلى معالجة أول عنصرٍ في القائمة بطريقةٍ خاصة. وفي هذا المثال، إذا كنا نضيف العنصر الأول الى القائمة، فعلينا أن نُعدِّل قيمة head، أما في الحالات الأخرى، فعلينا أن نجتاز القائمة، حتى نصل إلى نهايتها، ثم نضيف العقدة الجديدة.
2. يُبيّن ذلك التابع طريقة استخدام حلقة التكرار for من أجل اجتياز العقد الموجودة في القائمة. في مثالنا هذا لدينا حلقة واحدة. ولكن في الواقع قد تحتاج إلى كتابة نسخٍ عديدةٍ من تلك الحلقة ضمن الحلول الخاصة بك. من جهة أخرى، لاحِظ كيف صرّحنا عن node قبل بداية الحلقة؛ والهدف من ذلك هو أن نتمكَّن من استرجاعها بعد انتهاء الحلقة.

والآن حان دورك، أكمل متن التابع indexOf. ويجب أن تقرأ توثيق List indexOf لكي تعرف ما ينبغي عليك القيام به. انتبه تحديدًا للطريقة التي يُفترَض له معالجة القيمة الفارغة null بها.

كما هو الحال في تمرين مقالة تحليل الخوارزميات، وفَّرنا التابع المساعد equals للموازنة بين قيمة عنصرٍ ضمن المصفوفة وبين قيمةٍ معينةٍ أخرى، وفَحْص ما إذا كانت القيمتان متساويتين. يُعالِج التابع القيمة الفارغة معالجةً سليمة. لاحِظ أن التابع مُعرَّفٌ باستخدام المُعدِّل private؛ لأنه ليس جزءًا من الواجهة List، ويُستخدَم فقط داخل الصنف.

شغِّل الاختبارات مرةً أخرى عندما تنتهي. ينبغي أن ينجح الاختبار testIndexOf وكذلك الاختبارات الأخرى التي تعتمد عليه.

والآن، عليك أن تكمل نسخة التابع add ذات المعاملين. تَستقبِل تلك النسخة فهرسًا وتُخزِّن القيمة الجديدة في الفهرس المُمرَّر. وبالمثل، اقرأ أولًا التوثيق List add ثم نفِّذ التابع، وأخيرًا، شغِّل الاختبارات لكي تتأكّد من أنك نفّذتها بشكل سليم.

لننتقل الآن إلى التابع الأخير: أكمل متن التابع remove. اقرأ توثيق التابع List remove. بعدما تنتهي من إكمال هذا التابع، ينبغي أن تنجح جميع الاختبارات.

بعد أن تُنهِي جميع التوابع وتتأكَّد من أنها تَعمَل بكفاءة، يُمكِنك مقابتها مع النسخ المتاحة في مجلد solution في مستودع الكتاب ThinkDataStructures على GitHub.

ملحوظة متعلقة بكنس المهملات garbage collection

تنمو المصفوفة في الصنف MyArrayList -من التمرين المشار إليه- عند الضرورة، ولكنها لا تتقلص أبدًا، وبالتالي لا تُكنَس المصفوفة ولا يُكنَس أي من عناصرها حتى يحين موعد تدمير القائمة ذاتها. في المقابل، تتقلص القائمة المترابطة عند حذف العناصر منها، كما تُكنَس العقد غير المُستخدَمة مباشرةً، وهو ما يُمثِل واحدةً من مميزات هذا النوع من هياكل البيانات.

انظر إلى تنفيذ التابع clear:

    public void clear() {
        head = null;
        size = 0;
    }

عندما نضبُط قيمة الرأس head بالقيمة null، فإننا نحذف المرجع إلى العقدة الأولى. إذا لم تكن هناك أي مراجع أخرى إلى ذلك الكائن (من المفترض ألا يكون هناك أي مراجع أخرى)، فسيُكنَس الكائن مباشرةً. في تلك اللحظة، سيُحذَف المرجع إلى الكائن المُمثِل للعقدة الثانية، وبالتالي يُكنَس بدوره أيَضًا. وستستمر تلك العملية إلى أن تُكنَس جميع العقد.

بناءً على ما سبق، ما هو تصنيف التابع clear؟ يتضمَّن التابع عمليتين ثابتتي الزمن، ويبدو لهذا كما لو أنه يستغرِق زمنًا ثابتًا، ولكنك عندما تستدعيه ستُحفزّ كانس المهملات على إجراء عملية تتناسب مع عدد العناصر، ولذلك ربما علينا أن نَعُدّه خطّيَّ الزمن.

يُعدّ هذا مثالًا على ما نُسميه أحيانًا بـمشكلة برمجية في الأداء، أي أن البرنامج يفعل الشيء الصحيح، ولكنه لا ينتمي إلى ترتيب النمو المُتوقَّع. يَصعُب العثور على هذا النوع من الأخطاء خاصةً في اللغات التي تُنفِّذ أعمالًا كثيرةً وراء الكواليس مثل عملية كنس المهملات مثلاً، وتُعدّ لغة جافا واحدةً من تلك اللغات.

ترجمة -بتصرّف- للفصل Chapter 3: ArrayList من كتاب Think Data Structures: Algorithms and Information Retrieval in Java.

اقرأ أيضًا

• المقال التالي: تحليل زمن تشغيل القوائم المنفذة باستخدام قائمة مترابطة
• المقال السابق: مدخل إلى تحليل الخوارزميات
• تحليل زمن تشغيل القوائم المنفذة باستخدام قائمة ازدواجية الترابط
• تحليل زمن تشغيل القوائم المنفذة باستخدام قائمة مترابطة