שאלה 1ד מבחן סמסטר ג 2009

מנהל: TA_Isana

שאלה 1ד מבחן סמסטר ג 2009

הודעהעל ידי zoran » 18:31 18/06/2010

נתון מערך בן n מספרים שלמים. ידוע שהוא מכיל את הערך 10 k פעמים. ידוע גם שכל ה10-ים מרוכזים בסוף המערך. האם ניתן לחשב את k
ב(O(logk? ענה בכן ולא
אין תשובה בפתרון שניתן. האם זה כן או לא?
zoran
 
הודעות: 30
הצטרף: 21:18 10/11/2009

Re: שאלה 1ד מבחן סמסטר ג 2009

הודעהעל ידי TA_Yakim » 21:17 20/06/2010

כן
קודם כל נמצא באיזה תחום לחפש
קוד: בחר הכל
i=0
len=A.length
while(A[len-2^i]=10){
                                i=i+1
}   // now 2^i >= k >= 2^(i-1)

הלולאה בזמן הדרוש ועכשיו נותר רק לחפש במערך בגודל 2k מה שגם עומד בזמן הדרוש
TA_Yakim
 
הודעות: 53
הצטרף: 18:54 03/06/2010


חזור אל - מבני נתונים 2010

מי מחובר

משתמשים הגולשים בפורום זה: אין משתמשים רשומים ו 2 אורחים