1
00:00:00,000 --> 00:00:11,270

2
00:00:11,270 --> 00:00:14,910
>> SPEAKER: خوب، این CS50 است.

3
00:00:14,910 --> 00:00:19,020
این پایان هفته سه است، و اگر
شما مزیت است برداشته نشده است در حال حاضر،

4
00:00:19,020 --> 00:00:21,790
می دانیم که وجود خواهد داشت ناهار
این جمعه به طور معمول، که در آن

5
00:00:21,790 --> 00:00:25,430
شما می توانید مکالمه خوب لذت ببرید
و مواد غذایی در آتش و یخ

6
00:00:25,430 --> 00:00:27,980
با برخی از در CS50
کارکنان و همکلاسی.

7
00:00:27,980 --> 00:00:30,170
سر در این URL را در اینجا.

8
00:00:30,170 --> 00:00:33,420
>> حالا شما ممکن است به یاد، و یا شما
ممکن است به زودی با آشنا می شود،

9
00:00:33,420 --> 00:00:35,970
این چیزها در اینجا، که
ها در پایان داده شده

10
00:00:35,970 --> 00:00:37,850
ترم برای کلاس های بسیاری از.

11
00:00:37,850 --> 00:00:40,870
به اصطلاح امتحان کتاب آبی، که در آن
شما ارسال پاسخ های خود را به آزمون.

12
00:00:40,870 --> 00:00:44,240
حالا من در اینجا 26 جمله
کتاب آبی، در هر یک از آنها

13
00:00:44,240 --> 00:00:47,580
نام، A از طریق Z. نوشته شده است و
در واقع نام هایی که ساده، A می باشد

14
00:00:47,580 --> 00:00:50,490
از طریق Z. و یکی از
اهداف در امروز دست

15
00:00:50,490 --> 00:00:53,910
در حال رفتن به ادامه چه
ما در روز دوشنبه آغاز شده است که نه

16
00:00:53,910 --> 00:00:57,830
خیلی به دنبال کد، اما واقعا
به دنبال ایده ها و حل مسئله.

17
00:00:57,830 --> 00:01:00,170
یکی از اهداف و
وعده های این دوره

18
00:01:00,170 --> 00:01:02,985
است که به شما یاد می دهد به فکر می کنم بیشتر
دقت، متد بیشتر،

19
00:01:02,985 --> 00:01:05,400
و برای حل مشکلات موثر تر است.

20
00:01:05,400 --> 00:01:09,526
و در واقع، ما می توانیم که واقعا
حتی بدون دست زدن به یک خط کد.

21
00:01:09,526 --> 00:01:12,150
بنابراین من یک زن و شوهر از فیل ها
تا امروز در اینجا، نارنجی و آبی،

22
00:01:12,150 --> 00:01:15,780
اگر ما می تواند یک داوطلب را دریافت کنید،
شاید از دورتر پشت از حد معمول.

23
00:01:15,780 --> 00:01:18,070
چگونه در مورد سمت راست وجود دارد، در آمده است.

24
00:01:18,070 --> 00:01:24,180
هدف از که در حال رفتن به به
کمک به اضافه اداره این آزمون است.

25
00:01:24,180 --> 00:01:24,935
نام شما چیست؟

26
00:01:24,935 --> 00:01:25,768
>> رسید مری بث.

27
00:01:25,768 --> 00:01:27,560
SPEAKER: مری بث، در آمده است.

28
00:01:27,560 --> 00:01:29,560
اجازه بدهید میکروفون دریافت در اینجا برای شما.

29
00:01:29,560 --> 00:01:32,172

30
00:01:32,172 --> 00:01:32,880
از ملاقات شما خوشبختم.

31
00:01:32,880 --> 00:01:34,005
>> رسید از ملاقات شما خوشبختم.

32
00:01:34,005 --> 00:01:36,790
SPEAKER: خوب، بنابراین من
اینجا کتاب آبی از طریق Z،

33
00:01:36,790 --> 00:01:41,680
و من قصد دارم به وانمود
من یکی از دانش آموزان،

34
00:01:41,680 --> 00:01:45,770
و آنها در آینده تا حدودی به صورت تصادفی
در پایان یک بلوک آزمون سه ساعت،

35
00:01:45,770 --> 00:01:49,400
به طوری که آنها در حال پایان دادن به در برخی از
منظور نیمه تصادفی مثل این.

36
00:01:49,400 --> 00:01:54,510
در حال حاضر کار خود را در یک لحظه در حال رفتن
به be-- این است که در واقع چگونه آنها را دریافت کنید

37
00:01:54,510 --> 00:01:56,820
در در پایان تبدیل شده
طبقه، به احتمال زیاد.

38
00:01:56,820 --> 00:02:01,120
شغل شما در حال حاضر در حال رفتن به، کاملا
به سادگی، به مرتب کردن این کتاب ها آبی برای ما

39
00:02:01,120 --> 00:02:05,220
از طریق Z.

40
00:02:05,220 --> 00:02:08,400
>> رسید آه، این است
رفتن به برای همیشه.

41
00:02:08,400 --> 00:02:13,747
>> SPEAKER: و ما را تماشا خواهد کرد
عنوان شما این کار را، بدون فشار.

42
00:02:13,747 --> 00:02:15,330
رسید: نه، هیچ فشار و یا هر چیزی.

43
00:02:15,330 --> 00:02:19,230

44
00:02:19,230 --> 00:02:23,570
>> SPEAKER: و برای تفریح،
اجازه دهید قرار دادن یک تایمر.

45
00:02:23,570 --> 00:02:26,680

46
00:02:26,680 --> 00:02:28,700
>> رسید سرگرم کننده بسیار، بسیار سرگرم کننده است.

47
00:02:28,700 --> 00:02:36,741

48
00:02:36,741 --> 00:02:38,574
>> SPEAKER: من می توانم میکروفن را برای شما نگه دارد.

49
00:02:38,574 --> 00:02:40,240
همه حق است، ما فقط دو برابر میشه سرعت ما.

50
00:02:40,240 --> 00:02:44,190

51
00:02:44,190 --> 00:02:49,060
بنابراین در عین حال، اجازه دهید من در برخواهد داشت چه
رفتن به این سوال برای مری بث

52
00:02:49,060 --> 00:02:51,540
است آنچه که او انجام می دهند، چگونه است
او در مورد حل این رفتن؟

53
00:02:51,540 --> 00:02:54,040
و در واقع، شما ممکن است
تا کنون در مورد چیزی فکر

54
00:02:54,040 --> 00:02:57,440
بسیار ساده به عنوان زمانی که شما انتخاب کنید
تا 26 کتاب شبیه به این،

55
00:02:57,440 --> 00:02:59,350
که یک طبیعی
دستور به آنها.

56
00:02:59,350 --> 00:03:01,335
روند چیست
که شما در واقع استفاده کنید؟

57
00:03:01,335 --> 00:03:03,770
آیا آن نسبتا تصادفی فقط
چیدن یکی از اولین را مشاهده می کنید

58
00:03:03,770 --> 00:03:05,250
و قرار دادن آن در محل خود را؟

59
00:03:05,250 --> 00:03:09,680
آیا شما برای اولین بار دست خود را در اطراف حرکت می کند
به دنبال پس از آن به دنبال B؟

60
00:03:09,680 --> 00:03:11,722
آیا شما نگاهی به
جفت از آنها را کنار به کنار هم

61
00:03:11,722 --> 00:03:14,680
و فقط می گویند، یک دقیقه صبر کنید، این
درست نیست، و پس از آن مبادله منظور؟

62
00:03:14,680 --> 00:03:16,960
ما در حال حاضر در روز دوشنبه شاهد
که تعدادی از راه های وجود دارد

63
00:03:16,960 --> 00:03:22,140
که در آن ما می توانیم این کار را انجام، و
در واقع همانطور که ما در پایان در اینجا،

64
00:03:22,140 --> 00:03:26,360
من توجه داشته باشید شاید را
از آنچه مری بث در حال انجام است.

65
00:03:26,360 --> 00:03:30,040
ما چند شمع به نظر می رسد،
بزرگتر از یک، سه کوچکتر است.

66
00:03:30,040 --> 00:03:33,790

67
00:03:33,790 --> 00:03:36,415
>> رسید من آنها را سفارش
هنگامی که دو حرف من

68
00:03:36,415 --> 00:03:39,540
که من می دانم با هم در یک رشته هستند،
من آنها را با هم قرار داده به طوری که من نمی

69
00:03:39,540 --> 00:03:42,915
باید در مورد حفظ نگران
آهنگ از یک ردیف کامل از کتاب.

70
00:03:42,915 --> 00:03:45,706
این فقط، آه، A برای اولین بار،
من این پشته کردم اینجا.

71
00:03:45,706 --> 00:03:47,580
SPEAKER: بنابراین، تقریبا شبیه
قطعات پازل است که

72
00:03:47,580 --> 00:03:49,860
به شکل سمت راست به
مطابقت با هر یک از دیگر.

73
00:03:49,860 --> 00:03:51,026
رسید بسیار زیبا، آره.

74
00:03:51,026 --> 00:03:55,320
SPEAKER: OK، عالی است.

75
00:03:55,320 --> 00:03:59,850
و در حال حاضر هر یک از این
شمع است که احتمالا طبقه بندی شده اند؟

76
00:03:59,850 --> 00:04:00,990
>> رسید آره.

77
00:04:00,990 --> 00:04:09,900
>> SPEAKER: خوب، از طریق Z. تمام
راست، تبریک می گویم، شما آن را انجام داد.

78
00:04:09,900 --> 00:04:11,461
شما باید انتخاب کنید.

79
00:04:11,461 --> 00:04:11,960
آبی؟

80
00:04:11,960 --> 00:04:13,530
خوب، با تشکر از شما برای آن.

81
00:04:13,530 --> 00:04:16,679
بنابراین مری بث پیشنهاد
چه روش او بود،

82
00:04:16,679 --> 00:04:19,720
اما چه روش دیگری است که چگونه شما
ممکن است در مورد مرتب سازی این چیزها برود؟

83
00:04:19,720 --> 00:04:21,130
چه شما انجام داده اند؟

84
00:04:21,130 --> 00:04:24,060
رکورد به ضرب و شتم می شده اند
یک دقیقه و 50 ثانیه یا بیشتر،

85
00:04:24,060 --> 00:04:26,039
به علاوه آنهایی که من را فراموش کرده به تعداد.

86
00:04:26,039 --> 00:04:27,080
چه شما انجام داده اند؟

87
00:04:27,080 --> 00:04:27,579
آره؟

88
00:04:27,579 --> 00:04:28,735
رسید را از پشته.

89
00:04:28,735 --> 00:04:29,776
شروع از ابتدا.

90
00:04:29,776 --> 00:04:32,284
مقالات خود را بررسی کنید.

91
00:04:32,284 --> 00:04:36,586
و اگر یکی از بالا بالاتر است
از، شاید، آنها،

92
00:04:36,586 --> 00:04:38,980
یکی از پایین است
بالاتر، و سپس آنها را تغییر دهید.

93
00:04:38,980 --> 00:04:41,300
>> SPEAKER: OK، بنابراین شروع
در بالا و پایین،

94
00:04:41,300 --> 00:04:43,716
و پس از آن کار راه خود را
به سمت داخل می خواهم که آنها را مبادله؟

95
00:04:43,716 --> 00:04:46,580
OK، بنابراین کمی مشابه
در روح به نوعی حباب،

96
00:04:46,580 --> 00:04:49,160
اما انتخاب افراط
نه جفت مجاور.

97
00:04:49,160 --> 00:04:52,080
اما کوتاه از آن است که وجود دارد این است که
مطمئنا یک دسته از راه های مختلف

98
00:04:52,080 --> 00:04:54,210
ما می توانیم این کار را انجام، و
رک و پوست کنده، من فکر می کنم شما نوع

99
00:04:54,210 --> 00:04:55,700
اتخاذ یک زن و شوهر روش، درست است؟

100
00:04:55,700 --> 00:05:00,567
شما ساخته شده مرتب کردن بر اساس چهار شمع مرتب شده، و
پس از آن به طور موثر آنها را با هم ادغام شدند.

101
00:05:00,567 --> 00:05:02,650
و این، اعتقاد داشتن، یکی دیگر از
روش در دسترس نباشد.

102
00:05:02,650 --> 00:05:06,950
شما آن را به عنوان یک شمع بزرگ درمان نیست،
شما این مشکل را به چهار مربع تقسیم شده است،

103
00:05:06,950 --> 00:05:09,820
اگر شما خواهد شد، و پس از آن به نحوی
آنها در پایان هم ادغام شدند.

104
00:05:09,820 --> 00:05:13,410
>> بنابراین اجازه دهید در نظر بگیرید، در نهایت،
به چه روش دیگری که ممکن است انجام این کار.

105
00:05:13,410 --> 00:05:15,860
ما رسمیت مفهوم
حباب مرتب کردن بر اساس آخرین بار،

106
00:05:15,860 --> 00:05:18,780
و فراخوان مرتب سازی حبابی بود
الگوریتمی که ما مشاهده

107
00:05:18,780 --> 00:05:22,640
با هشت نفر از همکلاسی های خود را در اینجا،
به ظاهر به صورت تصادفی در اولین طبقه بندی شده اند.

108
00:05:22,640 --> 00:05:26,110
و ما پس از آن تصمیم گرفت دو به دو، اگر
دو عنصر از نظم،

109
00:05:26,110 --> 00:05:26,950
به سادگی آنها را مبادله.

110
00:05:26,950 --> 00:05:28,930
پس از چهار و دو
بدیهی است از نظم،

111
00:05:28,930 --> 00:05:31,080
بنابراین این دو همکلاسی
مواضع روشن باشد.

112
00:05:31,080 --> 00:05:35,390
و بعد ما با چهار و شش تکرار،
پس از آن شش و هشت، در هر تکرار،

113
00:05:35,390 --> 00:05:36,980
در حال حرکت به سمت راست.

114
00:05:36,980 --> 00:05:42,590
>> بنابراین با توجه به هشت نفر، چند دو به دو
مقایسه به من در حالی که راه رفتن را از انجام

