האם ההוכחה הבאה בסדר ? מנמ"א
ענה על השאלה הבאה . אם התשובה שלילית , הוסף הוכחה; אם התשובה חיובית , הבא דוגמה של אלגוריתם (רצוי אלגוריתם ידוע) . השאלה : הוכחנו שהאלגוריתם D רץ בזמן טתה של (N^2) במקרה הגרוע ; האם זה אפשרי שהוא רץ בזמן (O(n על כל הקלטים שלו ? נסיון לפתרון : הטענה אינה נכונה . הוכחה : נניח , בשלילה , שזה אפשרי , שהאלגוריתם D רץ בזמן (O(n על כל הקלטים שלו . מכאן , שלא קיים קלט לאלגוריתם D , עליו רץ האלגוריתם בזמן הגדול (אסימפטוטית) מ - (O(n . מצד שני , הוכחנו שהאלגוריתם D רץ בזמן טתה של (N^2) במקרה הגרוע ; בפרט , האלגוריתם D רץ בזמן אומגה של (N^2) במקרה הגרוע . כלומר , קיים מקרה (המקרה הגרוע) , בו האלגוריתם D רץ בזמן , שאינו קטן אסימפטוטית מאומגה של (N^2) . אם כן : מצד אחד , לא קיים קלט , עליו רץ האלגוריתם D בזמן הגדול אסימפטוטית מ - (O(n ; מצד שני , קיים מקרה (הגרוע) , עליו רץ האלגוריתם D בזמן שאינו קטן אסימפטוטית מאומגה של (N^2) : סתירה . לכן הנחת השלילה שגויה , ואין זה אפשרי שהאלגוריתם D - שרץ בזמן טתה של (N^2) במקרה הגרוע - ירוץ בזמן (O(n על כל הקלטים שלו . האם כל ההוכחה הנ"ל נכונה ? בברכה , ליאור .
ענה על השאלה הבאה . אם התשובה שלילית , הוסף הוכחה; אם התשובה חיובית , הבא דוגמה של אלגוריתם (רצוי אלגוריתם ידוע) . השאלה : הוכחנו שהאלגוריתם D רץ בזמן טתה של (N^2) במקרה הגרוע ; האם זה אפשרי שהוא רץ בזמן (O(n על כל הקלטים שלו ? נסיון לפתרון : הטענה אינה נכונה . הוכחה : נניח , בשלילה , שזה אפשרי , שהאלגוריתם D רץ בזמן (O(n על כל הקלטים שלו . מכאן , שלא קיים קלט לאלגוריתם D , עליו רץ האלגוריתם בזמן הגדול (אסימפטוטית) מ - (O(n . מצד שני , הוכחנו שהאלגוריתם D רץ בזמן טתה של (N^2) במקרה הגרוע ; בפרט , האלגוריתם D רץ בזמן אומגה של (N^2) במקרה הגרוע . כלומר , קיים מקרה (המקרה הגרוע) , בו האלגוריתם D רץ בזמן , שאינו קטן אסימפטוטית מאומגה של (N^2) . אם כן : מצד אחד , לא קיים קלט , עליו רץ האלגוריתם D בזמן הגדול אסימפטוטית מ - (O(n ; מצד שני , קיים מקרה (הגרוע) , עליו רץ האלגוריתם D בזמן שאינו קטן אסימפטוטית מאומגה של (N^2) : סתירה . לכן הנחת השלילה שגויה , ואין זה אפשרי שהאלגוריתם D - שרץ בזמן טתה של (N^2) במקרה הגרוע - ירוץ בזמן (O(n על כל הקלטים שלו . האם כל ההוכחה הנ"ל נכונה ? בברכה , ליאור .