1
00:00:00,000 --> 00:00:05,760

2
00:00:05,760 --> 00:00:08,900
>> דאג LLOYD: אז בCS50 למדנו על
מגוון של מיון וחיפוש

3
00:00:08,900 --> 00:00:09,442
אלגוריתמים.

4
00:00:09,442 --> 00:00:11,400
ולפעמים זה יכול להיות
קצת מסובך לשמור

5
00:00:11,400 --> 00:00:14,161
אחר מה אלגוריתם עושה מה.

6
00:00:14,161 --> 00:00:15,910
יש לנו באמת רק
ברפרוף על פני השטח מדי,

7
00:00:15,910 --> 00:00:18,740
יש הרבה חיפוש אחר
ואלגוריתמי מיון.

8
00:00:18,740 --> 00:00:21,780
אז בסרט הזה בואו
רק לקחת כמה דקות

9
00:00:21,780 --> 00:00:24,980
כדי לנסות ולזקק כל אלגוריתם
עד אלמנטי הליבה שלה

10
00:00:24,980 --> 00:00:27,810
כך שאתה יכול לזכור ביותר
מידע חשוב עליהם

11
00:00:27,810 --> 00:00:31,970
ולהיות מסוגל לבטא
הבדלים, במידת צורך.

12
00:00:31,970 --> 00:00:34,220
>> הראשון הוא סוג בחירה.

13
00:00:34,220 --> 00:00:38,210
הרעיון הבסיסי מאחורי בחירת מין
הוא ימצא את האלמנט הקטן ביותר ממוין

14
00:00:38,210 --> 00:00:42,890
במערך ולהחליף אותו עם
אלמנט הראשון של מערך לא ממוינים ש.

15
00:00:42,890 --> 00:00:46,620
אנחנו אמרתי שהמקרה הגרוע ביותר
זמן לרוץ של שn בריבוע.

16
00:00:46,620 --> 00:00:50,060
ואם אתה רוצה להיזכר למה, לקחת
מסתכל על וידאו מיון בחירה.

17
00:00:50,060 --> 00:00:54,560
זמן הריצה הטוב ביותר במקרה
גם בריבוע n.

18
00:00:54,560 --> 00:00:58,910
>> מיון בועות, הרעיון מאחורי זה
אחד הוא להחליף זוגות סמוכים.

19
00:00:58,910 --> 00:01:01,730
אז זה המפתח שעוזר לך
זוכר את ההבדל כאן.

20
00:01:01,730 --> 00:01:04,920
בחירת סוג שהוא, כל כך רחוק,
למצוא את בועת smallest--

21
00:01:04,920 --> 00:01:06,790
מיון הוא להחליף זוגות סמוכים.

22
00:01:06,790 --> 00:01:08,710
אנחנו להחליף זוגות סמוכים
אלמנטים אם הם

23
00:01:08,710 --> 00:01:12,530
מקולקל, אשר למעשה
בועות אלמנטים גדולים יותר בצד הימין,

24
00:01:12,530 --> 00:01:17,060
ובה בעת הוא גם מתחיל
להעביר אלמנטים קטנים יותר בצד השמאל.

25
00:01:17,060 --> 00:01:20,180
זמן ריצת מקרה הגרוע ביותר
של מיון בועות בריבוע n.

26
00:01:20,180 --> 00:01:23,476
זמן הריצה הטוב ביותר במקרה
של בועת סוג הוא n.

27
00:01:23,476 --> 00:01:25,350
כי במצב ש
אנחנו לא מעשה--

28
00:01:25,350 --> 00:01:27,141
אולי לא צריך
לעשות כל עסקות החלף בכל.

29
00:01:27,141 --> 00:01:31,026
אנחנו רק צריכים לעשות אחד
עובר על פני כל אלמנטי n.

30
00:01:31,026 --> 00:01:34,600
>> במיון הכנסה,
רעיון בסיסי כאן הוא הסטה.

31
00:01:34,600 --> 00:01:36,630
זה מילות מפתח למיון הכנסה.

32
00:01:36,630 --> 00:01:39,630
אנחנו הולכים צעד פעם דרך
המערך משמאל לימין.

33
00:01:39,630 --> 00:01:41,670
וכמו שאנחנו עושים, אנחנו
הולך להעביר אלמנטים

34
00:01:41,670 --> 00:01:46,260
כבר ראו כדי לפנות מקום ל
קטן יותר שצריכים להתאים למקום

35
00:01:46,260 --> 00:01:48,080
בחזרה שבחלק מסודרים.

36
00:01:48,080 --> 00:01:51,600
אז אנו בונים מערך ממוין אחד
אלמנט בכל פעם, משמאל לימין,

37
00:01:51,600 --> 00:01:54,740
ואנחנו משמרות דברים כדי לפנות מקום.

38
00:01:54,740 --> 00:01:58,650
זמן הריצה הגרוע ביותר של
מיון הכנסה בריבוע n.

39
00:01:58,650 --> 00:02:02,380
במקרה הטוב ביותר בזמן ריצה הוא n.

40
00:02:02,380 --> 00:02:05,380
>> מיזוג sort-- מילות מפתח
כאן הוא לפצל ולמזג.

41
00:02:05,380 --> 00:02:08,949
אנחנו לפצל את המערך המלא, אם
זה שישה אלמנטים, שמונה אלמנטים,

42
00:02:08,949 --> 00:02:13,790
10,000 elements-- לפצל אותו
למטה בחצי, בחצי, בחצי,

43
00:02:13,790 --> 00:02:17,720
עד שיש לנו במערך
של מערכי יסוד n אחד.

44
00:02:17,720 --> 00:02:19,470
קבוצה של מערכי יסוד n אחד.

