לא מצאתי דרך אחרת

איך אני יכול בלי i+2?

קודם תסביר למה השתמשת בו בכלל...

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

{1,1,1,2,2,3,3}

זה למקרה שהשיטה תגיע ל {1,2} ואז תבדוק אם יש אחרי ה2 עוד 2

סבבה, צודק.

יכלת לעשות את הכל ב-if אחד עם כמה and ו-or.

תחשוב סנדוויץ!

for (int l = 1;  i < (values.length-1) ; i++)
  if ( (values[i] != values[i-1]) and (values[i] != values[i+1]) )
  return true;

אמ, זו לא ממש ההוכחה, פשוט הראית כאן ש-insertion sort רץ ב-nlogn. אבל לא הוכחת פה שאין שום מיון אחר שעושה את זה יותר מהר.

קיימת הוכחה מתמטית שבמיון המתבסס על השוואות בלבד, חייבים לבצע אומגה של nlogn השוואות (ב-worst case כמובן). ההוכחה מופיעה בויקיפדיה.

אהה.. אולי כי זאת לא אמורה להיות הוכחה...

אגב את הוהכחה בוויקפדיה הרבה יותר יפה לבנות בעזרת עץ בינארי, עם n! עלים. כל עלה מייצג

פרמוטציה, כל node רגיל מייצג פעולה [השוואה\הצבה], כל נתיב מייצג פתרון אפשרי. בשביל להגיע לפתרון הנכון צריך לפחות

לעשות נתיב אחד, במקרה הגרוע האורך של הנתיב == גובה העץ. הגובה של העץ חייב להיות לפחות log !n, ואנחנו יודעים ש log !n הוא

אומגה n log n כי סטירלינג אמר לנו. אז הנה לך Q.E.D.

raiman1, עכשיו זה ברור יותר? אם לא נסה לציר את העץ עבור [ 2,3,1 ]

יוצא nlogn נכון?

מה הסיבכויות של n^2 + 500n + 100000 ?

ושל nlogn + n ?

הפתרון שלך לא מתמודד עם הקצוות (תחשוב על 1,2,2,2,2,3), בשביל זה הוא בדק גם אם i==0 או i+2>=length.

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

תחשוב סנדוויץ!

for (int l = 1;  i < (values.length-1) ; i++)
  if ( (values[i] != values[i-1]) and (values[i] != values[i+1]) )
  return true;

מה הסיבכויות של n^2 + 500n + 100000 ?

ושל nlogn + n ?

לגבי הקוד הוא לא טוב למקרה קצה לדוגמא אם יש מערך כזה {1,1,2,2,3,3,4} צריך להוסיף מקרה שלמספר האחרון אין מספר אחריו אחת זה יחזיר false

הסיבוכיות הראשונה היא n^2 והשניה nlogn ....

כן, זה באמת שובר, תודה על התיקון.

הסיבוכיות הראשונה היא n^2 והשניה nlogn ....

בדיוק. ופה יש לך n log n. ובכלל באופן כללי כשיש לך nk ו k הוא קבוע, אתה מתעלם מ k.

כי אנחנו מעוניינים בקצב הגדילה ביחס ל n.