חידה

[melafefon11]

../images/Emo124.gifחידה../images/Emo110.gif

נתון מערך A של עצמים כלשהם. הפעולה היחידה שניתן לבצע על המערך היא לשאול האם [A = A[j עבור j,i כלשהם. המטרה היא להכריע האם במערך יש לפחות חצי עצמים זהים. סיבוכיות מבוקשת -(( O(N*Log(N 10x...

 

[ron369]

מאיפה זה?

למזלי, אני מכיר את הטריק. אם נחלק את המערך ל-m תת-קבוצות זרות ומשלימות בגודל k (כאשר k=n/m), נגיע ללמה שימושית. בחצי מסך כל הקבוצות (m/2), האיבר הנדרש יהיה במחצית מהתאים (k/2). קל להוכיח זאת לפי עקרון שובך היונים. סיבוכיות מתקבלת: O)NlgN(, עם אלגוריתם מתאים. אגב, זו חידה לא קלה בכלל - לפחות לפי דעתי.

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

 

[melafefon11]

אתה יכול להרחיב לגבי M ו K?

 

[ron369]

לכל M או לכל K (כך ש N=KM)

(אם אני לא טועה)

 

[ron369]

אגב,שים לב כמה קל לבנות פה

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

 

[עריסטו]

רמז

V הוא מערך המכיל n מספרים. האיברים במערך הם V_1, V_2, ..., V_n. ידוע שקיים מספר המופיע במערך יותר מ - n/2 פעמים. האלגוריתם הבא מדפיס את המספר הזה. ניתן לבסס עליו אלגוריתם שיפתור את החידה.

R = V_1 i = 2 j = 3 WHILE j <= n DO IF i = j THEN R = V_i IF V_i = R THEN j = j + 2 i = i + 1 END_WHILE PRINT R​

 

[ron369]

מה הסיבוכיות?

(אני פשוט רוצה לדעת אם אפשר לעשות את זה בדרך טובה יותר משלי)