45
00:02:19,470 --> 00:02:22,640
אז התחלנו עם אחד
מערך של 1,000 אלמנט,

46
00:02:22,640 --> 00:02:26,550
ואנחנו מגיעים לנקודה שבה אנחנו
יש 1,000 מערכים חד-יסוד.

47
00:02:26,550 --> 00:02:30,990
אז אנחנו מתחילים למזג מערכים תת אלה
שוב ביחד בסדר הנכונה.

48
00:02:30,990 --> 00:02:34,860
אז אנחנו לוקחים שני מערכים חד אלמנט
וליצור מערך דו-יסוד.

49
00:02:34,860 --> 00:02:38,180
אנחנו לוקחים שני מערכים דו-יסוד
וליצור מערך של ארבעה אלמנט

50
00:02:38,180 --> 00:02:43,900
וכן הלאה וכן הלאה עד שיש לנו
מחדש שוב מערך אלמנט n אחד.

51
00:02:43,900 --> 00:02:48,410
>> זמן הריצה הגרוע ביותר של
מיון המיזוג הוא n פעמים להיכנס n.

52
00:02:48,410 --> 00:02:52,390
יש לנו אלמנטי n, אבל
תהליך שחלוף זה

53
00:02:52,390 --> 00:02:56,960
לוקח להיכנס n צעדים כדי לקבל
חזרה למערך מלא.

54
00:02:56,960 --> 00:03:01,160
המקרה הטוב ביותר בזמן הריצה הוא גם יומן n
n כי תהליך זה לא ממש

55
00:03:01,160 --> 00:03:04,090
אכפת לי אם המערך היה
ממוין או לא להתחיל עם.

56
00:03:04,090 --> 00:03:07,590
התהליך הוא זהה, יש
אין דרך דברים קצרים.

57
00:03:07,590 --> 00:03:11,610
אז n להיכנס n במקרה הגרוע ביותר,
n להיכנס n במקרה הטוב.

58
00:03:11,610 --> 00:03:13,960
>> דברנו על שתי
מחפש אלגוריתמים.

59
00:03:13,960 --> 00:03:16,230
אז החיפוש ליניארי הוא על iterating.

60
00:03:16,230 --> 00:03:19,500
אנחנו להמשיך פני המערך
פעם אחת, משמאל לימין,

61
00:03:19,500 --> 00:03:21,950
מנסה למצוא את המספר
שאנחנו מחפשים.

62
00:03:21,950 --> 00:03:24,550
הזמן הגרוע ביותר הוא לרוץ O הגדול של n.

63
00:03:24,550 --> 00:03:27,610
זה עלול לקחת לנו iterating
על פני כל אלמנט

64
00:03:27,610 --> 00:03:30,660
כדי למצוא את האלמנט שאנחנו מחפשים
ל, או בתפקידו האחרון,

65
00:03:30,660 --> 00:03:31,630
או בכלל לא.

66
00:03:31,630 --> 00:03:34,720
אבל אנחנו לא יכולים לאשר כי עד
בדקנו בכל דבר.

67
00:03:34,720 --> 00:03:36,730
מ-המקרה הטוב, אנו מוצאים באופן מיידי.

68
00:03:36,730 --> 00:03:41,060
זמן הריצה הטוב ביותר במקרה של
החיפוש ליניארי הוא אומגה של 1.

69
00:03:41,060 --> 00:03:43,689
>> לבסוף, היה חיפוש בינארי,
אשר דורש מערך שונים.

70
00:03:43,689 --> 00:03:45,605
זכור כי זה מאוד
שיקול חשוב

71
00:03:45,605 --> 00:03:47,155
בעת עבודה עם חיפוש בינארי.

72
00:03:47,155 --> 00:03:50,180
זה תנאי הכרחי לשימוש בit--
המערך שאתה מחפש דרך

73
00:03:50,180 --> 00:03:52,160
חייב להיות מסודר.

74
00:03:52,160 --> 00:03:54,500
אחרת, מילת המפתח
הוא הפרד ומשול.

75
00:03:54,500 --> 00:03:58,310
לפצל את המערך למחצית ו
לחסל מחצית מהאלמנטים

76
00:03:58,310 --> 00:04:00,780
בכל פעם שככל שאתה מתקדם דרך.

77
00:04:00,780 --> 00:04:04,330
בגלל הפער הזה ומשול
ודברים פיצול במחצית גישה,

78
00:04:04,330 --> 00:04:07,450
זמן הריצה הגרוע ביותר
החיפוש בינארי שלו

79
00:04:07,450 --> 00:04:11,730
יומן n, שהוא באופן משמעותי
יותר טוב מn של החיפוש ליניארי.

80
00:04:11,730 --> 00:04:13,570
במקרה הטוב ביותר בזמן ריצה הוא עדיין אחד.

81
00:04:13,570 --> 00:04:17,010
>> אנו עלולים למצוא את זה באופן מיידי
פעם הראשונה שאנחנו עושים חלוקה, אבל,

82
00:04:17,010 --> 00:04:19,339
שוב, תזכור ש
למרות שהחיפוש בינארי הוא

83
00:04:19,339 --> 00:04:24,030
באופן משמעותי טוב יותר מחיפוש ליניארי
מכוח היותו יומן n לעומת n,

84
00:04:24,030 --> 00:04:27,110
אולי יש לך לעבור את העבודה
מיון המערך הראשון שלך, ש

85
00:04:27,110 --> 00:04:32,010
אולי לעשות את זה פחות יעיל בהתאם
בגודל של iterating מסודרים.

86
00:04:32,010 --> 00:04:35,250
>> אני דאג לויד, זה CS50.

87
00:04:35,250 --> 00:04:36,757