שאלה בסיבוכיות

[orninyo]

שלום

מישהו יכול להסביר לי בעברית את ההגדרה שבתמונה המצורפת?

ולתת רעיונות איך לעשות את זה בזמן

O(n)

ו-

O(n^2)

?

[attachment deleted by admin]

[yousux]

בשביל O של N זה נקרא לי קשור לזה:

http://en.wikipedia.org/wiki/Dynamic_programming

[orninyo]

אז מה בעצם המשפט הארוך הזה עם הסימנים המתמטיים אומר בעברית?

[yousux]

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

[שניצל]

הסימן שנראה כמו A הפוכה הוא "לכל".

כלומר, אתה צריך שהאיבר ה-i של S יהיה ה-ל הגדול ביותר שקטן או שווה ל-i, ולכל j מ-i-k+1 ל-i מתקיים (p(i) <=p(j.

קפיש?

[orninyo]

אני מבין מה כל סימן אומר אינדבידואלית

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

אני צריך פה איזה שורה תחתונה של מה האלגוריתם צריך לעשות בעברית נטו

מדובר בפיבונאצ'י ?

[שניצל]

לא קשור, לא דובר פה על סכומים.

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

[orninyo]

הגדול ביותר שקטן או שווה

ניסתי להבין מה הסברת ולא הצלחתי..

בין מה למה פועל המקס הזה ?

[שניצל]

אופס, התכוונתי k ויצא לי ל.

האיבר ה-i של S הוא המקסימום בין כל ה-kים שמקיימים את שני התנאים הבאים:

א. k<=i

ב. לכל j בין i-k+1 ל-i מתקיים (p(i)>=p(j.

[orninyo]

תודה