סיבוכיות בלולאות
- פותח הנושא oripollak
- פורסם בתאריך
ממש לא
יתכן ועד כה שהגישו לך במקום לימודייך כך זה היה, אך השאלה, והתשובה שניתנו לשואל היו "מעשיים". מדעי המחשב גרידא, ולא התבססות על מרצה כזה או אחר, או מה כן יכתבו לך במבחן או לא. אישית, נראה לי הרגל מאוד מגונה. בנושאי סיבוכיות, מאוד ברור, הסיבוכיות תלויה בגודל הקלט. ודברים קבועים אינם משפיעים על סדר הגודל האסימפטוטי. לכן, התשובה הנכונה לשאלתו תהיה O(M*N) כפי שגם רשמו, כמובן, אם ידוע משהו על היחס ביניהם, אז ניתן "לצמצם" את הכתיבה ל O(M^2) או O(N^2) תלוי ביחס ביניהם.
יתכן ועד כה שהגישו לך במקום לימודייך כך זה היה, אך השאלה, והתשובה שניתנו לשואל היו "מעשיים". מדעי המחשב גרידא, ולא התבססות על מרצה כזה או אחר, או מה כן יכתבו לך במבחן או לא. אישית, נראה לי הרגל מאוד מגונה. בנושאי סיבוכיות, מאוד ברור, הסיבוכיות תלויה בגודל הקלט. ודברים קבועים אינם משפיעים על סדר הגודל האסימפטוטי. לכן, התשובה הנכונה לשאלתו תהיה O(M*N) כפי שגם רשמו, כמובן, אם ידוע משהו על היחס ביניהם, אז ניתן "לצמצם" את הכתיבה ל O(M^2) או O(N^2) תלוי ביחס ביניהם.
בא לי מיץ עכשיו...
בכל המבחנים שראיתי ועשיתי במדעי המחשב אף פעם לא ראיתי בתשובות O של X*Y זה תמיד היה N בחזקת משהו (או משהו עם לוג..) N זה סימן מוסכם ולא משנה איזה אותיות תוקעים בשאלה אולי באקדמיה ובמקומות שבונים דברים כבדים כן נותנים חשיבות לאותיות אבל לפי השאלה זה נראה לי כמו רמה של תיכון ושם התשובה תהיה N^2 נניח שאני עושה מבחן בתיכון ויש לי מטריצה בגודל A על B מה יהיה סדר גודל המעבר על כל תאי המטריצה ? לפי דעתי התשובה המתבקשת היא O של N^2 ולא O של A*B
בכל המבחנים שראיתי ועשיתי במדעי המחשב אף פעם לא ראיתי בתשובות O של X*Y זה תמיד היה N בחזקת משהו (או משהו עם לוג..) N זה סימן מוסכם ולא משנה איזה אותיות תוקעים בשאלה אולי באקדמיה ובמקומות שבונים דברים כבדים כן נותנים חשיבות לאותיות אבל לפי השאלה זה נראה לי כמו רמה של תיכון ושם התשובה תהיה N^2 נניח שאני עושה מבחן בתיכון ויש לי מטריצה בגודל A על B מה יהיה סדר גודל המעבר על כל תאי המטריצה ? לפי דעתי התשובה המתבקשת היא O של N^2 ולא O של A*B
אתה כנראה פיספסת את המשמעות
של N. זה לא סתם אות, זה יכול להיות כל אות, אבל יש לה משמעות מסוימת, היא מייצגת את גודל הקלט. במקרה של מטריצה A*B, מה המשמעות של N בתשובה המתבקשת שלך? שום משמעות. גודל הקלט שלך הוא A כפול B, אין שום N באמצע, וכך גם הסיבוכיות, שהיא לצורך העניין לינארית במספר התאים, תהיה A*B, ולא שום N^2.
של N. זה לא סתם אות, זה יכול להיות כל אות, אבל יש לה משמעות מסוימת, היא מייצגת את גודל הקלט. במקרה של מטריצה A*B, מה המשמעות של N בתשובה המתבקשת שלך? שום משמעות. גודל הקלט שלך הוא A כפול B, אין שום N באמצע, וכך גם הסיבוכיות, שהיא לצורך העניין לינארית במספר התאים, תהיה A*B, ולא שום N^2.
Copyright©1996-2021,Tapuz Media Ltd. Forum software by XenForo® © 2010-2020 XenForo Ltd.