תורת הסיבוכיות – הבדלי גרסאות

{{תקציר פורטל|מדעי המחשב}}

'''תורת הסיבוכיות''' היא ענף של [[מדעי המחשב]], שבמסגרתו חוקרים את ה[[סיבוכיות]] של בעיות; כלומר, נבחנים ה[[משאב מערכת|משאבים]] הנחוצים לפתרון בעיה נתונה באמצעות [[מחשב]], ומושווית [[יעילות אלגוריתמית|יעילותם של אלגוריתמים]] שונים בפתרון בעיה זו. המשאב העיקרי הנבחן הוא '''[[סיבוכיות זמן|זמן הריצה]]'''; כלומר, נבחן משך הזמן (ה[[אסימפטוטה|אסימפטוטי]]) הנחוץ לשם ביצוע ה[[אלגוריתם]]. משאב נוסף הוא כמות ה'''[[סיבוכיות מקום|זיכרון]]''' הנחוץ לשם ביצוע האלגוריתם. ניתן להביא בחשבון משאבים נוספים, כגון כמה [[מעבד]]ים נחוצים לשם פתרון הבעיה ב[[עיבוד מקבילי]]. ענף הסיבוכיות החישובית נבדל מענף ה[[חישוביות]], שבו נבחנת השאלה האם ניתן בכלל לפתור בעיה נתונה, בלא קשר לכמות המשאבים הנחוצה.