צריך עזרה בפיתוח אלגוריתם...

[ronsh82]

צריך עזרה בפיתוח אלגוריתם...

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

 

[vicz]

אולי אני מפספסת משהו

זה נראה לי פשוט מדי עבור כל אחד מהאיברים עושים 4 בדיקות ויוצא O העניין הוא שיכולים להיות כמה איברים כאלה. האם מחזירים את הראשון שמוצאים?

 

[ronsh82]

הסבר..

מדובר במערך דו-מימדי... אם אתה עושה 4 בדיקות על כל איבר זה יוצא O(n^2)... אם ישנם כמה איברים כאלה מחזירים את הראשון...

 

[e s a l]

אי אפשר לעשות את זה בפחות מ(O(n^2

ככה שהאלגוריתם הפשוט ביותר הוא הטוב ביותר - פשוט לבדוק לגבי כל איבר את התנאי הנ"ל.

 

[ronsh82]

אני כמעט בטוח שאפשר...

...

 

[vicz]

יכול להיות שאפשר לשלול חלק מהאיברים

צריך לחשוב על זה..

 

[vinney]

איך בדיוק זה n^2? מה זה n אצלך?

n זה בד"כ גודל הקלט.

 

[ronsh82]

סליחה שלא ציינתי.. גודל המערך הוא NxN

...

 

[vinney]

אבל מה זה n?

שוב, סיבוכיות אלגוריתם מודדים בגודל הקלט. אם המערך שלך N*N, אז גודל הקלט הוא N^2, ולכן הסיבוכיות שויקי ציינה היא נכונה, מדובר בסיבוכיות לינארית בגודל הקלט.

 

[vicz]

עקרונית זה נכון

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

 

[vinney]

אני הייתי מבקש הבהרה

אכן השאלה נראית לי טריויאלית.

 

[ronsh82]

שוב הסבר...

גודל המערך הדו מימדי הוא NxN. לכן גודל הקלט הוא N^2. הפתרון הטריוויאלי במקרה זה הוא לעבור על כל האיברים ולעשות את 4 הבדיקות וסיבוכיות הפתרון הזה הוא O(N^2) בגלל שעוברים על כל האיברים במערך הדו מימדי... הפתרון הדרוש בשאלה זו הוא צריך להיות בסיבוכיות O(N) ולא לינארית בגודל הקלט.

 

[vinney]

לא לא לא

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