| כותב |
|
turj
אורח
הצטרף / הצטרפה: 01 October 2003
משתמש: אונליין
הודעות: 12647
|
| נשלח בתאריך: 30 August 2006 בשעה 13:28 | | IP רשוּם
|
|
|
|
נניח שיש מערך בגודל N.
כל האיברים במערך שונים אבל יש איבר אחד שמופיע פעמיים, לדוגמא:
1,2,3,4,5,6,3
המספרים שיכולים להופיע במערך הם 1 עד n-1, ז"א אם יש לי מערך בגודל 4 איברים
הוא יכול להכיל בתוכו אך ורק את המספרים: 1,2,3
צריך לכתוב אלגוריתם שימצא את אותו המספר שמופיע פעמיים
צריך למצוא את הדרך היעילה ביותר לעשות זאת והסיבוכיות חייבת להיות o(1)
ז"א האלגוריתם לא תלוי בעצם בגודל המערך.
למישהו יש רעיונות?
|
| חזרה לתחילת העמוד |
|
| |
אלצ'קו
אחראי פורומים
ג2ר פ33תי
הצטרף / הצטרפה: 20 January 2006
משתמש: מנותק/ת
הודעות: 609
|
| נשלח בתאריך: 30 August 2006 בשעה 14:00 | | IP רשוּם
|
|
|
|
נשמע קצת בעייתי.
|
| חזרה לתחילת העמוד |
|
| |
shoshan
מנהל האתר
הצטרף / הצטרפה: 16 July 2005
מדינה: Israel
משתמש: מנותק/ת
הודעות: 4637
|
| נשלח בתאריך: 30 August 2006 בשעה 16:17 | | IP רשוּם
|
|
|
|
אם זה אפשרי ב-(O(1 אני מעוניין לשמוע 
__________________
עד מתי רשעים יעלוזו?
עַל כֵּן אֶמְאַס וְנִחַמְתִּי עַל עָפָר וָאֵפֶר.
|
| חזרה לתחילת העמוד |
|
| |
turj
אורח
הצטרף / הצטרפה: 01 October 2003
משתמש: אונליין
הודעות: 12647
|
| נשלח בתאריך: 30 August 2006 בשעה 16:31 | | IP רשוּם
|
|
|
|
זה נשמע גם לי קצת בעייתי, יכול להיות שלא הבנתי פה, הנה אני אכתוב פה את המקור באנגלית:
You are given a sequence S of numbers whose values range from 1 to n-1.
One of these numbers repeats itself once in the sequence. (Examples: {1
2 3 4 5 6 3}, {4 2 1 2 3 6 5}). Write a program that finds this
repeating number using a constant amount of memory
Note: "Constant memory" = the memory required for the solution cannot be a function of n
לפי מה שהבנתי דרוש שם סיבוכיות של O(1) לא?
|
| חזרה לתחילת העמוד |
|
| |
אלצ'קו
אחראי פורומים
ג2ר פ33תי
הצטרף / הצטרפה: 20 January 2006
משתמש: מנותק/ת
הודעות: 609
|
| נשלח בתאריך: 30 August 2006 בשעה 16:32 | | IP רשוּם
|
|
|
|
shoshan כתב:
| אם זה אפשרי ב-(O(1 אני מעוניין לשמוע
|
|
|
טוב, אם הסיבוכיות של בדיקת איבר במערך היא 1/n, אז אפשר לבצע את התהליך ב-O(1)
turj כתב:
זה נשמע גם לי קצת בעייתי, יכול להיות שלא הבנתי פה, הנה אני אכתוב פה את המקור באנגלית:
You are given a sequence S of numbers whose values range from 1 to n-1.
One of these numbers repeats itself once in the sequence. (Examples: {1
2 3 4 5 6 3}, {4 2 1 2 3 6 5}). Write a program that finds this
repeating number using a constant amount of memory
Note: "Constant memory" = the memory required for the solution cannot be a function of n
לפי מה שהבנתי דרוש שם סיבוכיות של O(1) לא?
|
|
|
לא, זה לא מה שכתוב שם. איפה אתה רואה שמבקשים סיבוכיות זמן ריצה קבועה?
|
| חזרה לתחילת העמוד |
|
| |
shoshan
מנהל האתר
הצטרף / הצטרפה: 16 July 2005
מדינה: Israel
משתמש: מנותק/ת
הודעות: 4637
|
| נשלח בתאריך: 30 August 2006 בשעה 16:36 | | IP רשוּם
|
|
|
|
 באמת לא רשום שם.
__________________
עד מתי רשעים יעלוזו?
עַל כֵּן אֶמְאַס וְנִחַמְתִּי עַל עָפָר וָאֵפֶר.
|
| חזרה לתחילת העמוד |
|
| |
turj
אורח
הצטרף / הצטרפה: 01 October 2003
משתמש: אונליין
הודעות: 12647
|
| נשלח בתאריך: 30 August 2006 בשעה 16:45 | | IP רשוּם
|
|
|
|
לא הבנתי נכון
מה אומר ה constant memory הזה?
|
| חזרה לתחילת העמוד |
|
| |
shoshan
מנהל האתר
הצטרף / הצטרפה: 16 July 2005
מדינה: Israel
משתמש: מנותק/ת
הודעות: 4637
|
| נשלח בתאריך: 30 August 2006 בשעה 16:45 | | IP רשוּם
|
|
|
|
זכרון קבוע.
__________________
עד מתי רשעים יעלוזו?
עַל כֵּן אֶמְאַס וְנִחַמְתִּי עַל עָפָר וָאֵפֶר.
|
| חזרה לתחילת העמוד |
|
| |
אלצ'קו
אחראי פורומים
ג2ר פ33תי
הצטרף / הצטרפה: 20 January 2006
משתמש: מנותק/ת
הודעות: 609
|
| נשלח בתאריך: 30 August 2006 בשעה 16:48 | | IP רשוּם
|
|
|
|
ועכשיו כשהבנת מה השאלה, תחשוב איך פותרים אותה. זו שאלה די קלאסית, והפיתרון לא מי יודע מה מסובך.
|
| חזרה לתחילת העמוד |
|
| |
turj
אורח
הצטרף / הצטרפה: 01 October 2003
משתמש: אונליין
הודעות: 12647
|
| נשלח בתאריך: 30 August 2006 בשעה 16:49 | | IP רשוּם
|
|
|
|
רגע רגע רגע, עדיין לא הבנתי, מזאת אומרת שהזכרון קבוע?
מישהו מוכן להסביר יותר לעמוק? איך אני בכלל שולט בכמות הזכרון?
[אני יודע רק מה זה סיבוכיות]
|
| חזרה לתחילת העמוד |
|
| |
אלצ'קו
אחראי פורומים
ג2ר פ33תי
הצטרף / הצטרפה: 20 January 2006
משתמש: מנותק/ת
הודעות: 609
|
| נשלח בתאריך: 30 August 2006 בשעה 16:51 | | IP רשוּם
|
|
|
|
מה זה אומר זיכרון קבוע? זה אומר שכמות הזיכרון שהאלגוריתם שלך דורש היא קבועה ולא תלויה ב-N.
|
| חזרה לתחילת העמוד |
|
| |
shoshan
מנהל האתר
הצטרף / הצטרפה: 16 July 2005
מדינה: Israel
משתמש: מנותק/ת
הודעות: 4637
|
| נשלח בתאריך: 30 August 2006 בשעה 17:31 | | IP רשוּם
|
|
|
|
זה אומר שאין לך עוד מערך של בוליאנים באותו גודל של המערך של המספרים.
__________________
עד מתי רשעים יעלוזו?
עַל כֵּן אֶמְאַס וְנִחַמְתִּי עַל עָפָר וָאֵפֶר.
|
| חזרה לתחילת העמוד |
|
| |
turj
אורח
הצטרף / הצטרפה: 01 October 2003
משתמש: אונליין
הודעות: 12647
|
| נשלח בתאריך: 30 August 2006 בשעה 18:12 | | IP רשוּם
|
|
|
|
אוקיי הבנתי, הסיבוכיות פה לא משנה
פשוט אסור להשתמש בשום משתני עזר, נכון?
|
| חזרה לתחילת העמוד |
|
| |
shoshan
מנהל האתר
הצטרף / הצטרפה: 16 July 2005
מדינה: Israel
משתמש: מנותק/ת
הודעות: 4637
|
| נשלח בתאריך: 30 August 2006 בשעה 19:27 | | IP רשוּם
|
|
|
|
מותר משתני עזר, פשוט שלא יהיו תלויים במספר האיברים במערך.
__________________
עד מתי רשעים יעלוזו?
עַל כֵּן אֶמְאַס וְנִחַמְתִּי עַל עָפָר וָאֵפֶר.
|
| חזרה לתחילת העמוד |
|
| |
Fate
פורומיסט על
הצטרף / הצטרפה: 25 October 2005
משתמש: מנותק/ת
הודעות: 571
|
| נשלח בתאריך: 30 August 2006 בשעה 23:35 | | IP רשוּם
|
|
|
|
יש שני סיבוכיות,
סיבוכיות זמן ריצה, סיבוכיות זיכרון.
לרוב אפשר לשנות אלגוריתם כך שיקח יותר זיכרון אבל פחות זמן ריצה... או ההפך...
דוגמא קלאסית זה פריצה של md5 hash ע"י Brute Force.
שיטה אחת שהיא עם סיבוכיות זמן ריצה גבוהה זה כל פעם ליצר ערך ולבדוק את הוא זהה להאש.
שיטה שנייה, שהיא עם סיבוכיות זיכרון גבוהה, זה לבנות טבלה של כל ההאשים האפשריים, ואז ללכת להאש שהמספר שלו זה ההאש עצמו מתחילת הטבלה.
|
| חזרה לתחילת העמוד |
|
| |
turj
אורח
הצטרף / הצטרפה: 01 October 2003
משתמש: אונליין
הודעות: 12647
|
| נשלח בתאריך: 30 August 2006 בשעה 23:38 | | IP רשוּם
|
|
|
|
fate, תודה על ההסבר.
|
| חזרה לתחילת העמוד |
|
| |
אלצ'קו
אחראי פורומים
ג2ר פ33תי
הצטרף / הצטרפה: 20 January 2006
משתמש: מנותק/ת
הודעות: 609
|
| נשלח בתאריך: 30 August 2006 בשעה 23:53 | | IP רשוּם
|
|
|
|
Fate כתב:
יש שני סיבוכיות,
סיבוכיות זמן ריצה, סיבוכיות זיכרון.
לרוב אפשר לשנות אלגוריתם כך שיקח יותר זיכרון אבל פחות זמן ריצה... או ההפך...
דוגמא קלאסית זה פריצה של md5 hash ע"י Brute Force.
שיטה אחת שהיא עם סיבוכיות זמן ריצה גבוהה זה כל פעם ליצר ערך ולבדוק את הוא זהה להאש.
שיטה
שנייה, שהיא עם סיבוכיות זיכרון גבוהה, זה לבנות טבלה של כל ההאשים
האפשריים, ואז ללכת להאש שהמספר שלו זה ההאש עצמו מתחילת הטבלה.
|
|
|
וכשאתה בונה את הטבלה של כל ההאשים, אתה לא משתמש באותה סיבוכיות זמן ריצה כמו לבדוק את כל ההאשים בלי לשמור אותם בטבלה?
|
| חזרה לתחילת העמוד |
|
| |
Fate
פורומיסט על
הצטרף / הצטרפה: 25 October 2005
משתמש: מנותק/ת
הודעות: 571
|
| נשלח בתאריך: 31 August 2006 בשעה 00:38 | | IP רשוּם
|
|
|
|
אלצ'קו כתב:
Fate כתב:
יש שני סיבוכיות,
סיבוכיות זמן ריצה, סיבוכיות זיכרון.
לרוב אפשר לשנות אלגוריתם כך שיקח יותר זיכרון אבל פחות זמן ריצה... או ההפך...
דוגמא קלאסית זה פריצה של md5 hash ע"י Brute Force.
שיטה אחת שהיא עם סיבוכיות זמן ריצה גבוהה זה כל פעם ליצר ערך ולבדוק את הוא זהה להאש.
שיטה
שנייה, שהיא עם סיבוכיות זיכרון גבוהה, זה לבנות טבלה של כל ההאשים
האפשריים, ואז ללכת להאש שהמספר שלו זה ההאש עצמו מתחילת הטבלה.
|
|
|
וכשאתה בונה את הטבלה של כל ההאשים, אתה לא משתמש באותה סיבוכיות זמן ריצה כמו לבדוק את כל ההאשים בלי לשמור אותם בטבלה?
|
|
|
גם נכון, אבל במקרה של טבלה אתה יכול לקבל אותה ממישהו, להוריד מהאינטרנט.
וזה לא נכלל בחישובי זמן ריצה כי זה נתון DATA קבוע....
|
| חזרה לתחילת העמוד |
|
| |
נושאים פעילים
רשימת משתמשים
חיפוש
עזרה
הרשמה
התחברות
UnderWarrior Forums : 
תיכנות
