אנליזה של אלגוריתמים
ויקיפדיה האנציקלופדיה encyclopedia
אנליזה (ניתוח) של אלגוריתמים הוא תחום במדעי המחשב, העוסק בגילוי מאפיינים שונים באלגוריתמים, וסיווג רמת החיסכון שלהם במשאבים, ז"א קביעת כמות המשאבים הנדרשים עבור ביצועו.
יש לערוך ערך זה. הסיבה היא: הערך דורש הגהה, ויקיזציה וסידור חלק מהנוסחאות המתמטיות מופיעות בו. | |
בדרך-כלל, יעילותו של אלגוריתם תלויה במספר הצעדים (זמן המורכבות) ובשטח האחסון (מורכבות אחסון) הנדרשים.
המונח "ניתוח אלגוריתמים" נטבע על ידי דונלד קונת'.[1] ניתוח אלגוריתמים הוא חלק חשוב של תאוריה רחבה יותר הנקראת תורת הסיבוכיות, אשר מספקת הערכות תאורטיות לכמות המשאבים הדרושים לכל אלגוריתם הפותר בעיה חישובית נתונה. הערכות אלו מספקות תובנות חשובות באשר לחיפוש אחר אלגוריתמים יעילים יותר ויותר.
בניתוח תאורטי של אלגוריתמים, נהוג להעריך את המורכבות שלהם במובן אסימפטוטי. כלומר, להעריך את מורכבות האלגוריתם עבור קלט שרירותי גדול. סימון O גדולה [], סימון אומגה גדול [] וסימון טטא גדול [] משמשים למטרה זו. למשל, חיפוש בינארי הוא חיפוש האמור לרוץ מספר צעדים, יחסי ללוגריתם של אורך הרשימה הממוינת שבה מתבצע החיפוש, או ב- , ב"זמן לוגריתמי".
ממד יעילות מדיוק (לא אסימפטוטי) ניתן לחישוב במקרים מסוימים אך בדרך כלל הוא דורש הנחות מסוימות לגבי יישום מסוים של האלגוריתם, הנקרא מודל של מחשוב. מודל של מחשוב עשוי להיות מוגדר במונחים של מחשב אבסטרקטי, למשל, מכונת טיורינג, או על ידי הנחה כי פעולות מסוימות מבוצעות ביחידת זמן.
לדוגמה, אם ברשימה הממוינת עליה אנו מריצים חיפוש בינארי יש n אלמנטים, ואנחנו יכולים להבטיח כי כל בדיקה של אלמנט ברשימה יכולה להתבצע תוך יחידת זמן, אז צריך לכל היותר log2 n + 1 יחידות זמן להחזיר תשובה.