115
00:05:42,590 --> 00:05:45,220
از چپ به راست در یک تکرار است؟

116
00:05:45,220 --> 00:05:48,410
چند مقایسه؟

117
00:05:48,410 --> 00:05:49,197
هفت، درست است؟

118
00:05:49,197 --> 00:05:51,405
از آنجا که اگر هشت وجود دارد
مردم اما شما باید این جفت ارز

119
00:05:51,405 --> 00:05:53,880
آنها را و شما در حفظ و در حال حرکت
یکی به سمت راست هاپ،

120
00:05:53,880 --> 00:05:56,060
شما نمی خواهید به هشت
مقایسه، زیرا شما نمی توانید به مقایسه

121
00:05:56,060 --> 00:05:59,226
یک عنصر در برابر خود را، و یا آن را
فقط بی معنی است، بنابراین شما باید هفت.

122
00:05:59,226 --> 00:06:01,290
یا به طور کلی اگر،
ما n نفر، ما

123
00:06:01,290 --> 00:06:04,300
انجام نفر منهای 1 مقایسه
با مرتب سازی حبابی.

124
00:06:04,300 --> 00:06:08,150
>> بنابراین اجازه دهید در حال حاضر در نظر چقدر خوب یا
حباب بد مرتب کردن بر اساس واقع بود، و سعی کنید

125
00:06:08,150 --> 00:06:13,570
به خودمان واژگان را با
که به الگوریتم نقد مانند این،

126
00:06:13,570 --> 00:06:14,430
و به زودی خود ما.

127
00:06:14,430 --> 00:06:16,970
بنابراین پاس برای اولین بار از طریق
مرتب سازی حبابی، اولین بار

128
00:06:16,970 --> 00:06:20,909
من از چپ به راست در سراسر راه می رفت
مرحله، من نفر منهای 1 مقایسه صورت گرفت.

129
00:06:20,909 --> 00:06:22,950
و این رفتن به من
واحد اندازه گیری، درست است؟

130
00:06:22,950 --> 00:06:26,170
من نوع صحبت کردن و قدم زدن،
تا حدودی سریع، تا حدودی کند،

131
00:06:26,170 --> 00:06:29,300
بنابراین شمارش تعداد من از ثانیه
به خصوص گفتن نیست،

132
00:06:29,300 --> 00:06:32,260
اما شمارش تعداد
عملیات که من در روز دوشنبه انجام داد،

133
00:06:32,260 --> 00:06:35,900
مقایسه دو نفر، که احساس می کند
مانند یک واحد زیبا از اندازه گیری.

134
00:06:35,900 --> 00:06:40,980
>> بنابراین نفر منهای 1 مراحل اولین بار،
اما بعد از آن چه پس از آن رخ داده است؟

135
00:06:40,980 --> 00:06:46,610
یک حرکت صعودی یک پاس ها
از طریق یک لیست در غیر این صورت خشک جدانشده؟

136
00:06:46,610 --> 00:06:49,840
چه می تواند به شما من در مورد عنصر بگویید
که تمام راه را بیش از وجود دارد بود؟

137
00:06:49,840 --> 00:06:51,300
آره؟

138
00:06:51,300 --> 00:06:52,870
این بزرگترین عنصر بود، درست است؟

139
00:06:52,870 --> 00:06:55,710
شماره هشت، حتی اگر او
آغاز شده در اینجا، هر بار که من

140
00:06:55,710 --> 00:06:57,860
خود را در برابر مقایسه
همسایه، او را نگه داشته

141
00:06:57,860 --> 00:07:00,480
حباب تا به سمت راست
سمت از لیست.

142
00:07:00,480 --> 00:07:02,710
و در واقع، که در آن
الگوریتم نام خود را.

143
00:07:02,710 --> 00:07:07,630
>> در حال حاضر با این منطق، که چگونه بسیاری از مقایسه
نیاز من در زمان دوم را

144
00:07:07,630 --> 00:07:09,800
من را که پاس از چپ به راست؟

145
00:07:09,800 --> 00:07:10,730
نفر منهای 2، درست است؟

146
00:07:10,730 --> 00:07:14,297
این فقط می خواهد به هدر رفتن زمان می شود من اگر من
نگه داشتن نسبت هشت برابر کسی

147
00:07:14,297 --> 00:07:16,630
دیگری چون ما از قبل می دانیم
او در جای مناسب بود.

148
00:07:16,630 --> 00:07:19,760
به طوری که یک بیت از این
بهینه سازی، پس پاس بعدی

149
00:07:19,760 --> 00:07:23,899
در حال رفتن به همراه نفر منهای دو مرحله،
که در آن n تعداد زیادی از مردم است.

150
00:07:23,899 --> 00:07:26,940
در حال حاضر شما می توانید نوع قیاس، حتی
اگر شما یک دانشمند کامپیوتر نیست،

151
00:07:26,940 --> 00:07:27,680
چگونه این به پایان می رسد.

152
00:07:27,680 --> 00:07:31,259
در پایان این الگوریتم، احتمالا
شما فقط یک مقایسه را ترک کردم.

153
00:07:31,259 --> 00:07:33,800
شما باید به نوع تعمیر
شروع از لیست در مورد دو

154
00:07:33,800 --> 00:07:36,540
و یکی از سفارش
و باید یک و دو است،

155
00:07:36,540 --> 00:07:40,330
بنابراین این کف در
به علاوه 1 مقایسه نهایی است.

156
00:07:40,330 --> 00:07:44,500
>> در حال حاضر این نقطه، نقطه، نقطه نوع از امواج آن
دست در برخی از جزئیات juicier،

157
00:07:44,500 --> 00:07:46,452
اما اجازه دهید فقط به جلو و ساده.

158
00:07:46,452 --> 00:07:48,660
اگر شما از بالا به یاد
مدرسه، رک و پوست کنده، که بسیاری از شما

159
00:07:48,660 --> 00:07:50,340
کتاب های ریاضی به حال است که حال
بازی ورق کمی

160
00:07:50,340 --> 00:07:52,550
بر روی جلد جلو یا
پشت جلد است که شما نشان داد

161
00:07:52,550 --> 00:07:56,400
جمع آنچه که سری مانند
این در نهایت به اضافه شده است.

162
00:07:56,400 --> 00:07:59,600
در حالت کلی، اگر شما یک
متغیر مانند نفر، و در واقع این یکی،

163
00:07:59,600 --> 00:08:01,634
اگر شما در نگاه شما
کتاب ریاضی مدرسه قدیمی،

164
00:08:01,634 --> 00:08:04,050
شما می توانید ببینید که این در واقع
اضافه می کند تا این مبلغ در اینجا،

165
00:08:04,050 --> 00:08:07,970
n بار نفر منهای 1 تمام 2 تقسیم شده است.

166
00:08:07,970 --> 00:08:11,172
بنابراین در حال حاضر اجازه دهید تصریح
این درست است، به همین ترتیب کبیسه از ایمان،

167
00:08:11,172 --> 00:08:12,880
این چیزی است که این مبالغ
تا، و ما می توانیم

168
00:08:12,880 --> 00:08:14,341
ثابت کنند که در یک حالت کلی است.

169
00:08:14,341 --> 00:08:15,590
اما در حال حاضر اجازه دهید این گسترش است.

170
00:08:15,590 --> 00:08:19,920
بنابراین اجازه دهید این را چند برابر می کند، به طوری که
تعداد مربع، منهای نفر، تقسیم بر 2.

171
00:08:19,920 --> 00:08:23,200
این واقعا ازت مربع،
تقسیم بر 2، منهای نفر بیش از 2،

172
00:08:23,200 --> 00:08:25,010
به طوری که همه خوب و جالب است.

173
00:08:25,010 --> 00:08:27,060
اما چه اتفاقی می افتد اگر ما
در حال حاضر پلاگین در ارزش؟

174
00:08:27,060 --> 00:08:29,724
فرض کنید من هشت ندارد
مردم، اما می گویند یک میلیون نفر است.

175
00:08:29,724 --> 00:08:31,890
و یک میلیون فقط به خاطر
آن تعداد بسیار بزرگ است،

176
00:08:31,890 --> 00:08:34,039
اجازه دهید که در به برق وصل کنید و ببینید چه اتفاقی می افتد.

177
00:08:34,039 --> 00:08:39,039
بنابراین اگر من به برق وصل از یک میلیون به آن فرمول
من قصد دارم به یک میلیون مربع،

178
00:08:39,039 --> 00:08:42,868
تقسیم بر 2، منهای یک
میلیون، تقسیم بر 2.

179
00:08:42,868 --> 00:08:44,159
در حال حاضر چه چیزی است که رفتن به یکسانند؟

180
00:08:44,159 --> 00:08:47,354
بنابراین 500 میلیارد، منهای 500،000.

181
00:08:47,354 --> 00:08:49,270
و اگر من در واقع انجام
که ریاضی را، که به معنی

182
00:08:49,270 --> 00:08:53,920
که مرتب سازی بر یک میلیون
افراد مبتلا به نوعی حباب

183
00:08:53,920 --> 00:09:01,800
ممکن است من را 499،999،500،000
مراحل و یا مقایسه در پایان،

184
00:09:01,800 --> 00:09:02,900
ما فقط برونیابش.

185
00:09:02,900 --> 00:09:06,860
>> که احساس می کند بسیار آهسته، اما رک و پوست کنده
اندازه گیری یک ورودی خاص

186
00:09:06,860 --> 00:09:09,160
مثل این است، که همه گفتن نیست.

187
00:09:09,160 --> 00:09:14,050
اما در واقع آن نشان می دهد که به عنوان نفر
می شود بزرگتر و بزرگتر، این الگوریتم

188
00:09:14,050 --> 00:09:16,280
نوع احساس بدتر و
بدتر از آن، یا شما واقعا

189
00:09:16,280 --> 00:09:20,450
شروع به احساس درد است که
به توان رساندن، که تعداد مربع،

190
00:09:20,450 --> 00:09:21,770
که اضافه می کند تا بسیار سریع می باشد.

191
00:09:21,770 --> 00:09:25,340
و این جزئیات نیست
از دست داده به مردم، در واقع

192
00:09:25,340 --> 00:09:29,640
چند سال پیش یک سناتور خاصی که بود
مبارزات انتخاباتی، به پایین برای مصاحبه نشسته

193
00:09:29,640 --> 00:09:32,180
با اریک گوگل
اشمیت، مدیر عامل شرکت در آن زمان،

194
00:09:32,180 --> 00:09:36,380
و با یک سوال به چالش کشیده شد
بسیار شبیه ما امروز کاوش.

195
00:09:36,380 --> 00:09:38,468
اجازه دهید یک نگاه.

196
00:09:38,468 --> 00:09:45,280
>> [VIDEO پخش]

197
00:09:45,280 --> 00:09:48,560
>> -Senator، شما در اینجا
در گوگل، و من دوست دارم

198
00:09:48,560 --> 00:09:53,382
به ریاست جمهوری فکر می کنم
به عنوان یک مصاحبه شغلی.

199
00:09:53,382 --> 00:09:56,434
در حال حاضر، آن را سخت برای به دست آوردن
یک کار به عنوان رئيس جمهور،

200
00:09:56,434 --> 00:09:58,100
و شما در حال رفتن را از طریق لرز در حال حاضر.

201
00:09:58,100 --> 00:10:01,860
این هم سخت به یک کار در گوگل.

202
00:10:01,860 --> 00:10:05,490
ما سوالات، و ما
سوالات نامزدها را مطرح کنید،

203
00:10:05,490 --> 00:10:09,770
و این یکی از لری Schwimmer است.

204
00:10:09,770 --> 00:10:14,760
What-- شما بچه ها فکر می کنم من
شوخی، آن را در اینجا ببینید.

205
00:10:14,760 --> 00:10:17,930
کارآمدترین روش برای چیست
مرتب سازی بر اساس یک میلیون عدد صحیح 32 بیتی؟

206
00:10:17,930 --> 00:10:21,800

207
00:10:21,800 --> 00:10:24,350
>> -Well--

208
00:10:24,350 --> 00:10:25,200
>> -I'm عرض پوزش، maybe--

209
00:10:25,200 --> 00:10:27,400
>> نه، نه، نه.

210
00:10:27,400 --> 00:10:30,700
من فکر می کنم نوعی حباب
خواهد بود که راه را اشتباه رفتن است.

211
00:10:30,700 --> 00:10:34,165

212
00:10:34,165 --> 00:10:38,180
>> بیا در، که او را به این گفت؟

213
00:10:38,180 --> 00:10:40,590
من کامپیوتر را مشاهده کنید
علم در پس زمینه خود را.

214
00:10:40,590 --> 00:10:42,130
>> -We've جاسوس ما در وجود دارد.

215
00:10:42,130 --> 00:10:44,930

216
00:10:44,930 --> 00:10:48,444
>> -OK، اجازه دهید بپرسم مختلف
پرسش مصاحبه.

217
00:10:48,444 --> 00:10:49,300
>> [END VIDEO پخش]

218
00:10:49,300 --> 00:10:52,290
>> SPEAKER: بنابراین صحبت کردن در مورد
شماره های خاص هر چند،

219
00:10:52,290 --> 00:10:53,890
نمی شود که همه مفید است.

220
00:10:53,890 --> 00:10:56,810
این یک درس زندگی که حباب ندارد
مرتب کردن بر اساس، با توجه به یک میلیون ورودی،

221
00:10:56,810 --> 00:10:58,590
ممکن است به عنوان بسیاری از 500 میلیارد مراحل را.

222
00:10:58,590 --> 00:11:01,120
شما واقعا نمی تواند تعمیم
بیش از حد به طور موثر از آن

223
00:11:01,120 --> 00:11:03,560
و تصمیم گیری طراحی خوب
هنگام نوشتن برنامه.

224
00:11:03,560 --> 00:11:07,070
بنابراین اجازه دهید تمرکز هر چند در مورد چگونگی
ما ممکن است این نتیجه را ساده کنید.

225
00:11:07,070 --> 00:11:11,780
>> بنابراین من به رنگ زرد برجسته در اینجا
در نتیجه n را به 2 تقسیم به توان،

