רוטר - ברוח החידות/שאלות, עוד חידה מעניינת (שיכולה להיות גם

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

"ברוח החידות/שאלות, עוד חידה מעניינת (שיכולה להיות גם"

גירסת הדפסה

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

אשכול מספר 15763

ldan192
חבר מתאריך 14.9.08
95119 הודעות

16:18 13.03.10

ברוח החידות/שאלות, עוד חידה מעניינת (שיכולה להיות גם

ערכתי לאחרונה בתאריך 13.03.10 בשעה 16:22 בברכה, ldan192

שימושית מתישהו).
בהנתן מערך מאורך n של מספרים שלמים וחיוביים,
תנו אלגוריתם שבהינתן מספר k, מוצא שלושה אינדקסים s, t, u (שונים) עבורם A[s]+A[t]+A[u]=k - או מודיע שאין כאלה.
אני מכיר פתרון פשוט, יחסית, ב-(O(n^2 * logn.
אם תמצאו פתרון בסיבוכיות אפילו יותר טובה (סביר אבל שלא בהרבה) זה גם יהיה נחמד.

בהצלחה

בברכה,
עידן

שתף

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

האשכול	מחבר	תאריך כתיבה	מספר
טוב אז ככה	פאביו ג'וניור	13.03.10 17:12	1
גם n*log^2 n לא מורכב בהרבה :)	ldan192	13.03.10 17:16	2
חח זה פשוט ואפשר לפתור את זה בN בריבוע.	ronen333	13.03.10 18:01	3
הםםם, נראה לי שחסר לך עוד אינדקס :) בכל מקרה, יש גם ב-(O(n*log^2 n	ldan192	13.03.10 18:24	4
עידן אני מתפלא עליך	ronen333	13.03.10 21:58	6
נה, אני לא בא על חידות לא שימושיות, אני בא על דברים שבאמת פרקטיים ;)	ldan192	14.03.10 10:43	9
מה יש לי עם הא' היום :\|	ronen333	13.03.10 22:14	7
הפתרון של אביעד נכון.	Deuce	13.03.10 20:50	5
אני חושב שגם יש ב-nlogn :) וכן, פשוט אביעד השמיט פרטים מההתחלה	ldan192	14.03.10 10:43	8

פאביו ג'וניור

17:12 13.03.10

1. טוב אז ככה
בתגובה להודעה מספר 0

הO(n^2 * logn) דיי פשוט...
למיין... לרוץ על 2 אינדקסים ולחפש את השלישי בחיפוש בינארי פשוט...

עכשיו צריך לחשוב איזה דרך יותר יעילה יש לעשות את זה :P

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

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

ldan192
חבר מתאריך 14.9.08
95119 הודעות

17:16 13.03.10

2. גם n*log^2 n לא מורכב בהרבה :)
בתגובה להודעה מספר 1

בברכה,
עידן

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

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

ronen333
חבר מתאריך 20.2.03
6069 הודעות

18:01 13.03.10

3. חח זה פשוט ואפשר לפתור את זה בN בריבוע.
בתגובה להודעה מספר 0

קודם כל ממינים את המערך. (לא חשוב האמת עם איזה מיון כל עוד זה לא עובר סיבוך ריבועי)
לולאה פנימות-
2 אינדקסים I וJ.
I מצביע על התחלת המערך, J מצביע על סוף המערך. ביגלל שהמערך ממוין אפשר לדעת אם להעלות את הI או לא הוריד את הJ כדי לקבל את המספר K.
זה מתבצע בטטא של N.
ולולאה חיצונית שעוברת על N המספרים.

סיבוכיות זמן ריצה כוללת: N^2

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

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

ldan192
חבר מתאריך 14.9.08
95119 הודעות

18:24 13.03.10

4. הםםם, נראה לי שחסר לך עוד אינדקס :) בכל מקרה, יש גם ב-(O(n*log^2 n
בתגובה להודעה מספר 3

בברכה,
עידן

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

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

ronen333
חבר מתאריך 20.2.03
6069 הודעות

21:58 13.03.10

6. עידן אני מתפלא עליך
בתגובה להודעה מספר 4

ערכתי לאחרונה בתאריך 13.03.10 בשעה 22:08 בברכה, ronen333

קודם כל תסביר לי איך דבר כזה:

QuickSort(arr)
for(z=0;z<n;z++)
while(i<j)
{...}

מגיע לסיבוכיות של N^2 כפול LOGN.. הצעד הראשון שהוא מיון לוקח NLOGN בזמן הממוצע, לאחר מכן אתה מבצע לולאה חיצונית שמבצעת N איטרציות ולולאה פנימית שמבצעת גם כן N איטרציות.
זה
NLOGN+N^2
אם כבר.. והלוגריתם נהפך לזניח במקרה הגרוע ביותר ולכן זה N^2( כמו שאתה לא מתייחס לקבועים אתה גם לא מתייחס אילו)

הדבר השני שהפתעתי אותי זה עם החידה.. שראיתי את הכותר אמרתי לעצמי "אוו זה בטח יהיה מעניין, עידן הביא את זה" ומצטער לומר אבל איכזבת :P
אני מצפה שתביא משהו יותר מעניין פעם הבאה ;)

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

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

ldan192
חבר מתאריך 14.9.08
95119 הודעות

10:43 14.03.10

9. נה, אני לא בא על חידות לא שימושיות, אני בא על דברים שבאמת פרקטיים ;)
בתגובה להודעה מספר 6

בברכה,
עידן

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

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

ronen333
חבר מתאריך 20.2.03
6069 הודעות

22:14 13.03.10

7. מה יש לי עם הא' היום :|
בתגובה להודעה מספר 3

התכוונתי לרשום "או להוריד את הJ". בע.

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

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

Deuce
חבר מתאריך 1.9.08
6225 הודעות

20:50 13.03.10

5. הפתרון של אביעד נכון.
בתגובה להודעה מספר 0

למעשה קל לעשות רדוקציה לבעייה של למצוא 2 אינדקסים i,j כך ש-ai + aj = p. כדי לפתור את זה אפשר למיין את המערך (nlog n) ולמצוא (או להחליט שלא קיימים כאלה) בזמן ליניארי.
כעת נרוץ עם s על איברי המערך a[s] ועבור כל אחד כזה נחפש i, j כך ש-
a[i] + a[j] = (k - a[s])

זה עולה לנו n^2.
סה"כ n^2.

השאלה אם באמת יש טעם לרוץ על כל איברי as כנ"ל - נראה שכן.
בכל מקרה יהיה נחמד להוריד ל-nlog ^2 n. צריך לחשוב על זה.

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

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

ldan192
חבר מתאריך 14.9.08
95119 הודעות

10:43 14.03.10

8. אני חושב שגם יש ב-nlogn :) וכן, פשוט אביעד השמיט פרטים מההתחלה
בתגובה להודעה מספר 5

בברכה,
עידן

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

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