שאלה לגבי arrayList

[pantera]

יש לי שני רשימות של אינטג'ר שבכל תא קיים ספרה שביחד מדמות מספר שלם בגודל כלשהו למשל "123456789123456" אז בתא 0 יהיה 1 ובתא 1 יהיה 2.

נניח שיש לי שני רשימות כאלה בעלי אותה כמות של תאים (כמות ספרות) רציתי לדעת אם יש דרך קלה לדעת איזה רשימה מייצגת מספר גדול יותר או שחייב להשתמש בלולאה?

תודה.

[Gil28]

מה לא קל בלולאה?

[pantera]

כי זה יכול להיות מספרים ממש גדולים ולעבור בלולאה סיפרה סיפרה נראה לי איטי ולא יעיל אז חשבתי שאולי יש איזו פונקציה יעילה יותר.

[שניצל]

לעבור פעם אחת על איברים של רשימה (מה שנקרא סיבוכיות לינארית) זה פחות או יותר הדבר היעיל ביותר שאפשר לעשות עם הרשימה, אלא אם אתה יודע משהו על המבנה שלה (לדוגמה אם זו רשימה ממויינת, וגם אז זה לא תמיד עוזר, זה כבר תלוי בבעיה שאתה מנסה לפתור).

כמובן גם את המעבר היחיד הזה אפשר לעשות בצורות יעילות יותר או פחות, זה כבר תלוי בפתרון המדויק שלך.

[pantera]

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

כל רשימה כזאת יכולה להיות גם מספר שלילי (יש לה משתנה בוליאני שמצביע אם היא חיובית או שלילית) ולמשל בחיסור יש כמה מקרים אם למשל שניהם שליליים מה שהופך את החיסור לחיבור וכו

במקרה שאחד שלילי ואחד חיובי אין בעיה לדעת מי יותר גדול וגם במקרה שניהם בעלי אותו סימן וגודל רשימה שונה אז אפשר לדעת מי מספר יותר גדול. הבעיה היא כאשר הם בעלי אותו סימן ואותו גודל רשימה

אז לעשות לולאה זה באמת פתרון שנראה הכי טוב אבל במקרה קיצון רק הספרה האחרונה תהיה שונה ואז זה "איטי"(כי מדובר במספרים אינסופיים כביכול) אבל אם אין דרך אחרת זה מה שאני אעשה.

תודה.

[borsood]

תשתמש ב size, אבל לא מובטח לך שהפומנקציה לא עושה לולאה בעצמה.

[Gil28]

גם אם הרשימות שלך בגודל כמה עשרות אלפים, זה בכלל לא נורא.

[Milford Cubicle]

יש לי שני רשימות של אינטג'ר שבכל תא קיים ספרה שביחד מדמות מספר שלם בגודל כלשהו למשל "123456789123456" אז בתא 0 יהיה 1 ובתא 1 יהיה 2.

נניח שיש לי שני רשימות כאלה בעלי אותה כמות של תאים (כמות ספרות) רציתי לדעת אם יש דרך קלה לדעת איזה רשימה מייצגת מספר גדול יותר או שחייב להשתמש בלולאה?

תודה.

לא הבנתי מה הסיבוכיות הגדולה בלולאה.

לפי תיאור המצב שלך - אתה בכלל לא צריך לעבור על הרשימה! רק על התא הראשון. מי שגבוה יותר = מייצג מספר גבוה יותר. רק אם הם זהים אז אתה בודק את התא הבא וכן הלאה.

[pantera]

לא הבנתי מה הסיבוכיות הגדולה בלולאה.

לפי תיאור המצב שלך - אתה בכלל לא צריך לעבור על הרשימה! רק על התא הראשון. מי שגבוה יותר = מייצג מספר גבוה יותר. רק אם הם זהים אז אתה בודק את התא הבא וכן הלאה.

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

עשיתי בסוף לולאה שעושה את זה אבל חשבתי שאולי יש דרך אחרת, בכל אופן הסיבוכיות לא חשובה לתרגיל אז זה לא משנה.

תודה.

[QttP]

יכולות להיות מיליון דרכים אחרות, אבל קל לראות שבמקרה הגרוע הן לא יכולות להיות יותר טובות מזמן ריצה של N. כי במקרה הגרוע המספרים זהים עד כדי ספרה אחת, ואז בכל מקרה צריך לראת את כל הספרות כדי להחליט.