226
00:11:11,780 --> 00:11:14,330
تا یک میلیون مربع
تقسیم بر 2، و پس از آن

227
00:11:14,330 --> 00:11:16,710
I برجسته ام چه
پاسخ نهایی

228
00:11:16,710 --> 00:11:20,180
زمانی که ما کم کردن n را به 2 تقسیم شده است.

229
00:11:20,180 --> 00:11:24,850
و این ادعا من قصد دارم به ساعت است،
که هک مراقبت اگر شما تفریق کردن

230
00:11:24,850 --> 00:11:30,060
تعداد کمی قدیمی بیش از 2 زمانی که برای اولین بار از
بخشی از این فرمول، بسیار بزرگتر است؟

231
00:11:30,060 --> 00:11:33,910
این غالب دیگر
مدت، نفر به توان تقسیم بر 2

232
00:11:33,910 --> 00:11:37,510
بسیار بزرگتر است، به وضوح، به عنوان
نفر می شود بزرگ مانند یک میلیون،

233
00:11:37,510 --> 00:11:41,450
که واقعا وجود دارد یک اختلاف بزرگ در
در پایان از روز بین 500 میلیارد

234
00:11:41,450 --> 00:11:45,730
و 499999500000؟

235
00:11:45,730 --> 00:11:46,349
نه واقعا.

236
00:11:46,349 --> 00:11:48,640
و به این ترتیب آنچه که ما در حال رفتن به
انجام به عنوان دانشمندان کامپیوتر است

237
00:11:48,640 --> 00:11:53,270
این عبارات منظور پایین و چشم پوشی از
چیزی شبیه به این و واقعا

238
00:11:53,270 --> 00:11:56,050
فقط آن را ساده به
مدت که رفتن به مهم.

239
00:11:56,050 --> 00:12:00,315
بزرگتر مجموعه داده های ما، بزرگتر
پایگاه های داده ما را دریافت کنید، صفحات وب را بیشتر

240
00:12:00,315 --> 00:12:02,690
ما باید به جستجو، بیشتر
دوستان شما در فیس بوک است.

241
00:12:02,690 --> 00:12:07,340
>> همانطور که n بزرگتر می شود، ما واقعا هستیم
رفتن به مورد بزرگترین مراقبت

242
00:12:07,340 --> 00:12:11,560
مدت در هر تجزیه و تحلیل چنین از
عملکرد الگوریتم ما.

243
00:12:11,560 --> 00:12:16,230
و من قصد دارم برای گفتن، شما می دانید چه،
مرتب سازی حبابی در دستور O بزرگ است،

244
00:12:16,230 --> 00:12:18,060
به سفارش از n مربع.

245
00:12:18,060 --> 00:12:20,090
این دقیقا همان نفر نمی
مربع که ما دیده ایم،

246
00:12:20,090 --> 00:12:22,060
اما که واقعا اهمیت بده
در مورد آن نظر کوچکتر،

247
00:12:22,060 --> 00:12:24,390
و رک و پوست کنده، که واقعا
مراقبت اگر ما 2 تقسیم؟

248
00:12:24,390 --> 00:12:25,870
این تنها یک ضریب ثابت است.

249
00:12:25,870 --> 00:12:29,480
و 500 میلیارد برابر 250 است
میلیارد واقعا که بزرگ از یک معامله؟

250
00:12:29,480 --> 00:12:32,190
من فقط می تواند یک سال صبر،
اجازه دهید لپ تاپ من به معنای واقعی کلمه

251
00:12:32,190 --> 00:12:34,810
دریافت در سخت افزار با دو برابر سرعت،
و این نوع از تفاوت

252
00:12:34,810 --> 00:12:36,650
فقط از بین می رود به طور طبیعی در طول زمان.

253
00:12:36,650 --> 00:12:39,300
>> آنچه ما در مورد مراقبت است
بیان، بخش

254
00:12:39,300 --> 00:12:42,489
از بیان که رفتن به متفاوت باشد
به عنوان ورودی ما بزرگتر و بزرگتر می شود.

255
00:12:42,489 --> 00:12:45,280
و در واقع، در دنیای واقعی،
این چیزی است که اتفاق می افتد به طور فزاینده

256
00:12:45,280 --> 00:12:48,330
است که ورودی به مشکلات ما و
الگوریتم های در حال گرفتن بزرگتر است.

257
00:12:48,330 --> 00:12:53,470
بنابراین O بزرگ است برای رفتن به نماد،
نماد مجانبی، که ما فقط

258
00:12:53,470 --> 00:12:57,160
استفاده به عنوان دانشمندان کامپیوتر برای توصیف
عملکرد، و یا هم در حال اجرا،

259
00:12:57,160 --> 00:12:58,130
یک الگوریتم.

260
00:12:58,130 --> 00:13:00,800
به طوری که ما می توانیم الگوریتم مقایسه
در رایانه های مختلف نوشته شده است

261
00:13:00,800 --> 00:13:04,170
افراد مختلف، با استفاده از
برخی از متریک اساسا مشابه

262
00:13:04,170 --> 00:13:07,557
مانند تعداد مقایسه های شما
ساخت، و یا شاید تعداد سواپ

263
00:13:07,557 --> 00:13:08,140
شما در حال ساخت.

264
00:13:08,140 --> 00:13:11,910
>> چه ما به نمی
تعداد دفعات مشاهده شده مقدار زمان است

265
00:13:11,910 --> 00:13:13,981
که می گذرد در حالی که ساعت
بر روی دیوار به طور معمول.

266
00:13:13,981 --> 00:13:16,230
چیزی که ما در حال رفتن نیست که نگران باشید
در مورد حافظه چقدر است

267
00:13:16,230 --> 00:13:17,820
شما با استفاده از امروز در
حداقل، هر چند که

268
00:13:17,820 --> 00:13:19,370
یکی دیگر از منابع ما ممکن است اندازه گیری.

269
00:13:19,370 --> 00:13:23,610
ما قصد داریم به تلاش برای پایه تجزیه و تحلیل ما
فقط در عملیات اساسی، آنهایی،

270
00:13:23,610 --> 00:13:25,930
رک و پوست کنده، که شما می توانید بیشتر بصری را ببینید.

271
00:13:25,930 --> 00:13:30,700
بنابراین با چیزی شبیه به O بزرگ از n
مربع، من ادعا می کنند که O از n به توان

272
00:13:30,700 --> 00:13:35,820
است بالا در به اصطلاح محدود
زمان مرتب سازی حبابی در حال اجرا.

273
00:13:35,820 --> 00:13:38,820
به عبارت دیگر، اگر شما
می خواستم به ادعا وجود دارد که

274
00:13:38,820 --> 00:13:41,370
این حد بالا در مورد چگونگی بسیاری از
مراحل یک الگوریتم ممکن را،

275
00:13:41,370 --> 00:13:46,240
آن را به در O بزرگ از n باشد
مربع در این مورد، یک حد بالا.

276
00:13:46,240 --> 00:13:49,710
>> اگر من به جای تغییر
داستان نمی شود در مورد نوع حباب،

277
00:13:49,710 --> 00:13:50,910
اما در مورد این حد بالا.

278
00:13:50,910 --> 00:13:54,030
آیا می توانید از یک الگوریتم فکر می کنم
که ما در حال حاضر نگاه

279
00:13:54,030 --> 00:13:59,530
که حد بالای، حداکثر
اندازه گیری از زمان و یا عملیات،

280
00:13:59,530 --> 00:14:04,300
می توان گفت که محدود شود
توسط n، یک تابع خطی،

281
00:14:04,300 --> 00:14:07,260
نه یک درجه دوم که منحنی؟

282
00:14:07,260 --> 00:14:10,780
الگوریتم آن چیست
همیشه طول می کشد بیش

283
00:14:10,780 --> 00:14:12,860
از مثل مراحل نفر، یا
مراحل ها 2n، و یا مراحل 3N؟

284
00:14:12,860 --> 00:14:13,360
آره؟

285
00:14:13,360 --> 00:14:15,030
>> رسید پیدا کردن
بزرگترین عدد در یک لیست؟

286
00:14:15,030 --> 00:14:16,930
>> SPEAKER: پرفکت، پیدا کردن
بزرگترین عدد در یک لیست.

287
00:14:16,930 --> 00:14:18,940
اگر من داده من یک لیست از
مردم به عنوان مثال،

288
00:14:18,940 --> 00:14:21,440
هر یک از که برگزاری یک عدد،
چه حداکثر تعداد است

289
00:14:21,440 --> 00:14:23,770
از مراحل آن را باید من را،
یک فرد منطقی هوشمند،

290
00:14:23,770 --> 00:14:27,530
برای پیدا کردن بزرگترین شخص در آن لیست؟

291
00:14:27,530 --> 00:14:28,100
نفر، درست است؟

292
00:14:28,100 --> 00:14:31,320
از آنجا که در بدترین حالت، که در آن
ممکن است بزرگترین ارزش است؟

293
00:14:31,320 --> 00:14:32,700
راست، تمام راه را در پایان.

294
00:14:32,700 --> 00:14:34,575
پس در بدترین حالت
محدود بالا، من ممکن است

295
00:14:34,575 --> 00:14:36,450
باید به تمام راه
در اینجا و مانند باشد،

296
00:14:36,450 --> 00:14:39,170
آه، اینجا تعداد هشت است،
و یا هر آنچه که ارزش است.

297
00:14:39,170 --> 00:14:41,330
در حال حاضر آن را فقط احمق است
اگر من حفظ رفتن، درست است؟

298
00:14:41,330 --> 00:14:43,840
در حال جستجو برای عناصر بیشتر و بیشتر
اگر آخرین از آنها بیش از وجود دارد؟

299
00:14:43,840 --> 00:14:45,340
پس مطمئنا، نفر یک حد بالا است.

300
00:14:45,340 --> 00:14:47,420
من لازم نیست به
مراحل بیشتر از آن.

301
00:14:47,420 --> 00:14:51,580
>> بنابراین اگر به جای من پیشنهاد کرد که
الگوریتم در این جهان وجود دارد که

302
00:14:51,580 --> 00:14:57,750
یک زمان در حال اجرا است که
محدود O بزرگ log n است، ورود نفر؟

303
00:14:57,750 --> 00:15:00,390
از کجا این دیده می شود که قبل از؟

304
00:15:00,390 --> 00:15:00,890
آره؟

305
00:15:00,890 --> 00:15:03,309
>> رسید در مشکل دفترچه تلفن؟

306
00:15:03,309 --> 00:15:04,850
SPEAKER: مانند مشکل دفترچه تلفن.

307
00:15:04,850 --> 00:15:07,754
میزان چه بود
زمان زیادی و یا چگونه بسیاری از اشک آن

308
00:15:07,754 --> 00:15:10,170
در زمان من برای پیدا کردن کسی مثل
مایک اسمیت در دفترچه تلفن؟

309
00:15:10,170 --> 00:15:13,212
ما ادعا را log n است، و
حتی اگر نا آشنا و یا آن را از آن

310
00:15:13,212 --> 00:15:15,170
مبهم و مه آلود کمی چه
لگاریتم و یا توان بود،

311
00:15:15,170 --> 00:15:17,650
فقط به یاد داشته باشید که log n است
به طور کلی به روند اشاره دارد،

312
00:15:17,650 --> 00:15:20,790
در این مورد، از تقسیم
چیزی در نیم دوباره، و دوباره،

313
00:15:20,790 --> 00:15:25,790
و دوباره، و دوباره، به طوری که آن را به
می شود به طور فزاینده ای کوچک به عنوان شما انجام دهد.

314
00:15:25,790 --> 00:15:28,470
>> بنابراین ورود از n اشاره دارد، مطمئن،
به عنوان مثال دفترچه تلفن،

315
00:15:28,470 --> 00:15:32,662
به جستجوی دودویی در تئوری، زمانی که ما
درب های مجازی در هیئت مدیره به حال،

316
00:15:32,662 --> 00:15:34,370
و یا زمانی که شان بود
جستجو برای چیزی.

317
00:15:34,370 --> 00:15:37,374
اگر او جستجوی دودویی استفاده کرده بودند، وارد سیستم شوید نفر
خواهد بود که حد بالا چه مقدار

318
00:15:37,374 --> 00:15:38,040
زمانی که طول می کشد.

319
00:15:38,040 --> 00:15:44,027
اما این الگوریتم که در زد
ورود به سیستم نفر در نظر گرفته شده چه جزئیات کلیدی؟

320
00:15:44,027 --> 00:15:45,360
این لیست، راست طبقه بندی شده اند شد؟

321
00:15:45,360 --> 00:15:47,789
الگوریتم شما اشتباه است اگر است
ورودی شما طبقه بندی شده اند نیست،

322
00:15:47,789 --> 00:15:49,830
و در عین حال شما با استفاده از
چیزی شبیه به جستجوی دودویی

323
00:15:49,830 --> 00:15:51,704
دلیل این که شما ممکن است پرش
حق بر عنصر

324
00:15:51,704 --> 00:15:53,600
بدون اینکه متوجه آن وجود دارد.

325
00:15:53,600 --> 00:15:55,600
>> در حال حاضر چه ممکن است این به این معنی، O بزرگ یک؟

326
00:15:55,600 --> 00:15:59,117
این به این معنی نیست که الگوریتم شما
طول می کشد و تنها یک مرحله،

327
00:15:59,117 --> 00:16:01,200
این فقط به معنی آن طول می کشد
تعداد ثابت قدم.

328
00:16:01,200 --> 00:16:04,060
شاید آن را به 1، شاید آن را
10، شاید آن را 1000،

329
00:16:04,060 --> 00:16:07,750
اما آن را مستقل از
اندازه مشکل است.

330
00:16:07,750 --> 00:16:10,850
مهم نیست که چقدر بزرگ n است،
یک الگوریتم زمان ثابت

331
00:16:10,850 --> 00:16:12,747
همیشه طول می کشد به همان تعداد از مرحله.

332
00:16:12,747 --> 00:16:15,080
پس چه ممکن است یک الگوریتم
ما در مورد یا فقط صحبت کرده ام

