שאלה בקשר לחסם(אומגה)

[inferno3]

שאלה בקשר לחסם(אומגה)

יש שאלה בספר של קורמן שהולכת כך: נגדיר אומגה אינסוף(אומגה עם סמל של אינסוף למעלה) עכשיו ההגדרה היא:

f>=c*g -->fn = omgea infinity(gn)​

עבור C חיובי. וזה מתקיים עבור אינסוף N-ים ..עכשיו מבקשים להראות שעבור 2 פונקציות..מתקיים או FN היא O של GN או FN היא אומגה אינסוף של GN או שניהם וצריך להראות שזה לא מתקיים עבור אומגה "רגיל" אני אשמח אם מישהו יוכל להסביר לי ..מה בדיוק ההבדל בין אומגה אינסוף לבין אומגה רגיל?..כי זה נראה בדיוק אותו דבר(לפי ההגדרה) תודה רבה

 

[מסית ומדיח]

../images/Emo92.gif

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

 

[inferno3]

שאלה

אתה מתכוון לזה ..שאפשר לדוגמא לקחת :

c=1 f = 0 g = (-1)^n then: fn>=c*g​

וזה מתקיים עבור אינסוף N-ים(אי-זוגיים) אבל FN היא לא אומגה(רגיל) של GN!.

 

[vinney]

זה נכון לכל C

וגם ההגדרה של אומגה אינסוף היא לכל C, לדעתי.

 

[inferno3]

אתה יכול לחשוב על דוגמא?

כלומר שמתקיים רק אומגה אינסוף אבל לא אומגה?

 

[GuestOfHonor]

חיובי

בדיוק היה לנו את התרגיל הזה במבנה נתונים. תסתכל על הפונקציות הבאות : ƒ = n g = {1 עבור n זוגי n² עבור n אי-זוגי } כעת, ניתן לראות שf≠O(g) , וגם שf הוא לא אומגה(g). וזה בגלל שלכל c>0 וn>0 שנבחר, ניתן למצוא n גדול מספיק (פעם זוגי ופעם אי-זוגי) כדי לסתור את הגדרת החסם מלמעלה והחסם מלמטה.

 

[vinney]

כלל אצבע

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

 

[1ca1]

אפשר גם עם רציפה

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

 

[1ca1]

סליחה, טטא=אומגא כמובן

ודיי קל להראות שאם הפונקציה לא O של => הפונקציה היא אומגא אינסוף של (היה בתרגיל במבנ"ת...), פשוט בונים סדרה באינדוקציה... (אפשר נראה לי גם לקבל מיידית ע"י אקסיומת הבחירה, אבל זה סתם מתמטיקה, עדיף אינדוקציה...)

 

[ron369]

יותר פשוט

מניחים שf(x) גדולה מg(x) רק במספר סופי של n-ים. ואז לוקחים את הנקודה המקסימלית, מוסיפים ל-f, ומקבלים ש f+c>g, כלומר ש g=O(f). מש"ל.

 

[ron369]

*g גדולה מ-f במס' סופי של נק'

וכמובן שב f+c>g אני מתכוון באינסוף ובכלל. אחרת, אם זה לא מתקיים, בכל מקרה מתקיים החלק של התטה אינסוף, אם אני לא טועה.

 

[inferno3]

בעצם זה לא טוב

הפונקציות חייבות להיות חיוביות(לפי השאלה).

 

[מסית ומדיח]

דוגמא יותר טובה

f = n! for even n f = (n-1)! for odd n g = (n-1)! for odd n g = n! for even n​

 

[מסית ומדיח]

תיקון טעות

f = n! for even n f = (n-1)! for odd n g = (n-1)! for even n g = n! for odd n​

 

[inferno3]

תודה על העזרה.