5. סיבוכיות

מבנה נתונים ואלגוריתמים

השתמשנו כבר בסימון O כדי לציין התנהגות כללית של אלגוריתם כפונקציה של גודל הבעיה. אמרנו כי אלגוריתם הוא O(log n), אם זמן הריצה שלו T(n) לפתרון בעיה בגודל n פרופורציונאלי ל- log n.

5.1 הסימון O

באופן פורמלי, O(g(n)) היא קבוצת הפונקציות f , כך שעבור c>0 כלשהו:

f(n)< cg(n)

לכל המספרים השלמים החיוביים n>N, עבור כל N גדול דיו. דרך אחרת לכתוב זאת היא:

lim f(n)/g(n) ≤ c , n→∞

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

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

ניתן להגדיר שתי פונקציות נוספות: Ω(g) ו- θ(g)

Ω(g) היא קבוצת הפונקציות Ω(g) שעבורה f(n)≥cg(n) לכל השלמים החיוביים n>N ו-

θ(g) = Ω(g) ∩ O(g)

ונוכל להסיק:

f Î θ(g)

אם:

lim f(n)/g(n) = c , n→∞

לכן, Ω(g) הוא חסם תחתון - פונקציות ב- Ω(g) גדלות מהר יותר מ- g, ו- θ(g) הן פונקציות הגדלות באותו קצב של g. לגבי שני הביטויים האחרונים הללו, כמו בשאר הדיון בנושא תיאוריית הסיבוכיות, מה שחשוב הוא סדר הגודל שבו גדלות הפונקציות, ולא הקבוע c שעשוי להשתנות בין שפות שונות, ביו מערכות הפעלה שונות ובין מהדרים שונים.

5.2 התכונות של הסימון O

ניתן להסיק את התכונות הכלליות הבאות כשעוסקים בסימון O:

• ניתן להתעלם מהמקדמים הקבועים.
• חזקות גבוהות של n גדלות מהר יותר מחזקות נמוכות.
• קצב הגדילה של סכום ביטויים שווה לקצב הגדילה של הביטוי בעל קצב הגדילה המהיר ביותר.
• קצב הגדילה של פולינום שווה לקצב הגדילה של הביטוי המוביל שלו (הביטוי בעל החזקה שמהסדר הגבוה ביותר).
• אם פונקציה f גדלה בקצב מהיר יותר מפונקציה g, וזו גדלה בקצב מהיר יותר מפונקציה h, אזי f גדלה בקצב מהיר
• יותר מאשר h.
• מכפלת החסמים העליונים של פונקציות מהווה חסם עליון של מכפלת הפונקציות.
• פונקציות מעריכיות (אקספוננציאליות) גדלות בקצב מהיר יותר מקצב גדילת החזקות.
• פונקציות לוגריתמיות גדלות בקצב איטי יותר מקצב גדילת החזקות.
• כל הפונקציות הלוגריתמיות גדלות באותו הקצב.
• הסכום של r n החזקות הראשונות גדל כחזקה ה- r+1.

5.3 אלגוריתמים פולינומיאלים ובעיות סוררות

אלגוריתם נקרא אלגוריתם פולינומיאלי אם זמן הסיבוכיות שלו הוא פולינומיאלי, כלומר, האלגוריתם הוא O(nª) עבור מספר שלם a.

בעיה נקראת בעיה סוררת (Intractable Algorithm) אם לא ידוע על אלגוריתם פולינומיאלי הפותר אותה. בהמשך נסקור בעיות מסוג זה.

5.4 ניתוח של אלגוריתם

5.4.1 רצף ביטויים פשוט

רצף ביטויים המבוצעים פעם אחת, שהסיבוכיות שלו היא O(1). אין זה משנה כמה ביטויים מכיל הרצף, מה שחשוב הוא שמספר הביטויים וזמני הביצוע שלהם קבועים לכל הבעיות.

5.4.2 לולאות פשוטות

אם בעיה בגודל n ניתנת לפתרון על ידי לולאה פשוטה:

for(i=0;i<n;i++)

{s;}

כאשר s הוא רצף ביטויים פשוט, אזי זמן הסיבוכיות של הפתרון יהיה nO(1), או בצורת הכתיבה המקובלת O(n).

אם ישנן שתי לולאות מקוננות:

for(j=0;j<n;j++)

for(i=0;i<n;i++)

{s;}

כאשר, שוב, s הוא רצף ביטויים פשוט, אזי יש n חזרות על רצף של O(n), והסיבוכיות המתקבלת היא nO(n), או כפי שמקובל לכתוב O(n²).

במקרים שבהם האינדקס קופץ בגדלים שהולכים וגדלים עם איטרציה נוספת, הלולאה עשויה להראות למשל כך:

h=1;

while(h<n)

{s; h=2h}

רצף ביטויים זה מכיל log n +1 ערכים, כך שהסיבוכיות תהיה O(log n).

במקרים שבהם הלולאה הפנימית תלויה באינדקס של לולאה חיצונית, כמו באופן הבא:

for(j=0;j<n;j++)

for(i=0;i<j;i++)

{s;}

הסיבוכיות תהיה O(n²), בדיוק כפי שהתקבל במקרה של לולאות מקוננות שראינו קודם, כך שמספר המשתנה של האיטרציות של הלולאה הפנימית אינו משפיע על "התמונה הכוללת".

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

h=n;

for(j=0;j<h;j++)

{

for(i=0;i<j;i++)

{s;}

h=h/2;

}

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

מושגים

חסם עליון

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

חסם תחתון

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

אלגוריתם פולינומיאלי

אלגוריתם אשר זמן הסיבוכיות שלו הוא פולינומיאלי, כלומר, האלגוריתם הוא O(nª) עבור מספר שלם a.

בעיה סוררת (Intractable Algorithm)

בעיה אשר לא ידוע על אלגוריתם פולינומיאלי הפותר אותה.

המשך ל: תורים חזור ל: תוכן עניינים