|
|
לא ת 1 כל ם ~ ל ;; ךד ~ :: ) םידכר ז ( 22 , והמלאכה רא-ליים ~ זכ ' ~ דלא ' ~~ ל : ~~ ' )! רא ( ו 3 ' , בפרק הקודם ראינו שלבעיות אלגוריתמיות מסוימות יש פתרונות שהם מהירים הרבה יותר מאשר מקביליהם הנאיביים . ראינו , למשל , שניתן לחפש איבר ברשימה ממוינת בזמן לוגריתמי , ומכאן שלצורך חיפוש שם בספר טלפונים המכיל מיליון רשומות די לנו , במקרה הגרוע ביותר ב-20 , השוואות בלבד במקום מיליון . באותה רוח , ניתו למיין ספר טלפונים לא ממוין המכיל מיליון רשומות בעזרת כמה מיליוני השוואות בלבד , במקום מיליארדים רבים , שכן קיים אלגוריתם מיון שזמן ריצתן O ( Nx l ogN ) העולה בביצועיו על אלגוריתמים שזמן ריצתם ריבןעי . ייתכן שאינך מתרשם מכך במיוחד . אתה עשוי לטעון שהנך די ייעשיריי כדי להרשות לעצמך מיליון השוואות לצורך חיפוש ברשימה . אתה עשוי לטעון גם שכמה שניות נוספות של זמן מחשב אינו משנות , ולכן חיפןש סדרתי טןב לא פחןת מאשר חיפוש בינרי . טיעןן זה מקבל משנה תוקף ברגע שאנו מגלים שעל המחשב , ולא על המשתמש האנושי , לבצע את אותה מטלה משעממת וחסרת השראה - דפדוף ברשימת כל השמות שבספר . טיעון דומה תופס גם לגבי מיון ,...
To the book |
|
|