333
00:16:15,080 --> 00:16:20,418
به طور مستقیم است که به شما می آید که
همیشه در زمان ثابت به اصطلاح اجرا می شود؟

334
00:16:20,418 --> 00:16:20,918
آره؟

335
00:16:20,918 --> 00:16:22,001
>> رسید اضافه کردن دو عدد.

336
00:16:22,001 --> 00:16:25,320
SPEAKER: اضافه کردن دو عدد،
2 به علاوه 2 برابر 4، انجام می شود.

337
00:16:25,320 --> 00:16:27,227
به طوری که ممکن است کار کند، چه چیز دیگری؟

338
00:16:27,227 --> 00:16:28,560
چگونه در مورد جهان واقعی، آره؟

339
00:16:28,560 --> 00:16:30,686
>> رسید پیدا کردن
اولین چیزی که در یک لیست.

340
00:16:30,686 --> 00:16:32,810
SPEAKER: پیدا کردن اولین
عنصر در یک لیست، اطمینان حاصل کنید.

341
00:16:32,810 --> 00:16:34,540
ما در واقع صحبت شده است
در مورد آرایه ها در حال حاضر،

342
00:16:34,540 --> 00:16:36,540
چگونه می توانم به شما در دریافت
اولین عنصر در یک آرایه،

343
00:16:36,540 --> 00:16:40,465
مهم نیست چه مدت
آرایه در کد C است؟

344
00:16:40,465 --> 00:16:43,090
شما درست مثل طبقه بندی استفاده کنید
صفر نماد، بم، شما وجود دارد.

345
00:16:43,090 --> 00:16:46,120
و در واقع آرایه ها، به عنوان یک به کنار،
پشتیبانی چیزی به طور کلی شناخته شده

346
00:16:46,120 --> 00:16:49,240
به عنوان دسترسی تصادفی، دسترسی تصادفی
حافظه، دلیل این که شما به معنای واقعی کلمه می تواند

347
00:16:49,240 --> 00:16:50,284
پرش به یک محل.

348
00:16:50,284 --> 00:16:52,700
ما می توانیم این را حتی بیشتر به سادگی انجام
ما می توانیم به هفته صفر عقب

349
00:16:52,700 --> 00:16:53,900
هنگامی که ما خراش بود.

350
00:16:53,900 --> 00:16:59,707
چه مدت آن را برای کشید
می گویند بلوک در ابتدا برای اجرای؟

351
00:16:59,707 --> 00:17:00,790
فقط زمان ثابت، درست است؟

352
00:17:00,790 --> 00:17:03,960
چیزی می گویند، می گویند
چیزی، مهم نیست

353
00:17:03,960 --> 00:17:07,359
چگونه خش بزرگ جهان است، آن را همیشه
رفتن به همان مقدار از زمان

354
00:17:07,359 --> 00:17:08,490
به سادگی به چیزی می گویند.

355
00:17:08,490 --> 00:17:11,089
>> به طوری که زمان ثابت است،
اما آنچه در سمت تلنگر است؟

356
00:17:11,089 --> 00:17:13,030
در صورتی که رو به بالا بود
مرزهای، چه می شود اگر ما می خواهیم

357
00:17:13,030 --> 00:17:17,089
برای توصیف محدوده پایین تر
از الگوریتم های زمان ما در حال اجرا؟

358
00:17:17,089 --> 00:17:19,852
تقریبا یک بهترین حالت
به طور بالقوه، اگر شما خواهد شد،

359
00:17:19,852 --> 00:17:23,060
هر چند این شرایط می تواند به بهترین اعمال
موارد، بدترین موارد، موارد متوسط ​​بیش

360
00:17:23,060 --> 00:17:26,359
به طور کلی، اما اجازه دهید فقط تمرکز
در مرزهای پایین تر به طور کلی.

361
00:17:26,359 --> 00:17:31,920
یک الگوریتم است که چه
پایینی از مراحل نفر،

362
00:17:31,920 --> 00:17:33,350
و یا مراحل ها 2n، و یا مراحل 3N؟

363
00:17:33,350 --> 00:17:36,241
برخی از عوامل از مراحل نفر،
که پایین تر آن محدود.

364
00:17:36,241 --> 00:17:36,740
آره؟

365
00:17:36,740 --> 00:17:37,910
>> رسید حباب مرتب کردن بر اساس؟

366
00:17:37,910 --> 00:17:41,610
>> SPEAKER: حباب مرتب کردن بر اساس طول می کشد
شما مراحل نفر حداقل، چرا؟

367
00:17:41,610 --> 00:17:42,279
چرا؟

368
00:17:42,279 --> 00:17:45,320
چرا باید که شروع به آمدن به شما
به طور مستقیم، حتی اگر آن را نمی کند تنها

369
00:17:45,320 --> 00:17:46,530
رتبهدهی نشده است؟

370
00:17:46,530 --> 00:17:47,030
آره؟

371
00:17:47,030 --> 00:17:47,990
>> رسید [نامفهوم].

372
00:17:47,990 --> 00:17:51,652

373
00:17:51,652 --> 00:17:52,360
SPEAKER: دقیقا.

374
00:17:52,360 --> 00:17:55,810
در بهترین شرایط ممکن
مرتب سازی حبابی، و بسیاری از الگوریتم ها،

375
00:17:55,810 --> 00:17:58,769
اگر من به شما دست هشت نفر
که در حال حاضر طبقه بندی شده اند،

376
00:17:58,769 --> 00:18:00,560
این امر می تواند احمقانه
برای شما، الگوریتم،

377
00:18:00,560 --> 00:18:02,202
برای رفتن به عقب و جلو
بیش از یک بار، درست است؟

378
00:18:02,202 --> 00:18:04,285
از آنجا که در اسرع وقت شما
راه رفتن از طریق لیست یک بار،

379
00:18:04,285 --> 00:18:08,090
شما باید بدانند، آه، من هیچ
معاوضه، این لیست طبقه بندی شده اند است، خروج.

380
00:18:08,090 --> 00:18:09,700
اما این که در آینده به شما تعداد مراحل را.

381
00:18:09,700 --> 00:18:12,033
>> و برعکس، چه چیزی دیگر
شیوه تفکر در مورد آن؟

382
00:18:12,033 --> 00:18:15,240
حباب نوع امگا است،
به تعبیری، از n،

383
00:18:15,240 --> 00:18:19,050
چرا که اگر شما در نگاه
کمتر از تعداد عناصر، چه

384
00:18:19,050 --> 00:18:23,009
موضوع اساسی وجود دارد؟

385
00:18:23,009 --> 00:18:24,550
شما نمی دانید که اگر آن را طبقه بندی شده اند، درست است.

386
00:18:24,550 --> 00:18:26,800
ما انسان ها نگاه ممکن است در هشت
مردم و مانند، آه، آن را طبقه بندی شده اند،

387
00:18:26,800 --> 00:18:28,430
که من نفر مراحل را ندارد، اما این کار را کرد.

388
00:18:28,430 --> 00:18:30,810
چشم شما، حتی اگر شما نوع
از یک میدان بزرگ دید،

389
00:18:30,810 --> 00:18:33,184
شما در هشت عنصر نگاه کرد،
شما در هشت نفر نگاه کرد،

390
00:18:33,184 --> 00:18:34,610
که هشت مرحله را به طور موثر.

391
00:18:34,610 --> 00:18:38,612
و تنها اگر من را از طریق تمام راه رفتن
کارهای من می دانم، بله، طبقه بندی شده اند.

392
00:18:38,612 --> 00:18:41,320
اگر من در نیمه راه فکر کردن، همه
سمت راست، آن را بسیار طبقه بندی شده اند تا کنون،

393
00:18:41,320 --> 00:18:42,520
شانس آن را طبقه بندی شده اند که چه هستند؟

394
00:18:42,520 --> 00:18:44,186
این الگوریتم نمی شود درست است.

395
00:18:44,186 --> 00:18:46,250
ممکن است سریع تر، اما اشتباه است.

396
00:18:46,250 --> 00:18:48,500
>> بنابراین در حال حاضر ما باید یک راه
توصیف یک محدوده پایین تر،

397
00:18:48,500 --> 00:18:49,710
و آنچه در مورد زمان ثابت؟

398
00:18:49,710 --> 00:18:54,565
یک الگوریتم است که پایین تر چه خبر
محدود به زمان در حال اجرا خود را از یک؟

399
00:18:54,565 --> 00:18:58,350
1 گام به گام، گام 2، 10 مرحله است، اما
ثابت، مستقل از n،

400
00:18:58,350 --> 00:18:59,310
اندازه ورودی؟

401
00:18:59,310 --> 00:19:03,930

402
00:19:03,930 --> 00:19:04,600
بله، در پشت.

403
00:19:04,600 --> 00:19:05,309
>> رسید تابع () printf؟

404
00:19:05,309 --> 00:19:06,183
SPEAKER: آن چیست؟

405
00:19:06,183 --> 00:19:07,184
رسید تابع () printf؟

406
00:19:07,184 --> 00:19:07,850
SPEAKER: تابع () printf.

407
00:19:07,850 --> 00:19:08,400
OK، اطمینان حاصل کنید.

408
00:19:08,400 --> 00:19:10,720
بنابراین به تعداد ثابت از مراحل.

409
00:19:10,720 --> 00:19:13,170
و من در حال حاضر که باید now--
ما در حال صحبت کردن در مورد کد C

410
00:19:13,170 --> 00:19:16,040
و نه خراش، چیزی
مثل مثلا با تابع () printf،

411
00:19:16,040 --> 00:19:17,710
ما باید شروع به گرفتن دقیق.

412
00:19:17,710 --> 00:19:21,090
از آنجا که تابع () printf نمی کشد
ورودی، آن را به یک رشته است،

413
00:19:21,090 --> 00:19:23,220
و رشته ها را به لحاظ فنی طول داشته باشد.

414
00:19:23,220 --> 00:19:25,530
بنابراین اگر ما در حال حاضر می خواهید انتخاب کنید
بر شما، اگر برای شما مهم نیست،

415
00:19:25,530 --> 00:19:29,430
از لحاظ فنی ما می تواند که تابع () printf استدلال می کنند
اختصاص یک ورودی با طول متغیر،

416
00:19:29,430 --> 00:19:32,270
و قطعا ممکن است بیش را
زمان برای چاپ یک رشته در این مدت،

417
00:19:32,270 --> 00:19:33,560
از این طولانی است.

418
00:19:33,560 --> 00:19:36,570
>> بنابراین اگر ما فقط در نظر
مرتب سازی و جستجو نمونه؟

419
00:19:36,570 --> 00:19:40,450
چه در مورد مایک اسمیت در گوشی
کتاب، یا جستجوی دودویی به طور کلی؟

420
00:19:40,450 --> 00:19:42,220
در بهترین حالت، آنچه ممکن است اتفاق می افتد؟

421
00:19:42,220 --> 00:19:45,577
I باز کردن دفترچه تلفن و، بم،
این تعداد مایک اسمیت وجود دارد.

422
00:19:45,577 --> 00:19:46,660
من می توانم او را از حق دور تماس بگیرید.

423
00:19:46,660 --> 00:19:49,390
>> در زمان یک گام، شاید دو مرحله،
اما یک عدد ثابت از مراحل

424
00:19:49,390 --> 00:19:50,230
اگر من خوش شانس.

425
00:19:50,230 --> 00:19:52,570
و رک و پوست کنده، ما در دیدم
دوشنبه همکلاسی خود

426
00:19:52,570 --> 00:19:54,710
دریافت کاملا خوش شانس دو بار در یک ردیف.

427
00:19:54,710 --> 00:19:57,050
و این ثابت بود و در واقع
زمان در مرزهای پایین تر

428
00:19:57,050 --> 00:20:01,280
در الگوریتم مورد نظر برای پیدا کردن
تعداد 50 پشت آن بسته شده

429
00:20:01,280 --> 00:20:01,830
درب.

430
00:20:01,830 --> 00:20:06,400
>> در حال حاضر، به عنوان یک به کنار، اگر شما کشف
که هر دو O بزرگ، حد بالا،

431
00:20:06,400 --> 00:20:09,310
و امگا، حد کم،
یکی در همان است که

432
00:20:09,310 --> 00:20:11,830
از همان فرمول در است
پرانتز، شما همچنین می توانید

433
00:20:11,830 --> 00:20:15,170
می گویند، فقط به فانتزی،
که چیزی است در تتا

434
00:20:15,170 --> 00:20:18,270
از n یا تتا برخی از ارزش های دیگر.

435
00:20:18,270 --> 00:20:20,661
این فقط بدان معناست که وقتی بزرگ
O و امگا یکسان هستند.

436
00:20:20,661 --> 00:20:21,910
در حال حاضر آنچه در مورد انتخاب نوع؟

437
00:20:21,910 --> 00:20:23,400
حال با استفاده از واژگان جدید.

438
00:20:23,400 --> 00:20:27,407
در انتخاب نوع، آنچه که ما بودند
انجام دوباره، و دوباره، و دوباره؟

439
00:20:27,407 --> 00:20:29,990
من که قرار بود به جلو و عقب از طریق
لیست، به دنبال چه کسی؟

440
00:20:29,990 --> 00:20:33,260

441
00:20:33,260 --> 00:20:34,730
تعداد کوچکترین.

442
00:20:34,730 --> 00:20:37,560
>> پس چگونه بسیاری از مراحل، چگونه
بسیاری از مقایسه های من

443
00:20:37,560 --> 00:20:43,250
به منظور کشف کردن را که
کوچکترین عنصر در این فهرست بود؟

444
00:20:43,250 --> 00:20:44,437
نفر منهای 1، درست است؟

445
00:20:44,437 --> 00:20:47,770
از آنجا که اگر من فقط با یک من شروع
داده شده و من شروع به مقایسه او و یا او را،

446
00:20:47,770 --> 00:20:49,519
پس از آن او، او را
و یا او را، او را، من

447
00:20:49,519 --> 00:20:52,010
تنها می تواند عناصر جفت
با هم نفر منهای 1 بار.

448
00:20:52,010 --> 00:20:55,630
بنابراین انتخاب نوع مشابه طول می کشد
نفر منهای 1 مراحل اولین بار.

