עבור לתוכן

שאלה לגבי arrayList

Featured Replies

פורסם

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

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

תודה.

פורסם
  • מחבר

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

פורסם

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

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

פורסם
  • מחבר

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

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

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

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

תודה.

פורסם

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

פורסם

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

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

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

תודה.

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

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

פורסם
  • מחבר
לא הבנתי מה הסיבוכיות הגדולה בלולאה.

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

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

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

תודה.

פורסם

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

ארכיון

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

דיונים חדשים