 |
|
 |
||
|
||||
 |
זה אלגוריתם שמוכן לקבל כל קלט שהוא? אז אי אפשר לחזות כמה זמן ידרש לו לפתור בעיה. או אולי זה אלגוריתם שמקבל כל קלט כאילו זה הפיתרון? אז זמן הריצה שלו הוא זמן קליטת הקלט. יכול גם שזמן הביצוע שלו זה אפס כי תוכן הקלט לא חשוב וצריך רק לדעת מי הזין את המחשב הנאיבי. הסבר נא. |
 |
 |
 |
|
|
|
||
|
||||
|
''אלגוריתם מיון נאיבי'', לצורך העניין, הוא שם כללי לקבוצה של כמה אלגוריתמים שאינם מתבססים על שום רעיון מחוכם, אלא על תפיסה אינטואיטיבית יחסית של מיון. למשל, מיון הכנסה, שהוא נפוץ למדי בקרב מי שמשחק קלפים - תתחיל עם יד ריקה, קח קלף מהערימה. קח את הקלף הבא והכנס אותו למקומו הנכון (לפני או אחרי הקלף הקיים). קח עוד קלף והכנס אותו למקומו הנכון (על ידי השוואה עם שני הקלפים שכבר יש ביד) וכן הלאה. במקרה ה''גרוע'', כל קלף יושווה עם כל הקלפים האחרים, ולכן מספר ההשוואות יהיה פרופורציוני לריבוע מספר הקלפים. שים לב שוב לנקודה המרכזית כאן - מדידת הזמן היא לא אבסולוטית (כמה שניות, למשל) אלא מתמקדת בקצב הגידול של ''זמן הריצה'' כאשר מגדילים את הקלט (כאן ''זמן הריצה'' הוא בעצם ''מספר הפעולות הבסיסיות''). |
|
|
|
|
|
|
||
|
||||
|
נדמה לי שהאלמוני פשוט לא הבין את המלה "מיון", ואכן זו מלה שדורשת הסבר כשקהל היעד לא למד מדעי המחשב: לרוב חושבים על "מיון" כחלוקת קבוצה לתת-קבוצות לפי קריטריון1, ואז מתבקש ש"אלגוריתם מיון" פירושו אלגוריתם הכרעה. כנראה מוטב לומר "אלגוריתמי סידור". (לאלמוני - אם זה הבלבול, ואם הוא עדיין קיים - הכוונה ב"מיון" לסידור קבוצת מספרים, שנתנונים ללא סדר, לפי גודלם.) 1 זו אפילו האטימולוגיה של המלה. |
|
|
|
|
|
|
||
|
||||
|
המממ, אכן. לא חשבתי על זה בכלל. | |
|
|
|
|
|
||
|
||||
|
נא להסביר את (1)! | |
|
|
|
|
|
||
|
||||
|
''מיון'' נולד מהמילה ''מין''. יענו, מיון היה במקור חלוקת איברים לתת-קבוצות לפי מינם. | |
|
|
|
|
|
||
|
||||
|
ומה ההבדל בין זה לבין המובן הרגיל של מיון? | |
|
|
|
|
|
||
|
||||
|
זה (חלוקה על-פי מינים) המובן ה"רגיל" של מיון. המובן השונה הוא זה של מדעי-המחשב – סידור לפי סדר כלשהו (למשל, לקסיקוגרפי). שימוש במשמעות רגילה: למיין את הקלפים לזוגיים ואי-זוגיים. שימוש במשמעות ממ"ח: למיין את הקלפים בסדר עולה. |
|
|
|
|
|
|
||
|
||||
|
לדעתי מדובר בטעות תרגום שמישהו עשה אי שם בשנות הששים, ומאז אנו תקועים עם מושגים עבריים לא מדוייקים. המילים "SORT" או "ORDER" הן הן שהיו צריכות להיות מתורגמות ל"סידור" (אגב: סידור בשני מובניו - גם כסדור של פרטים לפי גודלם, וגם סידור במובן של "לסדר את העניינים": sort things out) - בעוד ש"מיון" היא המילה שהיתה צריכה להיות התרגום ל- "filtering" או "selecting" מעולם המחשבים. |
|
|
|
|
|
|
||
|
||||
|
sort באנגלית זה מין/סוג/מחלקה. to sort זה לארגן לפי מין/סוג/מחלקה. התרגום למיון הוא דווקא מצויין. המילה order במדעי המחשב אכן מתורגמת למילה סדר (למיטב ידיעתי). |
|
|
|
|
|
|
||
|
||||
|
באופן כללי, אומרים על אלגוריתם שהוא "נאיבי" אם הוא "לא מתוחכם", כלומר, הוא פותר את הבעיה בצורה הכי פשוטה שאפשר לחשוב עליה. במקרה של אלגוריתמי מיון, אלגוריתם נאיבי לדוגמא הוא האלגוריתם שהרבה אנשים משתמשים בו למיון הקלפים שלהם במשחקי קלפים: בכל פעם, תפוס אחד מהקלפים והעבר אותו למקומו הנכון, והמשך כך עד שהקלפים ממוינים. כדי למיין n קלפים, האלגוריתם הזה יבצע בערך n בריבוע צעדים. הסיבה שעבור כל קלף, צריך לבצע בערך n צעדים כדי להעביר למצוא את מקומו הנכון, ואת זה צריך לבצע עבור n קלפים. |
|
|
|
| חזרה לעמוד הראשי | המאמר המלא |
| מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים | |
 RSS מאמרים |
כתבו למערכת |
אודות האתר |
טרם התעדכנת |
ארכיון |
חיפוש |
עזרה |
תנאי שימוש
|
© כל הזכויות שמורות |