449
00:20:55,630 --> 00:20:59,540
>> چگونه بسیاری از مراحل آن را به من به
پیدا کردن کوچکترین عنصر دوم؟

450
00:20:59,540 --> 00:21:02,920
نفر منهای 2، چون من گنگ بودن
اگر من در حفظ و نگاه همان مردم

451
00:21:02,920 --> 00:21:06,280
دوباره اگر من در حال حاضر او را انتخاب کرده ام
و یا او را و آنها را در جای خود.

452
00:21:06,280 --> 00:21:09,270
و مرحله سوم، نفر
منهای 3، پس از آن نفر منهای 4.

453
00:21:09,270 --> 00:21:11,020
ما این الگو را دیده ام
قبل از، و در واقع

454
00:21:11,020 --> 00:21:13,460
انتخاب نوع مشابه
دارای یک کران بالا

455
00:21:13,460 --> 00:21:16,210
از n به توان اگر ما تا که جمع.

456
00:21:16,210 --> 00:21:19,790
حد پایین تر، انتخاب نوع آن چیست؟

457
00:21:19,790 --> 00:21:25,350
حداقل، چقدر باید انتخاب زمان
مرتب کردن بر اساس را، به عنوان ما آن را در روز دوشنبه مشخص شده است؟

458
00:21:25,350 --> 00:21:29,370

459
00:21:29,370 --> 00:21:30,490
پیشنهاد دو گزینه.

460
00:21:30,490 --> 00:21:32,360
شاید نفر، به عنوان قبل از.

461
00:21:32,360 --> 00:21:35,040
شاید آن را به نفر مربع، آن را به عنوان
در حال حاضر به عنوان حد بالا.

462
00:21:35,040 --> 00:21:35,874
>> رسید نفر مربع.

463
00:21:35,874 --> 00:21:36,664
SPEAKER: نفر مربع.

464
00:21:36,664 --> 00:21:37,368
چرا؟

465
00:21:37,368 --> 00:21:40,060
>> رسید از آنجا که شما
برای تعریف [نامفهوم].

466
00:21:40,060 --> 00:21:41,510
>> SPEAKER: دقیقا.

467
00:21:41,510 --> 00:21:45,077
حداقل که من انتخاب نوع تعریف
آن را خیلی ساده و بی تکلف بود، رفتن ادامه دهید،

468
00:21:45,077 --> 00:21:46,160
پیدا کردن کوچکترین عنصر.

469
00:21:46,160 --> 00:21:47,770
برو دوباره، پیدا کردن کوچکترین عنصر.

470
00:21:47,770 --> 00:21:49,490
برو دوباره، پیدا کردن کوچکترین عنصر.

471
00:21:49,490 --> 00:21:51,700
هیچ نوع وجود دارد
بهینه سازی در آن وجود دارد که

472
00:21:51,700 --> 00:21:54,350
ممکن است به من اجازه بعد از سقط
فقط نفر یا بیشتر مراحل.

473
00:21:54,350 --> 00:21:57,080
پس در واقع، انتخاب
مرتب کردن بر اساس، امگا از n مربع.

474
00:21:57,080 --> 00:22:00,667
>> چه در مورد نوع قرار دادن، که در آن من در زمان
که I، داده شد و پس از آن من به او plopped

475
00:22:00,667 --> 00:22:01,750
و یا او را در جای مناسب؟

476
00:22:01,750 --> 00:22:04,958
سپس من به نفر دوم اقدام،
او در جای مناسب plopped.

477
00:22:04,958 --> 00:22:07,910
سپس نفر بعدی، plopped
او در جای مناسب.

478
00:22:07,910 --> 00:22:10,537
توجه کنید که این بسیار
خطی، پس به صحبت می کنند.

479
00:22:10,537 --> 00:22:12,620
من یک خط راست، من هستم
رفتن به جلو و عقب،

480
00:22:12,620 --> 00:22:16,080
من به دنبال هرگز به عقب واقعا، اما
چه اتفاقی می افتد زمانی که من به او وارد

481
00:22:16,080 --> 00:22:20,302
و یا او را به آغاز
لیست که ما در روز دوشنبه بود؟

482
00:22:20,302 --> 00:22:21,010
چه اتفاقی افتاد؟

483
00:22:21,010 --> 00:22:21,510
آره؟

484
00:22:21,510 --> 00:22:23,122
رسید [نامفهوم].

485
00:22:23,122 --> 00:22:24,830
SPEAKER: آره، که
گرفتن بود، درست است؟

486
00:22:24,830 --> 00:22:26,746
شما ممکن است از یاد
همکلاسی های خود، در صورتی که

487
00:22:26,746 --> 00:22:29,670
هر حرکت با ساخت شد
پای خود را، که یک عملیات بود.

488
00:22:29,670 --> 00:22:33,610
بنابراین اگر سه نفر اینجا و آنجا
فرد جدید راه را بر داشت وجود دارد،

489
00:22:33,610 --> 00:22:37,360
در یک مرحله طولانی مثل این، مطمئن، او
و یا او فقط می تواند به پایان است.

490
00:22:37,360 --> 00:22:40,074
اما اگر ما در حال فکر کردن در مورد
کامپیوتر و مجموعه ای از حافظه،

491
00:22:40,074 --> 00:22:41,990
این افراد می رویم
به به زدن بیش از

492
00:22:41,990 --> 00:22:43,260
به اتاق را برای آن شخص.

493
00:22:43,260 --> 00:22:46,930
و به طوری که نفر منهای 1 shufflings،
نفر منهای 2 shufflings، نفر

494
00:22:46,930 --> 00:22:50,660
منهای 3 shufflings است فقط نوع
اتفاق می افتد پشت سر من، نه در مقابل من

495
00:22:50,660 --> 00:22:52,710
مانند قبل، از بعضی جهات.

499
00:22:52,557 --> 00:22:54,640
در حال حاضر به عنوان یک به کنار، و به عنوان
شما ممکن است را دیده اند، به صورت آنلاین

500
00:22:54,640 --> 00:22:57,699
اگر شما شروع به مجبور باشید در مورد
انواع، در بسیاری از آنهایی که متفاوت وجود دارد

501
00:22:57,699 --> 00:22:59,490
خارج وجود دارد، برخی از آنها
بهتر از دیگران است.

502
00:22:59,490 --> 00:23:02,200
در واقع، bogosort است
این نوع از سرگرم کننده را به نگاه کردن است.

503
00:23:02,200 --> 00:23:06,650
Bogosort طول می کشد مجموعه ای از
اعداد و یا می گویند یک دست ورق بازی،

504
00:23:06,650 --> 00:23:09,870
به طور تصادفی آنها را shuffles، و
چک اگر آنها طبقه بندی شده اند.

505
00:23:09,870 --> 00:23:12,130
و اگر نه، آن را دوباره.

506
00:23:12,130 --> 00:23:14,140
و اگر نه، آن را دوباره.

507
00:23:14,140 --> 00:23:15,440
اگر نه، آن را دوباره.

508
00:23:15,440 --> 00:23:17,060
باور نکردنی احمق.

509
00:23:17,060 --> 00:23:19,520
>> و در واقع، اگر شما به عنوان خوانده شده
مانند ویکیپدیا،

510
00:23:19,520 --> 00:23:21,200
نام مستعار خود را مرتب کردن بر اساس احمقانه است.

511
00:23:21,200 --> 00:23:25,180
این در نهایت کار خواهد کرد،
امیدوارم، با توجه به زمان کافی،

512
00:23:25,180 --> 00:23:28,240
اما آن مقدار از زمان
می تواند مدتی طول بکشد.

513
00:23:28,240 --> 00:23:31,650
پس اگر من می تواند، اجازه دهید سرعت همه چیز
از مثال مری بث قبل از آن،

514
00:23:31,650 --> 00:23:35,150
با داشتن تعداد کمی از عناصر بیشتر،
اما دو پردازنده است.

515
00:23:35,150 --> 00:23:37,100
دو نفر، اگر شما
نمی خواهد ذهن به ما بپیوندند.

516
00:23:37,100 --> 00:23:40,972
چگونه در مورد 1 در اینجا، و
اجازه دهید هیچ کس بیش از وجود دارد go--؟

517
00:23:40,972 --> 00:23:41,722
هیچ کس بیش از وجود دارد؟

518
00:23:41,722 --> 00:23:42,221
OK.

519
00:23:42,221 --> 00:23:44,190
شما با سیاه و سفید
پیراهن، بله، در آمده است.

520
00:23:44,190 --> 00:23:45,000
همه حق است، چه نام شما چیه؟

521
00:23:45,000 --> 00:23:45,720
>> رسید پیتر.

522
00:23:45,720 --> 00:23:46,100
>> SPEAKER: آن چیست؟

523
00:23:46,100 --> 00:23:46,766
>> رسید پیتر.

524
00:23:46,766 --> 00:23:49,450
SPEAKER: پیتر، دیوید، ملاقات با شما خوشبختم.

525
00:23:49,450 --> 00:23:53,670
خوب، ما پیتر در اینجا، اگر شما
می خواهم به روی میز آمده اینجا.

526
00:23:53,670 --> 00:23:54,550
و چه نام شما چیه؟

527
00:23:54,550 --> 00:23:55,216
>> رسید النا.

528
00:23:55,216 --> 00:23:55,970
SPEAKER: النا.

529
00:23:55,970 --> 00:23:57,030
OK، ملاقات با شما خوشبختم.

530
00:23:57,030 --> 00:23:58,060
النا ملاقات پیتر.

531
00:23:58,060 --> 00:23:59,170
پیتر، النا.

532
00:23:59,170 --> 00:24:02,290
و ما اندرو نیاز
تا اینجا نیز، لطفا.

533
00:24:02,290 --> 00:24:06,107
و چالش خود را در حال رفتن
به به مرتب کردن یک دسته کارت.

534
00:24:06,107 --> 00:24:08,190
و اگر نا آشنا، عرشه
از کارت باید در نهایت

535
00:24:08,190 --> 00:24:11,064
مرتب چیزی کمی مانند
این که در آن ما باشگاه انجام دهید، سپس

536
00:24:11,064 --> 00:24:13,660
پیک، پس از آن دل و
الماس، از تک خال به عنوان یک یک،

537
00:24:13,660 --> 00:24:15,570
تمام راه را تا به شاه.

538
00:24:15,570 --> 00:24:20,890
>> کارت من قصد دارم به شما بدهد
در حال رفتن به 52 در کمیت.

539
00:24:20,890 --> 00:24:23,160
ما قصد داریم به طور مشابه
زمانی که شما در یک لحظه.

540
00:24:23,160 --> 00:24:26,410
ما قصد داریم به پرتاب اندرو
تا بر روی صفحه نمایش در اینجا،

541
00:24:26,410 --> 00:24:28,170
تا که به تماشای شما به عنوان انجام این کار.

542
00:24:28,170 --> 00:24:31,070
و به طوری که همه از این
همه قابل مشاهده تر است،

543
00:24:31,070 --> 00:24:33,490
این کارت های I در آمازون کرده اند.

544
00:24:33,490 --> 00:24:42,861
به طوری که آنها در حال حاضر به صورت تصادفی
طبقه بندی شده اند، و ما قصد داریم به شما وقت.

545
00:24:42,861 --> 00:24:44,610
و ما در حال رفتن به
نگه داشتن آن واقعی این زمان،

546
00:24:44,610 --> 00:24:47,820
بنابراین ما قصد داریم که به شما فشار
چرا که در غیر این صورت این خسته کننده خواهد شد

547
00:24:47,820 --> 00:24:48,460
به سرعت.

548
00:24:48,460 --> 00:24:53,860
اگر شما می توانید اقدام به مرتب سازی 52
عناصر با هم از طریق برخی ابزار، در حال حاضر.

549
00:24:53,860 --> 00:25:04,710

550
00:25:04,710 --> 00:25:07,180
>> و دوباره، همانطور که ما این را تماشا کنید
بچه ها انجام آنچه، در پایان

551
00:25:07,180 --> 00:25:10,200
رفتن به تولید آشکار
در نتیجه، فکر می کنم در مورد واقعا

552
00:25:10,200 --> 00:25:12,962
چگونه آنها هر آن انجام می دهند،
چگونه شما ممکن است آن را توضیح دهید.

553
00:25:12,962 --> 00:25:15,045
از آنجا دوباره، این
تمام مراحل، الگوریتم

554
00:25:15,045 --> 00:25:17,090
که ما را برای به عنوان یک انسان اعطا می شود.

555
00:25:17,090 --> 00:25:22,349
اما شما احتمالا طولانی به حال
شهود، طولانی قبل از شما حتی

556
00:25:22,349 --> 00:25:24,390
در مورد گرفتن یک فکر
کلاس علوم کامپیوتر شما

557
00:25:24,390 --> 00:25:27,223
ممکن است شهود با حال
که برای حل مشکلات مثل این.

558
00:25:27,223 --> 00:25:29,560
اما هنگامی که شما تشخیص
الگوها و شروع

559
00:25:29,560 --> 00:25:32,407
برای رسمی مراحل که با آن
شما در حال حل این مشکلات،

560
00:25:32,407 --> 00:25:35,490
پیدا خواهید کرد که شما می توانید خیلی حل
جالب تر و پیچیده بیشتر

561
00:25:35,490 --> 00:25:39,190
مشکلات به سرعت.

562
00:25:39,190 --> 00:25:42,351
بنابراین کسی از مخاطبان، چه است
حداقل یک عنصر از الگوریتم

563
00:25:42,351 --> 00:25:43,350
که آنها با استفاده از اینجا؟

564
00:25:43,350 --> 00:25:44,275
>> رسید [نامفهوم]

565
00:25:44,275 --> 00:25:45,150
SPEAKER: آن چیست؟

566
00:25:45,150 --> 00:25:47,062
رسید با کت و شلوار.

567
00:25:47,062 --> 00:25:47,770
SPEAKER: با کت و شلوار.

568
00:25:47,770 --> 00:25:50,630
پس اول آنها خوشه
تمام الماس با هم

569
00:25:50,630 --> 00:25:52,560
به نظر می رسد، همه از
دل به هم به نظر می رسد،

