Recent Forum Posts
From categories:
page 1123...next »

It's 0(n). Copying all the n-1 elements.

Re: סלייסינג by Daniel NukraiDaniel Nukrai, 07 Aug 2017 14:08
סלייסינג
אמיר (guest) 07 Aug 2017 12:31
in discussion Spring 2017 / Exam - Spring 2017 » סלייסינג

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

תודה!

סלייסינג by אמיר (guest), 07 Aug 2017 12:31

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

אנחנו מבקשים שארבעת הפעילים הבאים בפורום ישלחו אלי בדוא״ל את שמם ומספר תעודת הזהות שלהם. ואנא - רק פעיל אחד לכל שם

Eden F
Arik H
Daniel Nukrai
גיא

כתובת הדוא״ל שלי היא
li.ca.uat.sc|ynneb#li.ca.uat.sc|ynneb

ורצוי שעה אחת קודם…

בברכה

בני

כל רמה ברקורסיה עולה n, אבל יש logn רמות, לכן זה צריך להיות nlogn, לא?

by guest (guest), 27 Jul 2017 16:44

לאן צריך להגיע?

מיקום הבחינה? by tal (guest), 27 Jul 2017 16:15

“The time has come," the Walrus said,
“To talk of many things:
Of shoes - and ships - and sealing - wax -
Of cabbages - and kings -
And why the sea is boiling hot -
And whether pigs have wings.”

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

The time has come by benny_chorbenny_chor, 27 Jul 2017 15:10
noam (guest) 27 Jul 2017 15:02
in discussion Spring 2017 / Exam - Spring 2017 » מועד א' 2016 סמסטר א' שאלה 2

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

by noam (guest), 27 Jul 2017 15:02

slicing עולה O(n), כי מה שקורה הוא שאנו יוצרים שתי רשימות חדשות בזכרון - שהגודל שלהן ביחד הוא n.

by noam (guest), 27 Jul 2017 14:58

מישהו יכול בבקשה להסביר למה סיבוכיות האלגוריתם של חיפוש בינארי עם סלייסינג שראינו הוא o(n)?
תודה!

יש הסבר מפורט לשאלה זו בדיוק, בעמוד 25 במצגת 8.

הסיבה היא שאם יש לנו 2 בחזקת 11 מינוס 1 אז כל הביטים של שדה האקספוננט הם 1, וזה מקרה
מיוחד, שאין מתייחסים אליו כאל מספר נקודה צפה רגיל, אלא כאל ״אינסוף״.

Re: floating Point by benny_chorbenny_chor, 27 Jul 2017 14:16

The two following statements can be proven formally using the $O( \bullet )$ notation definition:
If you also know that $n \geq m$, then $mn \leq n^2$, and therefore $O(mn+n^2)=O(n^2)$.
If you know that $m \geq n$, then $n^2 \leq mn$, and therefore $O(mn+n^2)=O(mn)$.

Without additional information, $O(mn+n^2)$ is the best you can do.

Re: BIG O notation - a question by Eden FEden F, 27 Jul 2017 13:49

Unless you got additional information on the relations between n and m, the right expression is $O(mn+n^2)$.
Each of the other two expressions may be incorrect for certain relations of m and n.
For example, $O(mn)$ will be incorrect in cases where $m<<n$. e.g. $n = m^2$.

Every time the following line is executed:

m = min(lst[i:n])

A new list of size n-i is created and passed as a parameter to min. However, after min returns a value, the list has no variable pointing to it (the variable was internal to min), and therefore we assume that Python frees that memory.
In conclusion, the maximum amount of memory used at any single time (due to that specific line) is $max_{0 \leq i \leq n}\{n-i\}=n$. Therefore, the space-complexity is $O(n)$ (the rest of the variables are of constant size).

Hey,
I have a question about big o notation -
O(mn+n^2) ?=? O(mn)/O(n^2)/O(mn+n^2)
Whats the best one?
thank you

BIG O notation - a question by no one (guest), 27 Jul 2017 12:38
floating Point
guest (guest) 27 Jul 2017 12:06
in discussion Spring 2017 / Exam - Spring 2017 » floating Point

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

floating Point by guest (guest), 27 Jul 2017 12:06

היי,
הגדרנו סיבוכיות מקום ככמות הזיכרון המקסימלית שנעשה בה שימוש במהלך התוכנית.
רציתי לדעת איך אני מתייחס לרשימות שלא שמורות לי, נגיד במקרה בו קיימת הלולאה הבאה:
נגיד שאורך הרשימה הוא n
for i in range(n)
m = min(lst[i:n])

האם יש להתחשב בסיבוכיות המקום בסלייסינג של הרשימה למרות שלא נשמרת בשום מקום קבוע ?
תודה רבה!

שאלה על סיבוכיות מקום by guest (guest), 27 Jul 2017 12:02
Amit (guest) 27 Jul 2017 11:34
in discussion Spring 2017 / Exam - Spring 2017 » מועד א' 2016 סמסטר א' שאלה 2

המרחק של 0000 לשאר המילים הוא 3.
התהייה היא, אם בכל מקרה בו אני לא נמצא בקוד nkd או חזרות או כל אחד מהקודים שלמדנו בכיתה - האם המשפט עדיין תופס כאן לגבי ה-d-1 שגיאות שניתן לזהות או שאנחנו עוברים לתאר דברים לפי תצורת הספירות?

by Amit (guest), 27 Jul 2017 11:34

היי, האם אתה מתכוון שלקידוד שמתואר כאן יש מילה שהמרחק ממנה לכל שאר המילים הוא 3?
אם כן, מה היא המילה הזאת? אני לא רואה אחת כזו.
באופן כללי יש כאן מילים שיש בהן שגיאה אחת ואפשר לתקן אותה, אבל לא את כל המילים שיש בהן שגיאה אחת.

by Arik HArik H, 27 Jul 2017 11:14
Amit (guest) 27 Jul 2017 10:52
in discussion Spring 2017 / Exam - Spring 2017 » מועד א' 2016 סמסטר א' שאלה 2

עדיין רלוונטי אם מישהו יכול לעזור :)

by Amit (guest), 27 Jul 2017 10:52

You should certainly understand the ideas involved in building a tree from a given corpus, as this was a major topic taught in the course. You are not expected to memoize the code.

Re: Huffman tree by benny_chorbenny_chor, 27 Jul 2017 09:01
page 1123...next »
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License