זמן ריצה פולינומיאלי

מתוך ויקיפדיה, האנציקלופדיה החופשית

יש לך הודעות חדשות (השווה לגרסה הקודמת).

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

לאלגוריתם נתון ישנו זמן ריצה פולינומיאלי אם קיים פולינום (P(n כך שזמן הריצה של האלגוריתם עבור קלטים בגודל n חסום על ידי ערך הפולינום עבור n. זמני ריצה שאינם נחסמים על ידי פולינום, כגון זמן ריצה אקספוננציאלי, נקראים לעתים "סופר-פולינומיאליים".

מקובל לקשר זמן ריצה פולינומיאלי עם חישוב יעיל, כך שאלגוריתם ייחשב יעיל אם זמן הריצה שלו פולינומיאלי. מעשית, לא כל זמן ריצה פולינומיאלי מעיד על יעילות, שכן קיימים פולינומים בעלי חזקות גבוהות - בעת פיתוח אלגוריתם נעדיף זמן ריצה פולינומיאלי מסדר נמוך, כגון זמן לינארי או ריבועי.


מקור: http://he.wikipedia.org../../../%D7%96/%D7%9E/%D7%9F/%D7%96%D7%9E%D7%9F_%D7%A8%D7%99%D7%A6%D7%94_%D7%A4%D7%95%D7%9C%D7%99%D7%A0%D7%95%D7%9E%D7%99%D7%90%D7%9C%D7%99.html