570
00:25:52,560 --> 00:25:56,520
و به این ترتیب، بدون توجه
برای اعداد بر روی کارت.

571
00:25:56,520 --> 00:26:00,900
و در حال حاضر به نظر می رسد، به عنوان مثال،
به مرتب سازی آنها بر اساس تعداد.

572
00:26:00,900 --> 00:26:06,870

573
00:26:06,870 --> 00:26:08,910
بسیار خوب است.

574
00:26:08,910 --> 00:26:12,370
>> همه حق است، پس آنچه
است که در مرحله نهایی و سپس در اینجا؟

575
00:26:12,370 --> 00:26:16,950
هنگامی که ما چهار لباس مرتب، چه
کار ما نیاز به انجام به چهار شمع

576
00:26:16,950 --> 00:26:20,059
به منظور دستیابی به یک
طبقه بندی شده اند عرشه، کاملا به سادگی؟

577
00:26:20,059 --> 00:26:21,350
بنابراین ما باید آنها را به ادغام دوباره.

578
00:26:21,350 --> 00:26:25,160
>> پس یک ایده جالب وجود دارد که
دوباره، جرات گفتن، بسیار حسی حتی

579
00:26:25,160 --> 00:26:28,140
اگر شما ممکن است هرگز سیلی اند
این نوع از برچسب بر روی آن.

580
00:26:28,140 --> 00:26:31,900
این مفهوم اساسی تقسیم
مشکل در نیمی از این زمان نیست،

581
00:26:31,900 --> 00:26:33,410
اما حداقل به چهار قطعه.

582
00:26:33,410 --> 00:26:36,810
حل بسیار
مشکلات اساسا یکسان

583
00:26:36,810 --> 00:26:40,480
در انزوا از یکدیگر،
و سپس ادغام نتایج.

584
00:26:40,480 --> 00:26:46,940

585
00:26:46,940 --> 00:26:50,140
و، عالی، انجام می شود.

586
00:26:50,140 --> 00:26:52,140
خوب، یک دور بزرگ
از تشویق، اگر ما می تواند.

587
00:26:52,140 --> 00:26:56,480
>> [تشویق حضار]

588
00:26:56,480 --> 00:26:59,740
>> SPEAKER: من هیچ ایده چه چیزی نظر شما
با این، اما در اینجا شما بروید.

589
00:26:59,740 --> 00:27:01,690
از شما بسیار سپاسگزارم.

590
00:27:01,690 --> 00:27:04,660
بنابراین اجازه دهید، دو دقیقه
و هشت ثانیه،

591
00:27:04,660 --> 00:27:07,490
اگر شما می خواهم برای به چالش کشیدن دوستان خود را.

592
00:27:07,490 --> 00:27:12,160
چه پس از آن است که رفتن به
یک را به دور از این

593
00:27:12,160 --> 00:27:13,830
که ما می توانیم اهرم به طور کلی؟

594
00:27:13,830 --> 00:27:16,080
خوب، فکر می کنم به
این آرایه از اعداد،

595
00:27:16,080 --> 00:27:19,060
و فکر می کنم در حال حاضر به برخی از
شبه ما در گذشته نوشته ام،

596
00:27:19,060 --> 00:27:22,080
و این شبه بود
حل مشکل دفترچه تلفن.

597
00:27:22,080 --> 00:27:25,150
به موجب آن در شبه I
شمارش یک راه بیشتر روشمند

598
00:27:25,150 --> 00:27:28,400
از توصیف چگونه من بسیار بصری
الگوریتم انسان از تقسیم تلفن

599
00:27:28,400 --> 00:27:31,650
کتاب در نیمه، تکرار، تکرار، تکرار،
تا زمانی که من کسی مثل مایک اسمیت،

600
00:27:31,650 --> 00:27:33,790
اگر او در واقع در دفترچه تلفن.

601
00:27:33,790 --> 00:27:37,610
>> اما من نوع استفاده آنچه من تماس بگیرید
یک رویکرد بسیار تکرار شونده در اینجا،

602
00:27:37,610 --> 00:27:42,160
در اطلاع خاص خط 8 و 11 خط.

603
00:27:42,160 --> 00:27:46,750
کسانی که شواهدی از تکرار است
رویکرد، رویکرد حلقه،

604
00:27:46,750 --> 00:27:49,040
چرا که این دقیقا همان
رفتار آنها شوند.

605
00:27:49,040 --> 00:27:52,910
این خط ها هر دو می گویند به
خط سه، و شما می توانید نوع

606
00:27:52,910 --> 00:27:55,140
که فکر می کنم در خود
چشم ذهن به عنوان یک حلقه.

607
00:27:55,140 --> 00:27:59,080
این به شما گفتن برای رفتن به بالا و به مرحله
سه و تکرار، دوباره و دوباره،

608
00:27:59,080 --> 00:28:00,010
و دوباره.

609
00:28:00,010 --> 00:28:04,410
>> اما اگر ما اهرم یک ایده کلیدی
اینجا است که ما نه آخرین بار انجام داد،

610
00:28:04,410 --> 00:28:10,280
و ساده خط 8 و
خط 11 و همسایگان خود

611
00:28:10,280 --> 00:28:12,840
به عنوان فقط این، در زرد.

612
00:28:12,840 --> 00:28:16,480
این اساسا کوتاه نمی
شبه بسیار زیاد است،

613
00:28:16,480 --> 00:28:20,530
اما آن را اساسا تغییر
ماهیت الگوریتم من.

614
00:28:20,530 --> 00:28:24,220
چه من در حال حاضر گفت:
در مرحله 7، در مرحله 10،

615
00:28:24,220 --> 00:28:29,140
است به جستجو برای مایک
در همان راه دقیق،

616
00:28:29,140 --> 00:28:31,580
اما فقط در سمت چپ
نیم یا نیمه سمت راست.

617
00:28:31,580 --> 00:28:33,420
>> بنابراین به عبارت دیگر، اگر
من از ابتدا شروع،

618
00:28:33,420 --> 00:28:36,150
انتخاب کنید تا به دفترچه تلفن، به وسط باز
دفترچه تلفن، در نام نگاه کنید،

619
00:28:36,150 --> 00:28:39,010
اگر اسمیت است که در میان
نام و نام خانوادگی را، با مایک، دیگری

620
00:28:39,010 --> 00:28:44,340
اگر اسمیت پیش از آن در کتاب است، گام هفت
جستجو برای مایک در نیمه سمت چپ کتاب است.

621
00:28:44,340 --> 00:28:47,130
اما این نوع از احساس
آن را ترک من حلق آویز، درست است؟

622
00:28:47,130 --> 00:28:49,240
در رنگ های زرد، است
آموزش، اما چگونه من انجام

623
00:28:49,240 --> 00:28:51,870
جستجو برای مایک در سمت چپ
نیمی از دفترچه تلفن؟

624
00:28:51,870 --> 00:28:54,210
کجا من
الگوریتم که با من

625
00:28:54,210 --> 00:28:57,100
می تواند برای کسی مثل مایک اسمیت جستجو؟

626
00:28:57,100 --> 00:28:58,980
خوب، آن را به ما خیره در صورت می شود.

627
00:28:58,980 --> 00:29:03,090
من به معنای واقعی کلمه می تواند با استفاده از همان دقیق
برنامه به طور موثر بالا رفتن به بالا

628
00:29:03,090 --> 00:29:06,490
دوباره و دوباره در حال اجرا
همان خطوط کد.

629
00:29:06,490 --> 00:29:10,610
>> بنابراین حتی اگر این باید احساس
مثل یک بیت از یک تعریف دوره ای

630
00:29:10,610 --> 00:29:13,480
که در آن شما در حال پاسخ دادن به کسی است
سوال و تنها با نوع درخواست

631
00:29:13,480 --> 00:29:15,990
سوال دوباره همان،
مانند چرا، چرا، چرا؟

632
00:29:15,990 --> 00:29:21,580
واقعیت این است چون ما سخت کدگذاری کرده ام
یک زن و شوهر از خطوط ویژه، مرحله 4،

633
00:29:21,580 --> 00:29:25,320
است که اگر، و مرحله 12، که
به طور موثر یکی دیگر از شعبه است،

634
00:29:25,320 --> 00:29:30,120
چرا که ما آن اقدامات چاره موقت،
این الگوریتم خاتمه خواهد اگر ما

635
00:29:30,120 --> 00:29:32,050
پیدا کردن مایک، و یا اگر ما نمی کنند.

636
00:29:32,050 --> 00:29:36,810
اما در مرحله ی 7 و 10 در حال حاضر، ما باید
آنچه ما می خواهیم از یک الگوریتم بازگشتی تماس بگیرید.

637
00:29:36,810 --> 00:29:40,420
و بازگشت است و در واقع یک ایده قدرتمند
که یک ذهن کمی خم در ابتدا است،

638
00:29:40,420 --> 00:29:42,500
که ما هم اکنون می توانید به شرح زیر اعمال می شود.

639
00:29:42,500 --> 00:29:46,600
>> ادغام مرتب کردن بر اساس خواهد بود که آخرین نوع که
ما در به طور رسمی نگاه کنید، حداقل در کلاس.

640
00:29:46,600 --> 00:29:50,040
و این اساسا متفاوت
از آن سه، و قطعا

641
00:29:50,040 --> 00:29:52,140
چهار اگر ما شامل bogosort.

642
00:29:52,140 --> 00:29:54,810
در اینجا شبه مرتب سازی ادغام است.

643
00:29:54,810 --> 00:30:00,170
وقتی که در ورودی از n عنصر، بنابراین با توجه به
آرایه ای از اندازه n، اگر n کمتر از 2 است،

644
00:30:00,170 --> 00:30:01,040
بازگشت.

645
00:30:01,040 --> 00:30:03,610
پس چرا که من
سلامت عقل اول چک کنید؟

646
00:30:03,610 --> 00:30:09,477
مفهوم چه اگر من به شما دست
آرایه ای که طول n کمتر از 2 است؟

647
00:30:09,477 --> 00:30:11,060
این در حال حاضر طبقه بندی شده اند، بدیهی است، درست است؟

648
00:30:11,060 --> 00:30:13,640
از آنجا که لیست هر دو است
یک عنصر است که بدیهی

649
00:30:13,640 --> 00:30:15,180
طبقه بندی شده اند، زیرا این
تنها چیزی که وجود دارد.

650
00:30:15,180 --> 00:30:18,138
و یا، آن را از صفر که به معنی
هیچ چیز برای مرتب سازی وجود دارد، بنابراین طبیعت

651
00:30:18,138 --> 00:30:18,720
آن طبقه بندی شده اند است.

652
00:30:18,720 --> 00:30:20,410
فقط هیچ مشکلی وجود ندارد وجود دارد.

653
00:30:20,410 --> 00:30:22,310
به طوری که حالت پایه به اصطلاح ما است.

654
00:30:22,310 --> 00:30:24,440
>> که در روح شبیه است
به آنچه که ما با مایک بود.

655
00:30:24,440 --> 00:30:26,023
اگر مایک در دفترچه تلفن، به او تماس بگیرید.

656
00:30:26,023 --> 00:30:27,740
اگر او وجود ندارد، رها کردن.

657
00:30:27,740 --> 00:30:31,240
این یک اصطلاح مورد پایه است، مطمئن شوید
این الگوریتم در پایان روز

658
00:30:31,240 --> 00:30:33,540
در شرایط خاص متوقف خواهد شد.

659
00:30:33,540 --> 00:30:37,890
>> اما در اینجا کبیسه از ایمان است در حال حاضر، دیگر،
مرتب سازی بر اساس نیمه سمت چپ عناصر،

660
00:30:37,890 --> 00:30:39,740
پس از آن مرتب سازی بر اساس حق
نیمی از عناصر،

661
00:30:39,740 --> 00:30:41,189
و سپس ادغام نیمه طبقه بندی شده اند.

662
00:30:41,189 --> 00:30:43,230
و در اینجا است که آن را احساس
مثل ما در حال copping است.

663
00:30:43,230 --> 00:30:46,900
من از شما خواسته ام به مرتب سازی
تعداد عناصر، و من

664
00:30:46,900 --> 00:30:50,712
گفت: OK، آن را توسط مرتب سازی
سمت چپ و سمت راست مرتب سازی.

665
00:30:50,712 --> 00:30:52,420
اما من و گفت یک
دیگر چیز، و این

666
00:30:52,420 --> 00:30:55,530
موضوع کلیدی به نظر می رسد
در شهود تا کنون،

667
00:30:55,530 --> 00:30:57,380
در این مرحله سوم از ادغام وجود دارد.

668
00:30:57,380 --> 00:31:00,430
کدام حتی اگر آن را
به نظر می رسد در روح به طوری گنگ،

669
00:31:00,430 --> 00:31:02,320
مانند فقط ادغام چیز
با هم، به نظر می رسد

670
00:31:02,320 --> 00:31:05,380
به یک گام کلیدی به سمت
سرهم از دو مشکلاتی که

671
00:31:05,380 --> 00:31:07,330
در نهایت در نیمه تقسیم شدند.

672
00:31:07,330 --> 00:31:12,090
>> بنابراین نوع ادغام، اجازه دهید این کار، اگر شما می خواهید
طنز من، با یک تظاهرات بیشتر،

673
00:31:12,090 --> 00:31:14,730
فقط به طوری که ما به برخی از
اعداد به کار با.

674
00:31:14,730 --> 00:31:19,470
آیا می توانم هشت استرس تبادل I
توپ برای هشت نفر؟

675
00:31:19,470 --> 00:31:29,320
خوب، چگونه در مورد شما سه، شما چهار
در این بخش، پنج، شش، و اجازه دهید

676
00:31:29,320 --> 00:31:30,720
انجام 7، 8، در آمده است.

677
00:31:30,720 --> 00:31:35,120

678
00:31:35,120 --> 00:31:36,520
OK، آره OK.

679
00:31:36,520 --> 00:31:38,640
منهای 8، وجود دارد ما، به علاوه 1.

680
00:31:38,640 --> 00:31:39,150
عالی.

