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

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

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

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

לאלגוריתם נתון ישנו זמן ריצה פולינומי אם קיים פולינום (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.html