פורסם 2012 בינואר 413 שנים כאשר יש לי לדוגמא מערך {1,2,2,4,4,1,3,1} ואני רוצה את הדרך הכי יעילה בכדי למצוא אם יש מספר שמופיע רק פעם אחתשבדוגמא זה המספר 3האם הדרך הכי מהירה זה ללסדר את המערך בסדר עולה ואז לבדוק כל פעם מספר ואת זה שאחריו או שיש דרך יותר יעילה לעשות את זה?אפשרי לעשות את זה בפחות מ logn?
פורסם 2012 בינואר 413 שנים אני מניח שאתה מתכוון nlogn, ולא lרק logn.אפשר לעשות את זה ב-(o(n, במעבר אחר על המערך, ע"י שימוש ב-HashMap שפשוט סופר כמה פעמים מופיע כל מספר.
פורסם 2012 בינואר 713 שנים אפשר גם בלי hashmap ב-O(n) תחת הגבלות מסויימות:אם יש לך מספרים אי שליליים שלמים ואתה יודע מה המספר המקסימלי שאתה יכול לקבל (אם אתה רק לא יודע מה המקסימלי, אז אפשר לעבור פעם אחת על המערך ולמצוא את המקסימום) אז-צור מערך באורך n, כאשר n הוא טווח המספרים האפשרי שלך (למשל בדוגמה שלך - 0 עד 4), ואתחל אותו לאפסים.רוץ על איברי הרשימה, כאשר עבור כל איבר עם ערך k, תעלה את התא k במערך שלך ב-1.אם העלת תא שהערך שלו כבר היה 1, סימן שיש לך איבר שחוזר פעמיים.מצטער על ההסבר הכושל, אני עייף.
פורסם 2012 בינואר 813 שנים הפתרון שהצעת נקרא מיון תאים (bucket sort) ואם לדייק היעילות שלו היא גודל המערך שנוצר או גודל הקלט (n) , הגדול מבינהם.בנוסף יש פה ניצול זכרון מאוד גבוהה.לדוגמא עבור הקלט {1000000} - מערך עם איבר אחד, שיטת המיון תיצור מערך עם מיליון תאים בזכרון, תבצע מיליון פעולות איפוס, פעולת קידום אחת ובסוף צריך לעבור על המערך כדי לחפש ערכים ולכן עוד מיליון פעולות השוואה.אגב אין מגבלה של מספרים חיובים כי בקלות ניתן ליצור שני מערכים אחד לחיובים והשני לשלילים ובאמצעות תנאי לשים שם את המספרים במערך המתאים.כלל אצבע - במיון זה משתמשים כאשר המרחק בין המינימום למקסימום ידוע מראש, הוא קטן מ nlogn על הקלט ויש מספיק זכרון! אחרת לא חסכנו כלוםלדוגמא, אם היה ניתן לנו מערך בגודל מיליון של מספרים בין 0 ל 10 לשיטת המיון הזאת היה יתרון משמעותי.
פורסם 2012 בינואר 913 שנים אתה מתכוון ל counting sort וכל comparison sort הוא אומגה של n log n. די קל להוכיח, אבל ככה אני חושב על זה: במקרה הכי טוב יש לך מבנה נתונים עם insert ב O של 1, והכל כבר ממויין. אתה מחזיק בערך x, מה הדרך הכי יעליה למצוא (בעזרת השוואות, כמובן) את ה index שלתוכו x נכנס, חיפוש בינארי, נכון? שזה log n, ואתה צריך לעשות את זה עבור כל x, כלומר n פעמים. לכן אתה מקבל n log n אפשר האמת להשתמש ב counting sort עם גודל קבוע (m), ביחד עם quick sort ואז אתה מקבל סיבוכיות זמן של (n log (n/m וסיבוכיות זיכרון m. והנה לך bucket sort
פורסם 2012 בינואר 913 שנים וכל comparison sort הוא אומגה של n log n. די קל להוכיח, אבל ככה אני חושב על זה:במקרה הכי טוב יש לך מבנה נתונים עם insert ב O של 1, והכל כבר ממויין. אתה מחזיק בערך x, מה הדרך הכי יעליה למצוא (בעזרת השוואות, כמובן) את ה index שלתוכו x נכנס, חיפוש בינארי, נכון? שזה log n, ואתה צריך לעשות את זה עבור כל x, כלומר n פעמים. לכן אתה מקבל n log nאמ, זו לא ממש ההוכחה, פשוט הראית כאן ש-insertion sort רץ ב-nlogn. אבל לא הוכחת פה שאין שום מיון אחר שעושה את זה יותר מהר.קיימת הוכחה מתמטית שבמיון המתבסס על השוואות בלבד, חייבים לבצע אומגה של nlogn השוואות (ב-worst case כמובן). ההוכחה מופיעה בויקיפדיה.
פורסם 2012 בינואר 913 שנים כאשר יש לי לדוגמא מערך {1,2,2,4,4,1,3,1} ואני רוצה את הדרך הכי יעילה בכדי למצוא אם יש מספר שמופיע רק פעם אחתשבדוגמא זה המספר 3האם הדרך הכי מהירה זה ללסדר את המערך בסדר עולה ואז לבדוק כל פעם מספר ואת זה שאחריו או שיש דרך יותר יעילה לעשות את זה?אפשרי לעשות את זה בפחות מ logn?אני דיי גרוע ביעילות... תה יכול להסביר לי למה במקרה הזה זה nlogn?,תודה מראש
פורסם 2012 בינואר 913 שנים קרא את המאמר בויקיפדיה על מיונים. אם אין שום מגבלות על הקלט, צריך למיין ע"י אחד ממיוני ההשוואה, ומוסבר שם מדוע הסיבוכיות של כל מיוני ההשוואה היא לפחות nlogn.
פורסם 2012 בינואר 913 שנים וב"אין שום מגבלות" הכוונה היא שאין לנו שום הנחות על הקלט (כלומר על האורך שלו, טווח הערכים שלו וההתפלגות).
פורסם 2012 בינואר 1013 שנים מחבר public boolean single(int[] values){ quickSort(values,0,values.length-1); for(int i=0;i+1<values.length;i++){ if(values[i]!= values[i+1] ) { if(i+2>=values.length||i==0) return true; if(values[i+1]!=values[i+2]) return true; } } return false } [code][/left][left] [/left]
ארכיון
דיון זה הועבר לארכיון ולא ניתן להוסיף בו תגובות חדשות.