681
00:31:39,150 --> 00:31:42,000
کلیه حقوق این در آمد تا، اجازه دهید
به سرعت شما اعداد را.

682
00:31:42,000 --> 00:31:50,800
شماره دو، شماره سه، شماره چهار،
تعداد پنج، شش، هفت و هشت.

683
00:31:50,800 --> 00:31:52,140
من این زمان هشت بود به درستی.

684
00:31:52,140 --> 00:31:56,390
>> OK، تا جلو بروید اگر شما می توانید، و
اجازه دهید در منظور اصلی خود را بر اساس

685
00:31:56,390 --> 00:31:59,810
که ما دیروز به حال که نگاه
مانند این، اگر شما نمی خواهد ذهن.

686
00:31:59,810 --> 00:32:03,620
و اجازه دهید آن را در مقابل میز.

687
00:32:03,620 --> 00:32:06,510
همه حق است، بنابراین ادغام مرتب کردن بر اساس.

688
00:32:06,510 --> 00:32:08,820
این جایی است که آن را
برای به دست آوردن نوع جالب توجه است،

689
00:32:08,820 --> 00:32:12,800
چون من به نظر می رسد به خودم
خیلی امروز اطلاعات کمتر است.

690
00:32:12,800 --> 00:32:15,149
>> بنابراین نوع اول از همه ادغام
در ورودی از n عنصر،

691
00:32:15,149 --> 00:32:18,440
و واضح است که کمتر از دو، آن را
هشت، بنابراین من به برخی از کار بیشتر انجام دهد.

692
00:32:18,440 --> 00:32:21,140
بنابراین در حال حاضر ذهنی ما به عنوان یک طبقه
در حال حاضر در شعبه دیگری،

693
00:32:21,140 --> 00:32:22,540
که به معنی سه مرحله.

694
00:32:22,540 --> 00:32:25,017
اول، من برای مرتب کردن
نیمه سمت چپ عناصر.

695
00:32:25,017 --> 00:32:26,350
پس چگونه در مورد انجام این کار من؟

696
00:32:26,350 --> 00:32:28,950
خوب، من قصد دارم به نوع
ذهنی لیست تقسیم در اینجا،

697
00:32:28,950 --> 00:32:30,700
شما لازم نیست که
از لحاظ جسمی حرکت می کند، و من

698
00:32:30,700 --> 00:32:33,180
رفتن به تمرکز تنها بر روی
نیمه سمت چپ عناصر کنید.

699
00:32:33,180 --> 00:32:36,770
پس چگونه من در مورد مرتب سازی به
یک لیست در حال حاضر از اندازه چهار؟

700
00:32:36,770 --> 00:32:38,730
الگوریتم من چیست؟

701
00:32:38,730 --> 00:32:42,580
اول چک من است نفر کمتر از دو، نه،
بنابراین من به بلوک دیگری ادامه دوباره.

702
00:32:42,580 --> 00:32:43,900
مرتب سازی بر نیمی از عناصر باقی مانده است.

703
00:32:43,900 --> 00:32:45,608
>> بنابراین در حال حاضر دوباره، ذهنی،
و این جایی است که

704
00:32:45,608 --> 00:32:49,550
شما باید به افزوده شدن تعداد زیادی از
تاریخ روانی، اگر شما خواهد شد.

705
00:32:49,550 --> 00:32:51,940
حالا من که مرتب سازی بر سمت چپ
نیمی از نیمه چپ.

706
00:32:51,940 --> 00:32:57,000
همه حق است، بنابراین در حال حاضر من همان ادغام من تماس بگیرید
مرتب سازی الگوریتم، N کمتر از دو؟

707
00:32:57,000 --> 00:33:00,590
نه، آن دو است، بنابراین من باید به مرتب کردن بر اساس
نیمه چپ و نیمه راست.

708
00:33:00,590 --> 00:33:02,042
بنابراین در اینجا ما بروید، مرتب کردن نیم باقی مانده است.

709
00:33:02,042 --> 00:33:03,750
چرا شما نه تنها
یک گام به جلو است.

710
00:33:03,750 --> 00:33:04,415
نام شما چیست؟

711
00:33:04,415 --> 00:33:04,860
>> رسید دارن.

712
00:33:04,860 --> 00:33:05,260
>> SPEAKER: دن.

713
00:33:05,260 --> 00:33:06,040
دن به جلو پا کرده است.

714
00:33:06,040 --> 00:33:06,748
>> رسید دارن.

715
00:33:06,748 --> 00:33:09,000
SPEAKER: دارن، انجام می شود.

716
00:33:09,000 --> 00:33:10,090
آیا شما می گویند دارن یا دن؟

717
00:33:10,090 --> 00:33:10,550
>> رسید دارن.

718
00:33:10,550 --> 00:33:11,216
>> SPEAKER: دارن.

719
00:33:11,216 --> 00:33:14,422
OK، دارن پا کرده است
به جلو و او در حال حاضر طبقه بندی شده اند.

720
00:33:14,422 --> 00:33:16,130
و این تقریبا یک
ادعای پوچ، درست است؟

721
00:33:16,130 --> 00:33:18,862
من واقعا به نظر می رسد برای دستیابی به توان
هر چیزی، اما اجازه دهید ادامه دهید.

722
00:33:18,862 --> 00:33:20,820
حالا به من حق مرتب سازی بر اساس
نیمی از عناصر.

723
00:33:20,820 --> 00:33:21,200
نام شما چیست؟

724
00:33:21,200 --> 00:33:21,690
>> رسید لوقا.

725
00:33:21,690 --> 00:33:22,273
>> SPEAKER: لوقا.

726
00:33:22,273 --> 00:33:23,400
در تاریخ آمده، گام به گام رو به جلو.

727
00:33:23,400 --> 00:33:25,640
انجام می شود، من لوقا طبقه بندی شده اند.

728
00:33:25,640 --> 00:33:28,570
قسمت سمت چپ در حال حاضر طبقه بندی شده اند و
نیمه سمت راست در حال حاضر طبقه بندی شده اند،

729
00:33:28,570 --> 00:33:30,770
اما دوباره، یک گام مهم در اینجا وجود دارد.

730
00:33:30,770 --> 00:33:32,940
چه من بعد باید کاری انجام دهید؟

731
00:33:32,940 --> 00:33:33,941
ادغام نیمه طبقه بندی شده اند.

732
00:33:33,941 --> 00:33:36,648
در حال حاضر ما در حال رفتن به فقط باید
همه به جلو و عقب در این راه،

733
00:33:36,648 --> 00:33:38,620
چون من نوع نیاز
برخی از فضای ابتدا.

734
00:33:38,620 --> 00:33:40,411
این تقریبا مثل این
بچه ها روی میز است،

735
00:33:40,411 --> 00:33:42,460
و من نیاز به برخی از اتاق
به آنها حرکت در اطراف در.

736
00:33:42,460 --> 00:33:44,170
من می خواهم به ادغام
شما بچه ها با نگاه

737
00:33:44,170 --> 00:33:45,960
در نیمه چپ و نیمه راست.

738
00:33:45,960 --> 00:33:48,740
و بدیهی است که برای اولین بار می آید،
نیمه چپ یا نیمه سمت راست؟

739
00:33:48,740 --> 00:33:52,710
بنابراین نیمه سمت راست، پس بیایید بیش از حرکت لوقا
در اینجا به موقعیت اولیه دارن است.

740
00:33:52,710 --> 00:33:57,640
و در حال حاضر به ادغام نیمه سمت چپ خود را در،
دارن رفتن به حرکت سمت راست وجود دارد.

741
00:33:57,640 --> 00:33:59,750
>> پس چون تقریبا احساس می کند
اثر نوع حباب،

742
00:33:59,750 --> 00:34:02,482
اما الگوریتم های اساسی من،
بسیار متفاوت این زمان.

743
00:34:02,482 --> 00:34:04,815
اما در حال حاضر که در آن همه چیز
کمی آزار دهنده به خاطر شما

744
00:34:04,815 --> 00:34:06,810
به عقب روانی
که در آن I ترک نشد.

745
00:34:06,810 --> 00:34:09,893
من فقط با هم ادغام شدند ام نیمه مرتب شده،
که به معنی من در الگوریتم من هستم که در آن؟

746
00:34:09,893 --> 00:34:12,229

747
00:34:12,229 --> 00:34:13,770
من به مرتب سازی در نیمه سمت راست، درست است؟

748
00:34:13,770 --> 00:34:15,910
>> اگر شما عقب، به معنای واقعی کلمه
در این ویدئو، شما

749
00:34:15,910 --> 00:34:18,339
ببینید که ما به این کردم
نقطه لوقا و دارن

750
00:34:18,339 --> 00:34:21,370
توسط مرتب سازی بر سمت چپ
نیمی از نیمه چپ.

751
00:34:21,370 --> 00:34:23,430
سپس ما آن هم ادغام شدند
نیمه مرتب شده، که

752
00:34:23,430 --> 00:34:27,941
به معنای گام بعدی این است مرتب کردن بر اساس
نیمه راست نیمه چپ.

753
00:34:27,941 --> 00:34:29,649
همه حق است، پس بیایید
این کار را با سرعت بیشتری.

754
00:34:29,649 --> 00:34:33,282
تمامی حقوق، شش، من قصد دارم به ادعا می کنند
شما در حال حاضر طبقه بندی شده اند، بیا جلو.

755
00:34:33,282 --> 00:34:33,990
نام شما چیست؟

756
00:34:33,990 --> 00:34:34,589
>> رسید آدریانو.

757
00:34:34,589 --> 00:34:35,200
>> SPEAKER: آدریانو.

758
00:34:35,200 --> 00:34:36,010
آدریانو در حال حاضر طبقه بندی شده اند.

759
00:34:36,010 --> 00:34:36,450
و چه نام شما چیه؟

760
00:34:36,450 --> 00:34:37,080
>> رسید الکس.

761
00:34:37,080 --> 00:34:38,379
>> SPEAKER: الکس در حال حاضر طبقه بندی شده اند.

762
00:34:38,379 --> 00:34:40,750
نیمه چپ، نیمه سمت راست،
آنچه که در مرحله نهایی است؟

763
00:34:40,750 --> 00:34:41,250
ادغام.

764
00:34:41,250 --> 00:34:44,310
خیلی بی اهمیت است، بنابراین من
رفتن به ادغام در شش،

765
00:34:44,310 --> 00:34:46,930
یک قدم به عقب،
هشت، یک قدم به عقب.

766
00:34:46,930 --> 00:34:49,530
و در حال حاضر متوجه این است
غذای آماده سودمند، چه

767
00:34:49,530 --> 00:34:53,930
در حال حاضر درست در مورد نیمه سمت چپ
لیست، صرف نظر از اینکه چگونه شروع کنیم؟

768
00:34:53,930 --> 00:34:55,090
این طبقه بندی شده اند است.

769
00:34:55,090 --> 00:34:57,750
>> در حال حاضر آن را در طبقه بندی شده اند نه
این طرح بزرگ از همه چیز،

770
00:34:57,750 --> 00:35:00,250
اما آن را به طور مستقل طبقه بندی شده اند
از نیمه دیگر.

771
00:35:00,250 --> 00:35:04,100
در حال حاضر چه مرحله I در هستم اگر من را نگه دارید
روندنج چگونه داستان شروع شد؟

772
00:35:04,100 --> 00:35:05,680
حالا من به مرتب سازی نیمه سمت راست.

773
00:35:05,680 --> 00:35:07,630
بنابراین در حال حاضر ما راه برگشت در هستی
آغاز داستان،

774
00:35:07,630 --> 00:35:08,921
و اجازه دهید این کار را با سرعت بیشتری.

775
00:35:08,921 --> 00:35:11,320
من می خواهم برای مرتب کردن
نیمه سمت راست از کل لیست.

776
00:35:11,320 --> 00:35:13,060
چه گام بعدی چیست؟

777
00:35:13,060 --> 00:35:15,840
مرتب کردن بر اساس نیمه سمت چپ نیمه راست.

778
00:35:15,840 --> 00:35:18,715
مرتب کردن بر اساس نیمه سمت چپ
نیمه سمت چپ نیمه راست.

779
00:35:18,715 --> 00:35:19,590
و چه نام شما چیه؟

780
00:35:19,590 --> 00:35:20,230
>> رسید عمر.

781
00:35:20,230 --> 00:35:21,970
>> SPEAKER: عمر، گام به گام رو به جلو، انجام می شود.

782
00:35:21,970 --> 00:35:22,860
نیمه سمت چپ طبقه بندی شده اند است.

783
00:35:22,860 --> 00:35:23,330
و چه نام شما چیه؟

784
00:35:23,330 --> 00:35:23,820
>> رسید کریس.

785
00:35:23,820 --> 00:35:25,620
>> SPEAKER: کریس، را یک گام
رو به جلو، شما در حال حاضر طبقه بندی شده اند.

786
00:35:25,620 --> 00:35:27,010
چه گام اصلی است؟

787
00:35:27,010 --> 00:35:27,510
ادغام.

788
00:35:27,510 --> 00:35:30,509
پس کس در حال رفتن به ادغام را به محل
در اینجا، اگر شما می توانید یک گام به عقب را،

789
00:35:30,509 --> 00:35:32,930
و سه در حال رفتن به
یک قدم به عقب، ادغام خواهند شد.

790
00:35:32,930 --> 00:35:38,080
بنابراین در نیمه سمت چپ
نیمه سمت راست، در حال حاضر طبقه بندی شده اند.

791
00:35:38,080 --> 00:35:41,747
صادقانه بگویم، این الگوریتم احساس ما
به هدر رفتن زمان راه بیش از پیش،

792
00:35:41,747 --> 00:35:44,830
اما اگر ما این را در زمان واقعی انجام، ما
ببینید چه چیزی takeaways خواهد بود.

793
00:35:44,830 --> 00:35:47,970
حالا من اینجا هستم، راست
نیمی از نیمه سمت راست،

794
00:35:47,970 --> 00:35:50,170
اجازه دهید من به جلو و مرتب نیمه چپ.

795
00:35:50,170 --> 00:35:51,482
گام رو به جلو، چه نام شما چیه؟

