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

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

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

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

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

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

זמן ריצה לינארי הוא בפרט פולינומיאלי ובפרט נחשב חישוב יעיל.


מקור: 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%9C%D7%99%D7%A0%D7%90%D7%A8%D7%99.html
שפות אחרות