שאלה על אלגוריתמים

[omni4]

שאלה על אלגוריתמים

יש לי מטריצה בגודל NxM, לא ממויינת. אני רוצה למצוא באיזה שורה ועמודה נמצא ערך k של המטריצה, בלי למיין אותה, יש משהו כזה, משהו בסגנון select מטריציוני? (אני חשבתי לעשות כך: להפוך את המטריצה למערך אחד ענק של שורה אחת ואז לעשות select).

 

[avinamal]

השאלה שלך לא ברורה. מטריצה היא כבר מערך.

 

[omni4]

ניסוח חדש

יש לי מערך דו-מימדי בגודל NxM, לא ממויין. אני רוצה למצוא באיזה שורה ועמודה נמצא ערך k של המטריצה, בלי למיין אותו. האם יש משהו כזה, משהו בסגנון select של מערך דו-מימדי? (אני חשבתי לעשות כך: להפוך את המערך הדו-מימדי למערך חד-מימדי אחד ענק ואז לעשות select).

 

[1ca1]

מה זה יעזור?

תצטרך לחלק את המימדים בצורה מסויימת בשביל לדעת באיזה שורה ועמודה. (אין כזה דבר בשם select חוץ מDBים למיניהם, אתה בסה"כ עושה חיפוש סדרתי (אם הוקטור לא ממויין)). מאחר שגודל המערך יהיה בדיוק mn, וחיפוש סדרתי עליו לוקח mn פעולות בworst-case זה בדיוק שקול על לרוץ על כל השורות, ואז לכל שורוה, לרוץ על כל העמודות (בעצם מעבר פשוט על המטריצה) ולחפש את הערך k. אם המטריצה שלך ממויינת בצורה כזאת או אחרת (למשל הרבה פעמים נהוג שכל דבר שעבור מספר ספציפי אז הוא קטן/גדול מכל המספרים "מעליו" ומ"אחוריו").

 

[omni4]

לידיעתך, זה לא אותו

select שאתה חושב, תסתכל בקישור: http://www.cs.biu.ac.il/~89-220/files/kth%20element.ppt#258,1,מציאת האיבר ה-k בקוטנו (בגודלו) האלגוריתם הוא למציאת ערך k הכי קטן במערך לא ממויין, זה שאתה לא מכיר משהו לא אומר שהוא לא קיים. אם אין לך תשובה עיניינית, אז בבקשה אל תכתוב.

 

[vinney]

הוא צודק אבל

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

 

[1ca1]

אבל מה שאתה אומר זה שטויות

דבר ראשון השאלה שם מדברת על בעיה שונה לחלוטין (מציאת האיבר ה-k בקוטנו במערך), כאן יש לך בעיה שונה לחלוטין. בכל אופן, שים לב שבמטריצה, אם תעבור לוקטור, הn במצגת שלך יהפוך לmn... והאלגוריתם הזה לא טוב ,למה? גם האלגוריתם המשוכלל שהראית שם, דורש dn/cn (כאשר n הוא גודל הוקטור, עוד פעם אצלמו זה mn) בכל מקרה (ואף יותר, כי זו קריאה רקורסיבית), ולכן אם נסתכל בסיבוכיות אסימפטוטית, נקבל שהוא גדול או שווה לO מה גם השאלה שאתה שאלת דיברה על מציאת איבר כללי, איך אתה יכול לדעת האם הוא k בקוטנו? רק להתחיל למצוא את המינימלי, ואז את האחד לפני המינימלי וכך הלאה ותגיע לO(n^2) בworst case לגבי מה שויני אמר, תיאורטית אם מדובר במערך לא ממויין, אפשר אולי לתת היוריסטיקות (אם אתה יודע מאיזה היגיון פנימי מגיעים הנתונים וכו'), אבל באופן כללי, לנתונים רנדומליים לחלוטין, תמיד תוכל להגיע לworst-case scenerio.