796
00:35:51,482 --> 00:35:52,190
رسید رمزی.

797
00:35:52,190 --> 00:35:53,210
SPEAKER: رمزی در حال حاضر طبقه بندی شده اند.

798
00:35:53,210 --> 00:35:53,570
نام شما چیست؟

799
00:35:53,570 --> 00:35:54,200
>> رسید مارینا.

800
00:35:54,200 --> 00:35:57,033
>> SPEAKER: مارینا در حال حاضر به عنوان طبقه بندی شده اند
خوب، اگر شما را یک قدم به جلو.

801
00:35:57,033 --> 00:36:00,690
گام کلیدی در اینجا در حال حاضر ادغام، من هستم
رفتن به دل و جرات از دو فهرست از من،

802
00:36:00,690 --> 00:36:01,720
چپ و راست.

803
00:36:01,720 --> 00:36:05,150
پنج در حال رفتن به اولین آمده،
و هفت در حال رفتن به آمده است.

804
00:36:05,150 --> 00:36:06,410
و دوباره، این عمدی است.

805
00:36:06,410 --> 00:36:08,535
این واقعیت که آنها در حال گرفتن
مراحل رو به جلو و عقب

806
00:36:08,535 --> 00:36:12,997
به معنای نشان دادن است که ما نمی توانیم
این الگوریتم در محل به راحتی

807
00:36:12,997 --> 00:36:15,830
عنوان مرتب سازی حبابی، و انتخاب نوع،
و نوع قرار دادن که در آن ما فقط

808
00:36:15,830 --> 00:36:16,960
نگه داشته مبادله مردم است.

809
00:36:16,960 --> 00:36:19,940
من به معنای واقعی کلمه نیاز به یک نوع
کاغذ ابتدا که در آن

810
00:36:19,940 --> 00:36:21,827
برای قرار دادن این دوستان
در حالی که من انجام ادغام،

811
00:36:21,827 --> 00:36:23,410
و پس از آن من می توانید آنها را پشت در محل قرار داده است.

812
00:36:23,410 --> 00:36:27,260
و این کلیدی چون من با استفاده از یک
منابع جدید، فضا، نه فقط زمان.

813
00:36:27,260 --> 00:36:28,270
>> OK، این شگفت انگیز است.

814
00:36:28,270 --> 00:36:32,050
نیمه چپ طبقه بندی شده اند است، نیمه سمت راست است
مرتب شده، در حال حاضر که کلید ادغام گام.

815
00:36:32,050 --> 00:36:33,450
چگونه من رفتن به ادغام این؟

816
00:36:33,450 --> 00:36:35,470
بنابراین اگر شما به دنبال من
دست چپ و راست،

817
00:36:35,470 --> 00:36:38,930
من قصد دارم به نقطه دست چپ من
در نیمه سمت چپ، دست راست من

818
00:36:38,930 --> 00:36:42,680
در نیمه سمت راست، و در حال حاضر من به
تصمیم گیری گام به گام آنها را به ادغام در.

819
00:36:42,680 --> 00:36:44,650
بدیهی است که چه کسی می آید برای اولین بار؟

820
00:36:44,650 --> 00:36:45,150
شماره یک.

821
00:36:45,150 --> 00:36:47,327
بنابراین در اینجا آمده است،
اینجا پد ابتدا ما است.

822
00:36:47,327 --> 00:36:49,910
بنابراین در حال حاضر یک و اطلاع شماره
آنچه من با دست راست من انجام دهید،

823
00:36:49,910 --> 00:36:54,152
من قصد دارم به حرکت یک دست راست من
گام به گام به نقطه شماره سه،

824
00:36:54,152 --> 00:36:55,860
و در حال حاضر من به
تصمیم همان.

825
00:36:55,860 --> 00:36:58,387
و در واقع ایستاده در سمت راست
مقابل لوقا در اینجا اگر شما می توانید،

826
00:36:58,387 --> 00:36:59,720
چرا که این پد ابتدا ما است.

827
00:36:59,720 --> 00:37:00,610
بنابراین چه کسی می آید بعد؟

828
00:37:00,610 --> 00:37:05,000
ما لوقا با تعداد دو
یا کریس با شماره سه.

829
00:37:05,000 --> 00:37:07,460
بدیهی لوقا، تعداد
دو، بنابراین شما به اینجا می آیند.

830
00:37:07,460 --> 00:37:11,270
>> اما دست چپ من در حال حاضر در حال رفتن به
شود یک واحد اضافه به نقطه در دارن،

831
00:37:11,270 --> 00:37:15,160
و در اینجا کلید را به دور با
ادغام، من قصد دارم برای حفظ انجام این کار،

832
00:37:15,160 --> 00:37:17,340
بدیهی است، اگر شما نوع
از منطق را دنبال کنید.

833
00:37:17,340 --> 00:37:19,670
اما دست من هرگز
رفتن به عقب،

834
00:37:19,670 --> 00:37:23,861
که به معنی من فقط در حال حرکت به
سمت چپ به روند ادغام من،

835
00:37:23,861 --> 00:37:26,360
و که رفتن به کلید است
تجزیه و تحلیل ما در فقط یک لحظه.

836
00:37:26,360 --> 00:37:27,859
>> پس به این پایان به سرعت در حال.

837
00:37:27,859 --> 00:37:31,650
بنابراین سه بعدی می آید،
پس از آن چهار می آید بعد،

838
00:37:31,650 --> 00:37:38,750
و در حال حاضر پنج می آید بعد، پس از شش،
و هفت، و سپس در نهایت هشت.

839
00:37:38,750 --> 00:37:42,960
انگار کمترین الگوریتم
، اما اگر ما در واقع

840
00:37:42,960 --> 00:37:45,510
آن را اجرا کنید در همان
از سرعت ساعت است، بنابراین به

841
00:37:45,510 --> 00:37:48,106
صحبت می کنند، با همان
تیک تاک ساعت به عنوان قبل از.

842
00:37:48,106 --> 00:37:48,605
چرا؟

843
00:37:48,605 --> 00:37:51,100
خوب، اجازه دهید یک
در نتیجه نهایی است.

844
00:37:51,100 --> 00:37:56,990
>> اجازه دهید به عقب برگرده اینجا، اجازه دهید من
بالا بکشد تظاهرات بصری

845
00:37:56,990 --> 00:37:59,030
از آنچه که ما فقط.

846
00:37:59,030 --> 00:38:06,110
زوم کردن در اینجا، در این
صفحه در اینجا، گفتن فایرفاکس

847
00:38:06,110 --> 00:38:08,200
که ما می خواهیم به صف
در این کادر، اجازه دهید

848
00:38:08,200 --> 00:38:11,260
می گویند مرتب سازی حبابی، که با آن
ما در حال حاضر به خوبی آشنا هستید،

849
00:38:11,260 --> 00:38:14,130
مرتب کردن بر اساس انتخاب، که دیگر
نسبتا یک سر راست است،

850
00:38:14,130 --> 00:38:18,250
و در حال حاضر امروز مرتب کردن بر اساس ادغام، که
خواهد بود پایان اوجی ما.

851
00:38:18,250 --> 00:38:21,530
دلیل آن را در زمان طولانی تر
در اینجا با انسان و من بطور شفاهی است،

852
00:38:21,530 --> 00:38:23,480
بدیهی است، من توضیح هر مرحله.

853
00:38:23,480 --> 00:38:26,920
اما اگر شما به سادگی اجرای این، بسیار
مرتب سازی حبابی مانند ما انجام دادیم و انتخاب

854
00:38:26,920 --> 00:38:30,890
مرتب کردن بر اساس نه تنها از نظر بصری، ساعت
چقدر موثر تر

855
00:38:30,890 --> 00:38:33,330
این اعمال نفوذ از
تقسیم و غلبه

856
00:38:33,330 --> 00:38:39,150
را می توان هنگامی که به یک مجموعه داده است که اعمال
حتی اندازه هشت نیست، اما حتی از حد،

857
00:38:39,150 --> 00:38:39,970
بسیار بزرگتر است.

858
00:38:39,970 --> 00:38:44,585
من به تو ادغام مرتب کردن بر اساس، طرف های
سمت با این الگوریتم های دیگر.

859
00:38:44,585 --> 00:38:56,364

860
00:38:56,364 --> 00:38:58,530
این است رفتن به دریافت دردناک
به سرعت، و پایان

861
00:38:58,530 --> 00:39:00,890
است به خصوص اوجی نیست،
آنها فقط تا پایان طبقه بندی شده اند.

862
00:39:00,890 --> 00:39:05,280
اما کلید را به دور است که
نگاه چقدر سریعتر ادغام مرتب کردن بر اساس

863
00:39:05,280 --> 00:39:08,110
بود، مگر اینکه شما فکر می کنم من
فقط نوع خراب با شما.

864
00:39:08,110 --> 00:39:13,100
اگر ما این کار را یک بار نهایی،
اجازه دهید در این بازنگری، اجازه بازگشت

865
00:39:13,100 --> 00:39:14,960
را انتخاب کنید و مرتب سازی حبابی،
و فقط برای ضربات،

866
00:39:14,960 --> 00:39:17,330
اجازه دهید درج را انتخاب کنید
مرتب کردن بر اساس، فقط برای اندازه گیری خوب است.

867
00:39:17,330 --> 00:39:20,020
و این بار دوباره، اجازه دهید
مرتب کردن بر اساس ادغام را انتخاب کنید و اجازه دهید

868
00:39:20,020 --> 00:39:21,595
در واقع اجرای این کنار.

869
00:39:21,595 --> 00:39:24,140

870
00:39:24,140 --> 00:39:26,930
>> و این، در واقع، یک اتفاق.

871
00:39:26,930 --> 00:39:31,140
چیزی که من به طور موثر انجام داده ام است من
ورودی من در نیمه تقسیم، دوباره،

872
00:39:31,140 --> 00:39:32,240
و دوباره، و دوباره.

873
00:39:32,240 --> 00:39:35,590
و فقط تا چند بار شما می توانید وجود دارد
ورودی های خود را به نیمه تقسیم، به سمت چپ

874
00:39:35,590 --> 00:39:36,240
و راست.

875
00:39:36,240 --> 00:39:39,425
فرمول که ما را از دیدن چه
که تقسیم توصیف در نیمه

876
00:39:39,425 --> 00:39:41,050
دوباره، و دوباره، و دوباره، و دوباره؟

877
00:39:41,050 --> 00:39:41,890
>> رسید ورود به نفر.

878
00:39:41,890 --> 00:39:42,760
>> SPEAKER: log n است.

879
00:39:42,760 --> 00:39:46,300
اما پس از آن یک گام مهم دیگر وجود دارد،
این الگوریتم مراحل ورود به سیستم نیست n است.

880
00:39:46,300 --> 00:39:48,992
اگر آن را تنها ورود به سیستم شد تعداد مراحل،
ما را در مشکل باشند

881
00:39:48,992 --> 00:39:51,200
به عنوان قبل از آن ما نمی تواند
مطمئن شوید که همه چیز طبقه بندی شده اند.

882
00:39:51,200 --> 00:39:54,480
شما باید حداقل در n عنصر نگاه
تا مطمئن شوید که نفر عناصر طبقه بندی شده اند،

883
00:39:54,480 --> 00:39:55,950
در غیر این صورت آن را کبیسه از ایمان است.

884
00:39:55,950 --> 00:39:59,810
>> پس از آن ورود به سیستم با حداقل تعداد مراحل، اما
آنچه در مورد این مرحله ادغام کلیدی

885
00:39:59,810 --> 00:40:04,370
که در آن I با هم ادغام شدند نیمه چپ و راست من
نیم و در سراسر مرحله راه می رفت؟

886
00:40:04,370 --> 00:40:06,980
چگونه بسیاری از مراحل است که ادغام کنید؟

887
00:40:06,980 --> 00:40:10,150
این نفر، اما من فقط نمی
ادغام زمان نهایی است.

888
00:40:10,150 --> 00:40:15,089
در هر یک از این تماس های تو در تو، در هر
از این ادغام تو در تو، من هنوز هم طبقه بندی شده اند.

889
00:40:15,089 --> 00:40:18,380
من هم ادغام شدند این دو نفر، پس از آن این دو
بچه ها، پس از آن این دو نفر و غیره.

890
00:40:18,380 --> 00:40:19,955
>> بنابراین من ادغام دوباره، و دوباره.

891
00:40:19,955 --> 00:40:20,580
چند بار؟

892
00:40:20,580 --> 00:40:23,510
بنابراین هر بار که من تقسیم
لیست در نیم، ادغام را انجام داد.

893
00:40:23,510 --> 00:40:25,460
تقسیم این فهرست به نصف، یک ادغام.

894
00:40:25,460 --> 00:40:28,570
بنابراین اگر تقسیم لیست
می تواند انجام شود بار log n است،

895
00:40:28,570 --> 00:40:33,880
و ادغام در نهایت طول می کشد نفر
مراحل، چه در حال حاضر ممکن بالا

896
00:40:33,880 --> 00:40:37,000
محدود در حال اجرا
زمان الگوریتم ما؟

897
00:40:37,000 --> 00:40:37,980
n log n استفاده.

898
00:40:37,980 --> 00:40:40,560
>> و در واقع، این چیزی است که
ما در اینجا به دست آورده ام.

899
00:40:40,560 --> 00:40:44,650
بنابراین احساس است که شما هنگامی که در دید را ببینید
آن سه چیز در کنار هم اجرا کنید

900
00:40:44,650 --> 00:40:47,930
است نفر در برابر نفر مربع
مربع برابر n log n استفاده.

901
00:40:47,930 --> 00:40:51,010
که اساسا خواهیم دید،
نه فقط امروز بلکه در آینده،

902
00:40:51,010 --> 00:40:52,760
بسیار، بسیار سریعتر.

903
00:40:52,760 --> 00:40:56,010
دور از کف زدن برای این افراد،
من آنها را با توپ استرس پاداش خواهد داد.

904
00:40:56,010 --> 00:41:00,260
بگذارید در این مورد موکول امروز، و
ما به شما در روز دوشنبه را ببینید.

905
00:41:00,260 --> 00:41:02,255