רוטר - עוד תרגיל על סיבוכיות (הוכח/הפרך), עזרה בבקשה

יומן פעילות	לוח שנה	מבזקי חדשות	תקנון	RSS	כותרות	כותרות לפי תגובה	ניקוי קוקיז	IP	להורדת אפליקציה
eBay	AliExpress	GearBest	Amazon	Booking	Kiwi	SkyScanner	Trip Advisor

"עוד תרגיל על סיבוכיות (הוכח/הפרך), עזרה בבקשה"

גירסת הדפסה

קבוצות דיון לימודים, מדע ותרבות נושא #21018	מנהל סגן המנהל מפקח Winner צל"ש מומחה

אשכול מספר 21018

jon snow

חבר מתאריך 18.7.13
655 הודעות, 1 פידבק

10:43 15.11.14

עוד תרגיל על סיבוכיות (הוכח/הפרך), עזרה בבקשה

http://srv1.jpg.co.il/1/54671031ecd4c.png

שתף

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

האשכול	מחבר	תאריך כתיבה	מספר
לא תתכן	Dark-Wish	15.11.14 11:29	1
למה שואפת לאינסופ?	jon snow	15.11.14 13:21	2
לקחתי את איקס בתור פונקציה כלשהי	Dark-Wish	15.11.14 13:53	3
מכתב	Deuce	20.11.14 19:21	4

Dark-Wish
חבר מתאריך 25.5.05
12576 הודעות

11:29 15.11.14

1. לא תתכן
בתגובה להודעה מספר 0

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

נשלח ע"י הסלולרי

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

jon snow

חבר מתאריך 18.7.13
655 הודעות, 1 פידבק

13:21 15.11.14

2. למה שואפת לאינסופ?
בתגובה להודעה מספר 1

נשארתי עם איקס קטן מקבוע. ולא התייסת בכלל לחלק הימני של המשפט?

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

Dark-Wish
חבר מתאריך 25.5.05
12576 הודעות

13:53 15.11.14

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

ערכתי לאחרונה בתאריך 15.11.14 בשעה 14:01 בברכה, Dark-Wish

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

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

מצד שני
אתה יכול לקחת פונקציה קבועה f=5, וזה מקיים לך את שני הצדדים...

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

Deuce
חבר מתאריך 1.9.08
6225 הודעות

19:21 20.11.14

4. מכתב
בתגובה להודעה מספר 0

תהא f שמקיימת את התנאי השני. לפי הגדרה קיים C כך שלכל n טבעי מתקיים:
f(n)^2 <= Cf(n)

כלומר:

f(n) <= C

לכל n, ולכן f = O(1), ולכן לא ייתכן ש-f הינה אומגה של lg n.

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד