פורסם 2002 בנובמבר 2923 שנים אבל מה קורה כאשר יש את אותו מספר כמה פעמים ברשימה? הרי יש רק תא אחד במערך להכניס אותו והוא יוצג רק פעם אחת, במקום פעמיים. תקנו אותי אם אני טועה.
פורסם 2002 בנובמבר 2923 שנים מה דעתך על זה (יושם בפסקל, לא יודע בקשר ל-C)נניח ויש לך מערך עם מספרים נתונים ואתה רוצה למיין אותוראשית את עושה סריקה של המספר הכי קטן, אחריי שמצאת אותו אתה מחליף אותו עם הערך הראשון במערךוככה אתה ממשיך, אתה עושה סריקה עכשיו של המספר הבא הכי קטן (רק שהפעם אתה סורק מהמקום השני במערך ולא מהראשון) ומחפש את הערך הכי קטן, אחריי שמצאת אותו אתה מחליף אותו עם הערך שנמצא במקום השני וכן הלאה...
פורסם 2002 בנובמבר 3023 שנים במקרה זה לא Selection Sort? כן זה SELECTION SORT... ועוד דבר, בעניין ה Bucket Sort , למרות שסיבוכיות זמן הריצה שלו היא ליניארית ביחס לאורך המערך, זמן הריצה הוא ארוך יותר מ Quicksort שכן יש צורך לעבור על המערך של כל הערכים האפשריים, ולכן בפועל הוא אמור להיות יותר איטי ברוב המקרים... לדעתי כדאי לנסות ולראות אם זה באמת ככה! וד"א, אני לא חושב שהמתרגל שלך המציא את האלגוריתם הזה מפני שזהו אלגוריתם די ידוע... :
פורסם 2002 בנובמבר 3023 שנים מחבר כמו שאמרתי, הוא נועד למיון מספרים בטווח נמוך במהירות גבוהה.בכל מקרה, אם הסיבוכיות היא לינארית אז הוא יותר איטי מ-quicksort, מפני שלכל n>10 מתקים:n < n*log(n)
פורסם 2002 בנובמבר 3023 שנים כמו שאמרתי, הוא נועד למיון מספרים בטווח נמוך במהירות גבוהה.בכל מקרה, אם הסיבוכיות היא לינארית אז הוא יותר איטי מ-quicksort, מפני שלכל n>10 מתקים:n < n*log(n)אכן, עבור מספרים קטנים ובטווח קטן הוא יפעל יותר מהר, אבל מצד שני, במקרה כזה זה לא כל כך משמעותי...בכל מקרה, יש דבר אחד שצריך להבין בעניין סיבוכיות - זה שסיבוכיות של אלגוריתם היא יותר קטנה, זה רק אומר שעבור קלט מאוד מאוד מאוד גדול (באופן פורמלי, כשאורך הקלט שואף לאינסוף) הוא יפעל יותר מהר. כאשר בפועל יכול להיות שהאלגוריתם בעל הסיבוכיות הקטנה יותר יפעל יותר זמן בגלל הקבועים. הנה דוגמה כדי להבהיר את הנקודה:נניח שאלגוריתם א' הוא בעל זמן ריצה של 000 ,100,000,000* n ולכן סיבוכיותו היא O(n)ואלגוריתם ב' הוא בעל זמן ריצה n^2 ולכן גם סיבוכיותו היא O(n^2).ולכן קל לראות שעבור n < 100,000,000,000 אלגוריתם ב' יפעל יותר מהר מאלגוריתם א' למרות שלאלגוריתם א' סיבוכיות יותר קטנה!וברור שבפועל לא נקבל קלט כל כך ארוך (למי שיש ספק, אפשר להוסיף עוד אפסים 8))יש מבין?
פורסם 2002 בנובמבר 3023 שנים מחבר נראה לי שאתה שוכח שסיבוכיות זמן ריצה נועדה לתאר את זמן הריצה הארוך ביותר של האלגוריתם, כלומר זמן הריצה במקרה הכי גרוע.אף אחד לא אמר שאם סיבוכיות זמן הריצה של אלגוריתמ אחד גדולה מהאחר, המימוש שלו ירוץ בכל המקרים לאט יותר.
פורסם 2002 בדצמבר 123 שנים נראה לי שאתה שוכח שסיבוכיות זמן ריצה נועדה לתאר את זמן הריצה הארוך ביותר של האלגוריתם, כלומר זמן הריצה במקרה הכי גרוע.לא מדויק! כשמדברים על סיבוכיות יש כמה אפשרויות: לפעמים מתכוונים למקרה הגרוע ביותר, לפעמים למקרה הממוצע ולפעמים (לעיתים רחוקות) למקרה הטוב(המהיר) ביותר.(כך למשל, אם נקח את ה quicksort בגירסתו המקורית, הסיבוכיות במקרה הממוצע ובמקרה הטוב ביותר היא n*logn ואילו במקרה הגרוע (שקורה כאשר המערך ממוין בסדר הפוך), הסיבוכיות היא n^2)מה שאני ניסיתי להבהיר זה שסיבוכיות זמן הריצה לא בהכרח שווה לזמן הריצה ואלו שני דברים שונים כשרוצים לדעת איזה אלגוריתם הוא מהיר יותר בפועל ולא מבחינה תאורטית.
פורסם 2002 בדצמבר 123 שנים מחבר אתה צודק, סיבוכיות היא לא זמן ריצה. היא אמצעי השוואה שיכול לתאר יחס בין זמני ריצה של אלגוריתמים שונים בעלי תפקידים זהם. זה ידוע ומובן.
פורסם 2002 בדצמבר 822 שנים complexity is always worst case, btw. and it's 100% bullshit, by the time it'll take you to calculat it you could benchmark every other way possible.
פורסם 2002 בדצמבר 822 שנים מחבר Benchmarks are ok, but they are machine specificA little taste of academic studies will change your mind :-)
פורסם 2002 בדצמבר 922 שנים complexity is always worst case, btw.now that's bullshit!!!מי אמר לך את זה?
פורסם 2002 בדצמבר 1022 שנים מחבר Because this is the definition of the term in computer science called "Complexity". It's like "Circle" is defined to be a set of points that are placed in equal distance from the center.
ארכיון
דיון זה הועבר לארכיון ולא ניתן להוסיף בו תגובות חדשות.