אלוהים1980
New member
שאלה על HashTable
בתרגיל בית במבני נתונים אני צריך לממש טבלת ערבול. אני מתכוון להשתמש בשיטה של שימוש בשתי פונקציות: 1. פונקצית המיקום - למציאת המקום עבור האיבר ע"פ המפתח שלו. 2. פונקצית הצעד - למקרה שהמקום כבר תפוס, למצוא את המקום הבא הפנוי. לאחר שנתון לי כבר גודל המערך הדרוש - N, אני צריך למצוא מספר ראשוני בשביל פונקצית המיקום. הצרה - סיבוכיות מציאת המספר הראשוני בגודל 2N בערך. (בעצם אני צריך שני מספרים כאלה - על מנת ליצור את שתי הפונקציות הנ"ל). הסיבוכיות צריכה להיות לכל היותר O של N. העניין הוא שכדי לגלות אם מספר הוא ראשוני אני צריך לעבור על כל המספרים הקטנים מהשורש שלו החל מ 2, ולבדוק האם הוא מתחלק בהם. אני חושש שהסיבוכיות תהיה גדולה מהנדרש. מה דעתכם?
בתרגיל בית במבני נתונים אני צריך לממש טבלת ערבול. אני מתכוון להשתמש בשיטה של שימוש בשתי פונקציות: 1. פונקצית המיקום - למציאת המקום עבור האיבר ע"פ המפתח שלו. 2. פונקצית הצעד - למקרה שהמקום כבר תפוס, למצוא את המקום הבא הפנוי. לאחר שנתון לי כבר גודל המערך הדרוש - N, אני צריך למצוא מספר ראשוני בשביל פונקצית המיקום. הצרה - סיבוכיות מציאת המספר הראשוני בגודל 2N בערך. (בעצם אני צריך שני מספרים כאלה - על מנת ליצור את שתי הפונקציות הנ"ל). הסיבוכיות צריכה להיות לכל היותר O של N. העניין הוא שכדי לגלות אם מספר הוא ראשוני אני צריך לעבור על כל המספרים הקטנים מהשורש שלו החל מ 2, ולבדוק האם הוא מתחלק בהם. אני חושש שהסיבוכיות תהיה גדולה מהנדרש. מה דעתכם?
) = O(n^0.5) = O(n