שאלת הציקליק

נכתוב פעולת עזר המקבלת רשימה ומיקום (המיקומים מתחילים ב-1) ומחזירה את החולייה במיקום התואם.

JAVA

public static Node<Integer> getNodeByPosition(Node<Integer> lst, int position)

{

        Node<Integer> p = lst;

for(int i=0; i<position-1; i++)

        p=p.getNext();

return p;

}

פעולת עזר שבעזרתה נדע מה האורך של הרשימה המקושרת.

C#

public static int Size(Node<Integer> lst)

{

        int counter=0;

        Node<Integer> p = lst;

while(p!=null)

{

        counter++;

        p=p.getNext();

}

return counter;

}

הפתרון בשפת java:

public static boolean isCyclic(Node<Integer> lst)

{

        int size = size(lst);

        Node<Integer> p = lst;

        int jump = p.getValue();

        for(int i=0; i<size; i++)

        {

                p = getNodeByPosition(lst , jump);

                if( p ==lst)

                        return false;

                jump = p.getValue();

        }

return p==lst;

}

סעיף ב'

מהי הסיבוכיות?

על מנת להסביר על הסיבוכיות יש תחילה להסביר על פונקציות העזר שבהן נעשה שימוש.

פונקציית size:

על מנת לחשב את גודלה של הרשימה המקושרת, היינו צריכים לעבור על כל האיברים בה. נניח כי אורך השרשרת הוא n, לכן הסיבוכיות היא O(n

פונקציית getNodeByPosition:

במקרה הכי גרוע נתבקש לקבל את החולייה הרחוקה ביותר (נניח והתחלנו בהתחלה), לכן נצטרך לעבור על n איברים. (נניח ש-n הוא גדולו של השרשרת).

הפונקציה העיקרית:

תחילה יש שימוש בפונקציית size, שהיא O(n)  כאשר n הוא גודלה של השרשרת.

לאחר מכן יש לולאת for המתבצעת n פעמים ובתוכה קריאה לפונקצייה getNodeByPosition המתבצעת o(n). לכן סה"כ הסיבוכיות היא O(n^2.