שאלה במיון - עמוד 2 - תכנות - HWzone פורומים
עבור לתוכן
  • צור חשבון

שאלה במיון

guy81

נוצר על ידי guy81
ב תכנות

Recommended Posts

שניצל Zone Master

שניצל

פורסם
פורסם

לא, בכל דלי יהיו לך (o(1 מספרים. יש לך n דליים ו-n מספרים, מה שאומר שאם ההתפלגות היא אחידה, אז בממוצע יהיה לך בדיוק מספר אחד בכל דלי. מיון דליים מסתמך על ההנחה הזו, ולכן כשמחשבים את הסיבוכיות שלו לא מתייחסים ל-worst case אלא לסיבוכיות הממוצעת.

קישור לתוכן
שתף באתרים אחרים
Gil28 Zone Master

Gil28

פורסם
פורסם

האלגוריתם אמנם מסתמך על התפלגות אחידה, אבל ממש לא מספר אחד בכל דלי.

האלגוריתם מחלק את המספרים לדליים (O(n, insertion sort (זמן קבוע) שוב (O(n ואז שרשור (O(n. סה"כ (O(n.

נ.ב. ממש מציק לכתוב (O(n

קישור לתוכן
שתף באתרים אחרים
שניצל Zone Master

שניצל

פורסם
פורסם

כי במיון דליים אין שום דרישה שמספר הדליים יהיה זהה למספר האיברים.

יכול להיות שיהיו n איברים ו-k דליים, ככה שבכל דלי יש בתוחלת (o(n/k איברים.

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

קישור לתוכן
שתף באתרים אחרים
guy81 Zone Wannabe

guy81

פורסם
  • מחבר
פורסם

טוב..עוד שאלה אחרונה לתקופה הקרובה(מקווה..)

בקשר לסעיף ב פה:

http://www.fastup.co.il/images/1548587.bmp

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

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

קישור לתוכן
שתף באתרים אחרים
Gil28 Zone Master

Gil28

פורסם
פורסם

1. hash ולא hush.

2. אם פונקציית הגיבוב מכניסה מפתח שונה לאותו תא, הרי שהיא לא מוצלחת אבל גם זה יכול לקרות. יוצרים רשימה מקושרת ואז במקום (1)O

תקבל O של אורך הרשימה.

קישור לתוכן
שתף באתרים אחרים

ארכיון

דיון זה הועבר לארכיון ולא ניתן להוסיף בו תגובות חדשות.

עבור לרשימת הדיונים
×
  • צור חדש...