תבנית:מבני נתונים ואלגוריתמים - מחברת קורס/גרפים/חיפוש רוחבי/תרגילים/זמן הריצה ברכיב קשירות קטן/תשובה v2

מתוך ויקיספר, אוסף ספרי הלימוד והמדריכים החופשי.

נגדיר את $\displaystyle V'$ כקבוצת הצמתים שאליהם אפשר להגיע מ $\displaystyle s$ , ו $\displaystyle E'$ כקבוצת הקשתות בין איברי צמתים אלה.

1-2 ו5-7 הן $\displaystyle O(1)$
3-4 הן $\displaystyle \Theta(|V|)$ .
הלולאה 8-14 מתבצעת בדיוק פעם אחת עבור כל צומת ב $\displaystyle V'$ . בפרט, הבדיקה ב8 והפעולה ב9 עולות $\displaystyle \Theta(|V'|)$ .
באופן דומה, הלולאה 10-14 מתבצעת בדיוק פעם אחת עבור כל זוג $\displaystyle u, v$ כך ש $\displaystyle (u, v) \in E'$ . הלולאה תורמת לכן $\displaystyle \Theta(|E'|)$ .

הסיבוכיות, לכן, היא $\displaystyle O(1) + \Theta(|V|) + \Theta(|V'|) + \Theta(|E'|) = \Theta(|V| + |E'|)$ .

כפי שנראה מיד, התשובה לסעיפים תלויה בפיזור הקשתות בין הצמתים ב $\displaystyle V$ .

[עריכה] הכרח

הנה משפט עזר בו נשתמש:

משפט:

לכל $\displaystyle \alpha < 1$ ,‏ $\displaystyle (n - n^{\alpha})^2 = \Theta(n^2)$

הוכחה: נשתמש בכללי גבולות וסדרי גדילה:

$\displaystyle \lim_{n \rightarrow \infty} \frac{(n - n^{\alpha})^2}{n^2} =$
$\displaystyle \lim_{n \rightarrow \infty} \frac{n^2 - 2n^{1 + \alpha} + n ^{2 \alpha}}{n^2} =$
$\displaystyle \lim_{n \rightarrow \infty} 1 - 2n^{\alpha - 1} + n ^{2 \alpha - 2} = 1$

נניח ש $\displaystyle V'$ הוא עץ (המסומן באליפסה בתרשים הבא), אך כל שני צמתים ב $\displaystyle V \setminus V'$ מחוברים בקשת.

מספר הקשתות בגרף הוא

$\displaystyle E = \Theta(|V'|) + \Theta((|V \setminus V'|^2) =$
$\displaystyle \Theta(|V|^{\alpha}) + \Theta((|V| - |V|^{\alpha})^2) =$
$\displaystyle \Theta(|V|^2).$

הסיבוכיות היא רק $\displaystyle O(|V| + |E'|) = O(|V|)$ , וקל לראות שביטוי זה אינו $\displaystyle \Theta(|V| + |E|) = \Theta(|V|^2)$ .

[עריכה] התכנות

שוב נניח ש $\displaystyle V'$ הוא עץ (המסומן באליפסה בתרשים הבא), אך כעת נניח שאין קשתות בגרף המקורי מעבר לקשתות אלו. במקרה זה הסיבוכיות תהיה מן הסתם $\displaystyle \Theta(|V| + |E'|) = \Theta(|V| + |E|)$ .

תבנית:מבני נתונים ואלגוריתמים - מחברת קורס/גרפים/חיפוש רוחבי/תרגילים/זמן הריצה ברכיב קשירות קטן/תשובה v2

מתוך ויקיספר, אוסף ספרי הלימוד והמדריכים החופשי.

[עריכה] הכרח

[עריכה] התכנות

צפיות

כלים אישיים

ניווט

קהילה

חיפוש

תיבת כלים