» נושאי לימוד
» נושאי לימוד
יום חמישי 5 בדצמבר 2024
שיטות חיפוש 1
דף ראשי  קובץ סדרתי  שיטות חיפוש 1 גרסה להדפסה

TF זמן הבאת רשומה כלשהי.

בקובץ סדרתי A (קובץ ממוין) יש 4 שיטות חיפוש אפשריות:

 

1. חיפוש טורי(Serial search)  – גוש אחר גוש, דורש מעבר על חצי קובץ בממוצע כדי למצוא רשומה:

קיבלנו ש TF  של A שווה ל Tשל ערימה TA F  = TP F 

וזה גרוע, אבל לא הגיוני להשתמש בחיפוש טורי בקובץ סדרתי ממוין,

לכן נפנה לשיטת החיפוש הבאה. 

 

2. חיפוש בינארי    (Binary searc  (h

חיפוש לפי מפתח ראשי על גושי/רשומות הקובץ כדי להגיע למקום הרשומה המבוקשת. ניגשים לאמצע הקובץ בודקים אם הרשומה המבוקשת נמצאת שם,

אם לא שואלים האם הרשומה נמצאת בחצי העליון או בחצי התחתון של הקובץ ואל החצי המתאים ניגשים ושוב מחלקים אותו ל- 2 וכך הלאה עד למציאת או אי-מציאת הרשומה הרצויה.

 

 

כל גישה היא גישה לגוש בודד, לכן העלות של TF היא log2  של מס' הגושים בקובץ

(b) כפול זמן הזזת זרוע (s + r) + זמן קריאת הגוש (btt) + זמן עיבוד לרשומה (c).

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

אי אפשר לדעת את מען הגוש הבא לקריאה עד לסיום הבדיקה/חישוב  cמיהו הגוש הבא שצריך לגשת אליו להמשך החיפוש.

 

 30-11-03 / 20:30  עודכן ,  18-11-03 / 00:00  נוצר ע"י רועי לוי  בתאריך 
 המשך מדדים להערכת קובץ סידרתי - הקודםהבא - שיטות חיפוש 2 
תגובות הקוראים    תגובות  -  0
דרכונט
מהי מערכת הדרכונט?
אינך מחובר, להתחברות:
דוא"ל
ססמא
נושאי לימוד
חיפוש  |  לא פועל
משלנו  |  לא פועל
גולשים מקוונים: 4