יש לי שאלה ביעילות על רשימה מקושרת, פתרתי אותה אבל הייתי שמח לפידבק האם הפיתרון שלי נכון

נתונות המחלקות הבאות:

public class IntNode {private int _value;
private IntNode _next;
public IntNode(int val, IntNode n) {
_value = val;
_next = n;
}
public int getValue() {
return _value;
}
public IntNode getNext() {
return _next;
}
public void setValue(int v) {
_value = v;
}
public void setNext(IntNode node) {
_next = node;
}
}

public class TwoIntLists {
private IntNode _listA, _listB;
public TwoIntLists (IntNode first, IntNode second) {
_listA = first;
_listB = second;
}
}

public class IntList {
private IntNode _head;
public IntList( ) {
_head = null;
}
public IntList (IntNode node) {
_head = node;
}
. . . // methods
}

עליכם להוסיף שיטה בשם split למחלקה IntList

השיטה מחלקת את איברי הרשימה עליה היא פועלת לשתי רשימות B - ו A, כל אחת באורך n/2

כך שההפרש בין סכום אברי A לסכום אברי B יהיה מקסימאלי. השיטה צריכה להחזיר אובייקט מהמחלקה TwoIntLists המכיל בשדותיו את ראשי הרשימות של A ושל B.

השיטה שתכתבו צריכה להיות יעילה ככל הניתן.

כתבו מה סיבוכיות הזמן וסיבוכיות המקום של השיטה שכתבתם.

מה שחשבתי לעשות זה למיין את הרשימה ע"י merge sort - עולה nlogn

למצוא את אורך הרשימה - עולה n

לחתוך את הרשימה ל-2 ואם יש עודף הוא יהיה בקבוצה A.

בסה"כ סיבוכיות זמן של nlogn וסיבוכיות מקום של 1

נשמע סבבה. בעקרון יש פתרון ב-(O(n אבל אני בספק אם למדת את הכלים בשבילו.

האש table ?

nop

http://www.cs.technion.ac.il/~bshouty/DS/Lecc10-WWW/Lec10.pdf

אבל n זה במקרה הכי טוב לא ?

ממוצע זה יצא יותר

התכוונתי לאלגוריתם שבשקופיות 7-8.

לא למדנו

אני יודע, בד"כ לומדים את זה רק בקורס באוניברסיטה.

אני לומד באוניברסיטה אבל אני בקורס מבוא

סביר שתלמד את זה בקורס במבני נתונים.