שאלה יפה שראיתי עכשיו...

[Fingertip]

שאלה יפה שראיתי עכשיו...

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

 

[gil levi]

אתה יכול להגדיר

מה סיבוב של מטריצה בבקשה?

 

[DadleFish]

אני מניח

ש-א' זו סיבוכיות זמן, ולא סיבוכיות מקום. נסתכל על המטריצה כאוסף "מעגלים", שהם למעשה ריבועים באורך צלע עולה, מהמרכז (שאינו משתנה בעת סיבוב), ועד הצלע החיצונית. נניח לצורך העניין שיש לנו מטריצה 3x3, אז יש שני מעגלים - אורך צלע 3 ואורך צלע 1. כל מעגל כזה צריך להסתובב ב-90 מעלות, נניח clockwise. מ-1 עד n-1 איברים בצלע, צריך לבצע החלפה בין כל 4 האיברים המתאימים בצלעות, בדומה להחלפה בין שני איברים. אין לי זמן להדגים/להסביר, אבל - 1. ברור שזה עובד על המטריצה עצמה ולכן סיבוכיות מקום קבועה; 2. מספר הפעולות הוא מסד"ג n^2 כי אם נסכום את אורכי הצלעות תהיה פשוט סדרה חשבונית עולה ולכן n^2 פעולות, כפול 4 שאינו משנה את הסד"ג.

 

[johnny d]

זמן ליניארי ומקום קבוע, לא כזו בעיה

בחר רבע, ועבור כל איבר ברבע זה (שאליו מתאימים עוד 3 איברים נוספים במטריצה שמתאימים לסיבובים של 90 מעלות) בצע החלפה סיבובית של ארבעת האיברים. חישוב האיברים בעזרת חיבור וחיסור, ליניארי, מקום קבוע, ארבעה מיקומים ומשתנה עזר להחלפה.

 

[Fingertip]

../images/Emo26.gif

מה שאהבתי בשאלה הוא לא הקושי שבה, אלא הפשטות... שימו לב לפתרון נחמד הנעזר בסימטריות: א. כידוע, סימטריה היא איזומטריה, וכל איזומטריה ניתנת להצגה כמכפלה של שיקופים. יש ארבעה שיקופים אפשריים במטריצה: שניים אורכיים ושניים אלכסוניים. נקרא להם n, e, ne, nw לפי כיוון ציר השיקוף עפ"י שושנת הרוחות. אפשר בקלות לאמת את הטרנספורמציות הבאות:

n: (i,j) -> (i, n + 1 - i) {We assume the numbering is 1..n} e: (i,j) -> (n 1 - i, j) nw: (i,j) -> (j,i) ne: (i,j) -> (n 1-i, n 1-j)​

אם נסמן ב-(Td(i,j הטרנספורמציה המתאימה לשיקוף בכיוון d עבור d = n, e, ne, nw, נקבל את הקוד הג'נרי הבא:

Reflect(A, d): {B is a new matrix} for i = 1..n, j = 1..n do B[Td(i,j)] := A[i,j]​

מכאן נקבל, למשל, בפשטות את הסיבוב בזוית של 90 מעלות:

RotateLeft := Reflect(Reflect(A, n), nw)​

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

IterateN: for i= 1..n, j = 1..[n/2] do return (i,j) return done; IterateE is similar IterateNW: for i = 2..n, j = 1..i-1 do return (i,j) return done; IterateNE is similar​

ואז הקוד עבור השיקוף יהיה:

Reflect(A, d): ind := iterateD while (ind <> done) do switch(A(ind), A(Td(ind)) ind := iterateD​

מה דעתכם? אהד.

 

[vinney]

אלגנטי ביותר ../images/Emo13.gif

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

 

[Fingertip]

העף מבט בסעיף ב'...

אהד.

 

[vinney]

כן, לזה התכוונתי...

הפתרון שלך לא בסיבוכיות מקום קבועה...

 

[Fingertip]

לא הבנתי...

הפתרון בסעיף ב' לא בסיבוכיות מקום קבועה? אבל אני לא יוצר שם שום דבר חדש (מלבד: i,j,ind וכנראה גם המשתנה שמשתמשים בו בהחלפה ב-switch). אהד.

 

[vinney]

הקטע הזה בפתרון שלך

פה:

{B is a new matrix} for i = 1..n, j = 1..n do B[Td(i,j)] := A[i,j]​

מה המשמעות של B? כי לי לא נראה כמו משהו שסיבוכיות המקום שלו קבוע, הוא תלוי בגודל A. זה יתאים לסעיף א', אבל לא לסעיף ב'.

 

[Fingertip]

נו? זה בסעיף א...

בסעיף ב' אני משנה את הפונקציה כך שהיא תשנה את המטריצה:

Reflect(A, d): ind := iterateD while (ind <> done) do switch(A(ind), A(Td(ind)) ind := iterateD​

וככה לא משתנה סיבוכיות המקום... אהד.

 

[vinney]

הא, אוקי

ידעתי שפיספסתי משהו