רוטר - שאלה בJAVA - ''סיבוכיות''

יומן פעילות	לוח שנה	מבזקי חדשות	תקנון	RSS	כותרות	כותרות לפי תגובה	ניקוי קוקיז	IP	להורדת אפליקציה
eBay	AliExpress	GearBest	Amazon	Booking	Kiwi	SkyScanner	Trip Advisor

"שאלה בJAVA - ''סיבוכיות''"

גירסת הדפסה

קבוצות דיון פיתוח, תיכנות ובניית אתרים נושא #21083	מנהל סגן המנהל מפקח Winner צל"ש מומחה

אשכול מספר 21083

Mirage
חבר מתאריך 18.12.11
5193 הודעות

16:46 17.01.15

שאלה בJAVA - ''סיבוכיות''

נניח נתון מערך של מספרים 0 או 1 מפוזרים באופן אקראי,
וצריך לחשב מרחק בין שני אפסים, ככה שלכל אחד נשנה ערך לפי מרחק הקטן ביותר שמתחיל מ-0 עד ל0 הראשון שאחריו.
לדוגמא:
נתון ציר מספרים - 01101110011
והתוצאה צריכה להיות כזאת: 01101210012
איך אפשר לבצע את זה בסיבוכיות הנמוכה ביותר בשימוש של לולאה אחת בלבד?

איך הייתם עושים את זה?

שתף

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

האשכול	מחבר	תאריך כתיבה	מספר
לא הבנתי את הדוגמא	Frank	17.01.15 16:51	1
הסבר	Mirage	17.01.15 17:00	2
אה עכשיו הבנתי	Frank	17.01.15 17:04	3
קודם כל תודה על העזרה	Mirage	17.01.15 17:19	5
עם 3 לולאות, 3 מערכי עזר - O(n)	U F O	17.01.15 17:17	4
בדיוק	Net_Boy	17.01.15 17:19	6
אפשר הסבר על הלולאה השלישית?	Mirage	17.01.15 17:24	7
דוגמא	U F O	17.01.15 17:26	8
מצוין הבנתי! תודה רבה רבה לך!	Mirage	17.01.15 17:34	9
מעולה, בהצלחה.	Frank	17.01.15 17:35	11
אפשר עם לולאה אחת וסיבוכיות מקום קבועה.	Frank	17.01.15 17:34	10
תן מבט פה:	meni181818	17.01.15 19:51	12

Frank
חבר מתאריך 1.2.03
18265 הודעות

16:51 17.01.15

1. לא הבנתי את הדוגמא
בתגובה להודעה מספר 0

למה שמת 2 איפה ששמת 2?

ומה הקשר ל-java?

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

Mirage
חבר מתאריך 18.12.11
5193 הודעות

17:00 17.01.15

2. הסבר
בתגובה להודעה מספר 1

1)
קשה לי קצת להסביר יותר מפורט מזה, לכן שמתי את הדוגמאות של המערכים, של נתון ושל התוצאה.
דוגמא נוספת למערכים:
0011111011110111
0012321012210123
כל מס' שאינו 0, יקבל ערך של המרחק שלו מה-0 הקרוב אליו.
2)כי הפיתוח מתבצע בJAVA אז אם מישהו ירצה לפרט בקוד מסוים אז שידע

@Frank@

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

Frank
חבר מתאריך 1.2.03
18265 הודעות

17:04 17.01.15

3. אה עכשיו הבנתי
בתגובה להודעה מספר 2

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

@Mirage@

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

Mirage
חבר מתאריך 18.12.11
5193 הודעות

17:19 17.01.15

5. קודם כל תודה על העזרה
בתגובה להודעה מספר 3

נניח ואני משתמש ב2 לולאות , כאשר אחת יושבת בתוך השנייה,
הסיבוכיות שלי יוצאת (O(n^2.
איך אפשר לגשת לבעיה הזאת, על מנת לבצע את זה בסיבוכיות הנמוכה ביותר?
יש לך אולי איזה רעיון?

@Frank@

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

U F O

חבר מתאריך 1.7.02
3594 הודעות, 2 פידבק

17:17 17.01.15

4. עם 3 לולאות, 3 מערכי עזר - O(n)
בתגובה להודעה מספר 0

לולאה 1 + מערך 1:
מחזיק את המרחק הכי קצר בין 1 ל0 כאשר תמיד לוקחים את ה0 הכי שמאלי

לולאה 2 + מערך 2:
מחזיק את המרחק הכי קצר בין 1 ל0 כאשר תמיד לוקחים את ה0 הכי ימיני
לולאה 3 + מערך 3 (פתרון):
לוקחים את המינימום מכל תא

סהכ
O(3n) = O(n)

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

Net_Boy

חבר מתאריך 1.4.02
17151 הודעות, 1 פידבק

17:19 17.01.15

6. בדיוק
בתגובה להודעה מספר 4

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

Mirage
חבר מתאריך 18.12.11
5193 הודעות

17:24 17.01.15

7. אפשר הסבר על הלולאה השלישית?
בתגובה להודעה מספר 4

מה הכוונה "מינמוום בכל תא"?
@U F O@

תודה רבה.

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

U F O

חבר מתאריך 1.7.02
3594 הודעות, 2 פידבק

17:26 17.01.15

8. דוגמא
בתגובה להודעה מספר 7

מערך 1: 1 2 495495 3 0 3
מערך 2: 0 3 999999 2 4 0
מערך 3: 0 2 495495 2 0 0

אתה לוקח מכל תא את הכי קטן

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

Mirage
חבר מתאריך 18.12.11
5193 הודעות

17:34 17.01.15

9. מצוין הבנתי! תודה רבה רבה לך!
בתגובה להודעה מספר 8

ולשאר העוזרים

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

Frank
חבר מתאריך 1.2.03
18265 הודעות

17:35 17.01.15

11. מעולה, בהצלחה.
בתגובה להודעה מספר 9

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

Frank
חבר מתאריך 1.2.03
18265 הודעות

17:34 17.01.15

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

ואותה לוגיקה כמו שכתבת.

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

meni181818

חבר מתאריך 12.12.13
1032 הודעות, 1 פידבק

19:51 17.01.15

12. תן מבט פה:
בתגובה להודעה מספר 0

http://jsfiddle.net/66z0y4tc/4

http://s28.postimg.org/izm7890yz/image.gif

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד