1
00:00:00,000 --> 00:00:02,570
[Powered by Google Translate] [بخش 3 - راحت تر]

2
00:00:02,570 --> 00:00:05,070
[راب Bowden - دانشگاه هاروارد

3
00:00:05,070 --> 00:00:07,310
>> [این CS50 است. - CS50.TV]

4
00:00:07,310 --> 00:00:12,700
>> بنابراین سوال اول عجیبی دقت کنید.

5
00:00:12,700 --> 00:00:17,480
GDB اجازه می دهد تا شما "اشکال زدایی برنامه، اما، بیشتر به طور خاص، چه آن را به شما اجازه انجام این کار؟

6
00:00:17,480 --> 00:00:22,590
من که یکی از آنها، پاسخ دادن و من نمی دانم چه دقیقا انتظار می رود،

7
00:00:22,590 --> 00:00:27,910
بنابراین من حدس می زنم آن چیزی در امتداد خطوط از آن به شما اجازه می دهد تا گام به گام

8
00:00:27,910 --> 00:00:31,540
راه رفتن را از طریق این برنامه، ارتباط برقرار کردن با آن، تغییر متغیر، انجام تمام این کارها -

9
00:00:31,540 --> 00:00:34,270
اساسا به طور کامل اجرای یک برنامه کنترل

10
00:00:34,270 --> 00:00:38,410
و بازرسی هر بخش از اجرای این برنامه داده شده است.

11
00:00:38,410 --> 00:00:43,030
بنابراین ویژگی های آن اجازه دهید همه چیز اشکال زدایی کنید.

12
00:00:43,030 --> 00:00:44,830
باشه.

13
00:00:44,830 --> 00:00:50,520
جستجوی دودویی چرا نیاز است که یک آرایه مرتب شوند؟

14
00:00:50,520 --> 00:00:53,360
چه کسی می خواهد برای پاسخ به این؟

15
00:00:56,120 --> 00:01:00,070
[دانشجوی] از آنجا که آن کار نمی کند اگر آن را طبقه بندی شده اند. >> آره. [خنده]

16
00:01:00,070 --> 00:01:04,910
اگر آن را دسته بندی نمی کند، و سپس آن را غیر ممکن است که آن را در نیمی از تقسیم

17
00:01:04,910 --> 00:01:07,850
و می دانیم که همه چیز را به سمت چپ کمتر است و همه چیز را به سمت راست

18
00:01:07,850 --> 00:01:10,490
بیشتر از مقدار متوسط ​​است.

19
00:01:10,490 --> 00:01:12,790
پس از آن نیاز به مرتب شوند.

20
00:01:12,790 --> 00:01:14,170
باشه.

21
00:01:14,170 --> 00:01:17,570
چرا مرتب سازی بر اساس حباب در O مربع N؟

22
00:01:17,570 --> 00:01:23,230
آیا کسی برای اولین بار سطح بالا بسیار سریع کلی از چه نوع حباب را می خواهید؟

23
00:01:25,950 --> 00:01:33,020
[دانشجوی] شما اساسا از طریق هر یک از عناصر و بررسی عناصر چند.

24
00:01:33,020 --> 00:01:37,150
اگر آنها از جایی که شما آنها را مبادله، پس از آن عناصر چند بعدی و به همین ترتیب شما را بررسی کنید.

25
00:01:37,150 --> 00:01:40,770
هنگامی که شما به پایان می رسند، پس از آن شما می دانیم که بزرگترین عنصر در پایان قرار می گیرد،

26
00:01:40,770 --> 00:01:42,750
بنابراین شما را نادیده می گیرند که یکی از پس از آن شما را در رفتن را از طریق،

27
00:01:42,750 --> 00:01:48,490
و هر بار شما باید به بررسی یکی کمتر عنصر تا زمانی که شما می توانید بدون هیچ تغییری. >> آره.

28
00:01:48,490 --> 00:01:58,470
این مرتب سازی بر حباب نامیده می شود زیرا اگر آرایه را در کنار خود تلنگر آن را به بالا و پایین، عمودی،

29
00:01:58,470 --> 00:02:03,100
پس از آن ارزش های بزرگ به پایین و نزول مقادیر کوچک حباب به بالا.

30
00:02:03,100 --> 00:02:05,210
که چگونه آن را از آنجا نام خود را.

31
00:02:05,210 --> 00:02:08,220
و آره، شما فقط از طریق رفتن.

32
00:02:08,220 --> 00:02:11,190
شما در حفظ و رفتن را از طریق آرایه، مبادله ارزش بزرگتر

33
00:02:11,190 --> 00:02:14,040
برای بدست آوردن بزرگترین ارزش ها به پایین.

34
00:02:14,040 --> 00:02:17,500
>> چرا آن را مربع N O؟

35
00:02:18,690 --> 00:02:24,620
اول، آیا هر کسی می خواهم بگویم چرا از آن O از N مربع؟

36
00:02:24,620 --> 00:02:28,760
[دانشجو] از آنجا که برای هر اجرا آن می رود N

37
00:02:28,760 --> 00:02:32,100
شما فقط می توانید اطمینان حاصل کنید که شما بزرگترین عنصر تمام راه را به پایین باشد،

38
00:02:32,100 --> 00:02:35,230
سپس شما باید به تکرار است که به عنوان بسیاری از عناصر. >> آره.

39
00:02:35,230 --> 00:02:41,800
پس در ذهن داشته باشید چه بزرگ O به معنی و چه به معنای امگا بزرگ است.

40
00:02:41,800 --> 00:02:50,560
O بزرگ است مثل حد بالا در مورد چگونه آهسته آن را در واقع می تواند اجرا شود.

41
00:02:50,560 --> 00:02:58,990
بنابراین با گفتن O آن از مربع N، O از N و یا دیگری آن را قادر به اجرا

42
00:02:58,990 --> 00:03:02,640
در زمان خطی است، اما از آن O از N نبات

43
00:03:02,640 --> 00:03:06,390
دلیل آن است که توسط O از N نبات محدود شده است.

44
00:03:06,390 --> 00:03:12,300
اگر آن را توسط O مربع N محدود، و سپس آن را توسط N نبات نیز محدود شده است.

45
00:03:12,300 --> 00:03:20,280
پس از آن نفر مربع، و در بدترین حالت آن را می توانید انجام دهید بهتر از مربع N،

46
00:03:20,280 --> 00:03:22,830
به همین دلیل است که آن O از N مربع است.

47
00:03:22,830 --> 00:03:31,200
بنابراین برای دیدن ریاضی اندکی که چگونه از آن بیرون می آید به مربع،

48
00:03:31,200 --> 00:03:40,530
اگر ما پنج چیز را در لیست ما، اولین بار که چگونه بسیاری از معاوضه می توانیم به طور بالقوه نیاز به

49
00:03:40,530 --> 00:03:47,170
به منظور رسیدن به این؟ اجازه دهید در واقع تنها -

50
00:03:47,170 --> 00:03:52,040
چگونه بسیاری از معاوضه می خواهیم در اولین اجرا از مرتب کردن حباب را از طریق آرایه؟

51
00:03:52,040 --> 00:03:53,540
[دانشجوی] n - 1. >> آره.

52
00:03:53,540 --> 00:03:58,340
>> اگر 5 عنصر وجود دارد، ما در حال رفتن به نیاز به n - 1 است.

53
00:03:58,340 --> 00:04:01,100
سپس در دوم که چگونه بسیاری از معاوضه می خواهیم را به؟

54
00:04:01,100 --> 00:04:03,440
[دانشجوی] n - 2 است. >> آره.

55
00:04:03,440 --> 00:04:11,640
و سوم به n - 3، و پس از آن برای راحتی من دو تاریخ و زمان آخرین ارسال

56
00:04:11,640 --> 00:04:15,270
و سپس ما در حال رفتن به نیاز به ایجاد 2 معاوضه و 1 مبادله.

57
00:04:15,270 --> 00:04:19,899
من حدس می زنم یکی از آخرین ممکن است یا ممکن است در واقع لازم نیست اتفاق می افتد.

58
00:04:19,899 --> 00:04:22,820
آیا این یک مبادله است؟ نمی دانم.

59
00:04:22,820 --> 00:04:26,490
بنابراین این کل مقدار سواپ یا حداقل مقایسه شما را.

60
00:04:26,490 --> 00:04:29,910
حتی اگر شما مبادله نیست، شما هنوز هم نیاز به مقایسه ارزش است.

61
00:04:29,910 --> 00:04:33,910
بنابراین N وجود دارد 1 - مقایسه در اولین اجرا از طریق آرایه.

62
00:04:33,910 --> 00:04:42,050
اگر این چیزها را تنظیم مجدد، اجازه دهید در واقع این شش چیز را تا چیزهایی پشته سادگی.

63
00:04:42,050 --> 00:04:44,790
و پس از آن من 3، انجام 2، 1.

64
00:04:44,790 --> 00:04:49,910
پس فقط چینش دوباره این مبالغ، ما می خواهیم تا ببینید که چگونه بسیاری از مقایسه ما را

65
00:04:49,910 --> 00:04:52,700
در کل الگوریتم.

66
00:04:52,700 --> 00:04:56,550
بنابراین اگر ما را به این بچه ها را در اینجا،

67
00:04:56,550 --> 00:05:07,470
پس ما هنوز فقط جمع مقایسه با این حال بسیاری وجود دارد.

68
00:05:07,470 --> 00:05:13,280
اما اگر این جمع و به این جمع ما و این مجموع را،

69
00:05:13,280 --> 00:05:18,130
هنوز هم مشکل مشابه دارد. ما فقط به آن گروه خاص خلاصه.

70
00:05:18,130 --> 00:05:22,400
>> بنابراین در حال حاضر ما در حال جمع 3 نفر است. این فقط 3 نفر نیست.

71
00:05:22,400 --> 00:05:27,650
این همیشه خواهد بود N / 2 نفر است.

72
00:05:27,650 --> 00:05:29,430
بنابراین در اینجا ما اتفاق می افتد به 6.

73
00:05:29,430 --> 00:05:34,830
اگر ما تا به حال 10 همه چیز، پس از آن ما می تواند این گروه را به مدت 5 جفت مختلف از چیزهایی

74
00:05:34,830 --> 00:05:37,180
و در نهایت با N + N + N + N + N است.

75
00:05:37,180 --> 00:05:45,840
بنابراین شما همیشه برای گرفتن N / 2 N، و پس از این خواهیم آن را به نقطه N مربع / 2.

76
00:05:45,840 --> 00:05:48,890
و بنابراین، حتی اگر آن عامل نیم، که اتفاق می افتد می آیند در

77
00:05:48,890 --> 00:05:54,190
به دلیل این واقعیت است که از طریق هر یک از تکرار بیش از آرایه مقایسه می کنیم 1 کمتر

78
00:05:54,190 --> 00:05:58,040
به طوری که ما بیش از 2 است، اما هنوز هم نفر مربع است.

79
00:05:58,040 --> 00:06:01,650
ما در مورد عامل ثابت نیم اهمیتی نمی دهند.

80
00:06:01,650 --> 00:06:07,760
بنابراین بسیاری از چیزهای O بزرگ مثل این متکی به نوع انجام این کار مرتب کردن بر اساس ریاضی،

81
00:06:07,760 --> 00:06:12,260
انجام مبالغ حساب و چیزهای سری هندسی،

82
00:06:12,260 --> 00:06:17,750
اما بسیاری از آنها در این دوره بسیار سرراست است.

83
00:06:17,750 --> 00:06:19,290
باشه.

84
00:06:19,290 --> 00:06:24,430
چرا مرتب سازی بر اساس درج امگا از N؟ چه امگا چیست؟

85
00:06:24,430 --> 00:06:27,730
[دو دانشجوی صحبت کردن در یک بار - ناخوانا] >> آره.

86
00:06:27,730 --> 00:06:30,630
امگا شما می توانید به عنوان حد پایین فکر می کنم.

87
00:06:30,630 --> 00:06:36,550
>> بنابراین هر چقدر هم که کارآمد خود را مرتب کردن بر اساس الگوریتم درج شده است،

88
00:06:36,550 --> 00:06:41,810
صرف نظر از لیست که در به تصویب رسید، آن را همواره برای مقایسه حداقل N همه چیز

89
00:06:41,810 --> 00:06:44,620
و یا آن را به بیش از چیزهای N تکرار.

90
00:06:44,620 --> 00:06:47,280
این است که چرا؟

91
00:06:47,280 --> 00:06:51,190
[دانشجوی] از آنجا که اگر این لیست در حال حاضر مرتب شده اند، و سپس از طریق تکرار اول

92
00:06:51,190 --> 00:06:54,080
شما تنها می توانید که اولین عنصر بسیار است که حداقل تضمین،

93
00:06:54,080 --> 00:06:56,490
و تکرار دوم شما فقط می توانید در دو مورد اول تضمین

94
00:06:56,490 --> 00:07:00,010
زیرا شما نمی دانید که بقیه از فهرست طبقه بندی شده اند. >> آره.

95
00:07:00,010 --> 00:07:08,910
اگر شما در یک لیست کاملا طبقه بندی شده اند منتقل می کند، حداقل شما را برای رفتن بیش از همه عناصر

96
00:07:08,910 --> 00:07:12,180
برای دیدن آن احتیاج به اطراف منتقل می شود.

97
00:07:12,180 --> 00:07:14,720
بنابراین عبور از روی لیست و گفت: آه، این است که در حال حاضر طبقه بندی شده اند.

98
00:07:14,720 --> 00:07:18,240
را برای شما به آن را غیر ممکن می دانم که این طبقه بندی شده اند تا زمانی که هر یک از عناصر را چک کنید

99
00:07:18,240 --> 00:07:20,660
برای دیدن است که آنها به منظور طبقه بندی شده اند.

100
00:07:20,660 --> 00:07:25,290
بنابراین کمتر محدود در مرتب سازی بر درج امگا از n است.

101
00:07:25,290 --> 00:07:28,210
چه بدترین حالت زمان اجرای مرتب سازی بر اساس ادغام،

102
00:07:28,210 --> 00:07:31,390
بدترین حالت O بزرگ دوباره؟

103
00:07:31,390 --> 00:07:37,660
بنابراین در بدترین حالت، چگونه به مرتب کردن بر اساس ادغام اجرا شده است؟

104
00:07:42,170 --> 00:07:43,690
[دانشجوی] N ورود N. >> آره.

105
00:07:43,690 --> 00:07:49,990
سریع ترین الگوریتم های مرتب سازی به طور کلی عبارتند از: N ورود N. شما نمی توانید انجام دهید بهتر است.

106
00:07:51,930 --> 00:07:55,130
>> موارد خاص وجود دارد، و اگر ما هم امروز - اما ما احتمالا won't -

107
00:07:55,130 --> 00:07:59,330
ما می تواند کند که بهتر از ورود N N را ببینید.

108
00:07:59,330 --> 00:08:04,050
اما در حالت کلی، شما نمی توانید بهتر از ورود N N.

109
00:08:04,050 --> 00:08:09,680
و ادغام مرتب کردن بر اساس اتفاق می افتد که یکی از شما باید برای این دوره است که n log n استفاده می دانیم.

110
00:08:09,680 --> 00:08:13,260
و بنابراین، ما در واقع خواهید پیاده سازی می شود که امروز است.

111
00:08:13,260 --> 00:08:18,070
و در نهایت، در بیش از سه جمله، چگونه انتخاب کار مرتب کردن بر اساس؟

112
00:08:18,070 --> 00:08:20,370
آیا کسی که می خواهید به جواب بدهد، و من جملات شما را به حساب

113
00:08:20,370 --> 00:08:22,390
چرا که اگر شما بیش از 3 -

114
00:08:25,530 --> 00:08:28,330
آیا کسی به یاد داشته باشید مرتب کردن بر اساس انتخاب؟

115
00:08:31,280 --> 00:08:37,809
مرتب کردن بر اساس انتخاب است که معمولا بسیار آسان است فقط از نام به یاد داشته باشید.

116
00:08:37,809 --> 00:08:45,350
شما فقط بیش از آرایه تکرار، هر چه که بزرگترین ارزش است و یا کوچکترین -

117
00:08:45,350 --> 00:08:47,290
هر سفارش شما مرتب سازی شوید.

118
00:08:47,290 --> 00:08:50,750
بنابراین می گویند ما در حال مرتب سازی از کوچکترین تا بزرگترین.

119
00:08:50,750 --> 00:08:55,250
شما بیش از آرایه تکرار، به دنبال هر عنصر حداقل،

120
00:08:55,250 --> 00:08:59,750
آن را انتخاب کنید، و سپس آن را فقط به مبادله آنچه در وهله اول.

121
00:08:59,750 --> 00:09:04,090
و سپس در پاس دوم طول آرایه، حداقل برای این عنصر را دوباره نگاه می کنم،

122
00:09:04,090 --> 00:09:07,490
آن را انتخاب کنید، و سپس مبادله آن را با آنچه که در مقام دوم است.

123
00:09:07,490 --> 00:09:10,650
بنابراین ما فقط به چیدن و انتخاب حداقل ارزش

124
00:09:10,650 --> 00:09:16,050
و قرار دادن آنها را در مقابل از آرایه تا زمانی که طبقه بندی شده اند.

125
00:09:19,210 --> 00:09:21,560
سوالات مطرح شده در آن؟

126
00:09:21,560 --> 00:09:25,710
>> این به ناچار در اشکال شما باید برای پر کردن زمانی که شما در حال ارسال pset ظاهر می شود.

127
00:09:29,010 --> 00:09:32,360
اینها اساسا پاسخ به این.

128
00:09:32,360 --> 00:09:34,230
خوب، بنابراین در حال حاضر مشکلات برنامه نویسی است.

129
00:09:34,230 --> 00:09:40,140
من در حال حاضر از طریق ایمیل فرستاده می شود - آیا هر کسی که ایمیل می کنید؟ باشه.

130
00:09:40,140 --> 00:09:46,630
من در حال حاضر از طریق ایمیل فرستاده می شود، فضایی که ما قصد داریم با استفاده از

131
00:09:46,630 --> 00:09:52,120
و اگر شما بر روی نام من کلیک کنید - بنابراین من فکر می کنم من قصد دارم تا در پایین

132
00:09:52,120 --> 00:09:57,170
به دلیل عقب R - اما اگر شما بر روی نام من کلیک کنید شما 2 تجدید نظر را ببینید.

133
00:09:57,170 --> 00:10:02,650
ویرایشهای (1) برای رفتن به من در حال حاضر کپی و کد را در فاصله جا به جا

134
00:10:02,650 --> 00:10:06,900
برای چیزی که جستجو شما قصد به پیاده سازی.

135
00:10:06,900 --> 00:10:10,540
و تجدید نظر 2 خواهد بود چیزی که مرتب سازی بر اساس است که ما بعد از آن پیاده سازی است.

136
00:10:10,540 --> 00:10:15,770
بنابراین شما می توانید بر روی ویرایشهای من 1 کلیک کنید و از کار وجود دارد.

137
00:10:17,350 --> 00:10:22,060
و در حال حاضر ما می خواهیم به پیاده سازی جستجو دودویی.

138
00:10:22,060 --> 00:10:26,470
>> آیا هر کسی مایل به سطح بالا توضیح شبه فقط به

139
00:10:26,470 --> 00:10:31,440
از آنچه که ما در حال رفتن به برای جستجو؟ آره.

140
00:10:31,440 --> 00:10:36,170
[دانشجوی] شما فقط وسط آرایه و اگر آنچه شما به دنبال آن هستید

141
00:10:36,170 --> 00:10:38,650
کمتر از آن و یا بیشتر از آن.

142
00:10:38,650 --> 00:10:41,080
و اگر آن را کمتر، شما را به نیمه است که کمتر

143
00:10:41,080 --> 00:10:44,750
و اگر آن را بیشتر، شما را به نیمه است که بیشتر بروید و دوباره تکرار کنید تا زمانی که شما فقط یک چیز است.

144
00:10:44,750 --> 00:10:46,570
[Bowden] آره.

145
00:10:46,570 --> 00:10:51,320
توجه کنید که آرایه ای از اعداد است ما در حال حاضر طبقه بندی شده اند.

146
00:10:51,320 --> 00:10:57,190
و به طوری که بدان معنی است که ما می توانیم استفاده از آن می گیرد و ما برای اولین بار می تواند چک،

147
00:10:57,190 --> 00:11:00,390
خوب، من به دنبال شماره 50.

148
00:11:00,390 --> 00:11:03,720
بنابراین من می تواند به وسط بروید.

149
00:11:03,720 --> 00:11:07,380
میانه سخت است برای تعریف هنگامی که آن را به یک تعداد حتی از چیزهایی،

150
00:11:07,380 --> 00:11:10,820
اما اجازه دهید فقط می گویند ما همیشه باید به وسط کوتاه.

151
00:11:10,820 --> 00:11:14,420
بنابراین در اینجا ما 8 همه چیز، بنابراین میانه خواهد بود 16.

152
00:11:14,420 --> 00:11:17,330
برای 50 من به دنبال، به طوری که 50 از 16 بزرگتر است.

153
00:11:17,330 --> 00:11:21,310
بنابراین در حال حاضر من اساسا می تواند به عنوان این عناصر آرایه من را درمان کنند.

154
00:11:21,310 --> 00:11:23,450
من می توانم به دور انداختن همه چیز را از 16 بیش از.

155
00:11:23,450 --> 00:11:27,440
آرایه من فقط این 4 عنصر، و من تکرار می کنم.

156
00:11:27,440 --> 00:11:31,910
بنابراین پس از آن من می خواهم برای پیدا کردن وسط دوباره، که می شود 42.

157
00:11:31,910 --> 00:11:34,730
42 کمتر از 50 است، بنابراین من می تواند به دور انداختن این دو عنصر است.

158
00:11:34,730 --> 00:11:36,890
این آرایه باقی مانده است.

159
00:11:36,890 --> 00:11:38,430
من قصد دارم برای پیدا کردن وسط دوباره.

160
00:11:38,430 --> 00:11:42,100
من حدس می زنم 50 یک مثال بد بود چون من همیشه پرتاب بود دور همه چیز را به سمت چپ،

161
00:11:42,100 --> 00:11:48,280
اما به همان اندازه، اگر من به دنبال چیزی

162
00:11:48,280 --> 00:11:52,100
و آن را کمتر از عنصر من در حال حاضر به دنبال

163
00:11:52,100 --> 00:11:55,080
پس از آن من قصد دارم به دور انداختن همه چیز را به سمت راست.

164
00:11:55,080 --> 00:11:58,150
بنابراین در حال حاضر ما نیاز به پیاده سازی.

165
00:11:58,150 --> 00:12:02,310
توجه داشته باشید که ما نیاز به تصویب در اندازه.

166
00:12:02,310 --> 00:12:06,730
ما نیز به اندازه سخت کد می تواند نیاز نیست.

167
00:12:06,730 --> 00:12:11,640
بنابراین اگر ما از آن خلاص شدن از شر # تعریف -

168
00:12:19,630 --> 00:12:21,430
باشه.

169
00:12:21,430 --> 00:12:27,180
چگونه می توانم به سادگی بیرون شکل چه اندازه از آرایه اعداد در حال حاضر؟

170
00:12:27,180 --> 00:12:30,950
>> چگونه بسیاری از عناصر موجود در آرایه اعداد هستند؟

171
00:12:30,950 --> 00:12:33,630
[دانشجو] اعداد، براکت، طول؟

172
00:12:33,630 --> 00:12:36,600
[Bowden] که در C. وجود ندارد

173
00:12:36,600 --> 00:12:38,580
نیاز دارند. طول.

174
00:12:38,580 --> 00:12:42,010
آرایه خصوصیات را نداشته باشند، بنابراین هیچ اموال طول آرایه وجود دارد

175
00:12:42,010 --> 00:12:45,650
که فقط می خواهد با این حال شما زمانی آن اتفاق می افتد.

176
00:12:48,180 --> 00:12:51,620
[دانشجو] ببینید که چه مقدار حافظه آن است و چقدر تقسیم - >> آره.

177
00:12:51,620 --> 00:12:55,810
پس چگونه می تواند ما را ببینید که چه مقدار حافظه آن است؟ >> [دانشجو] Sizeof. >> بله، sizeof.

178
00:12:55,810 --> 00:13:01,680
Sizeof اپراتور که برای بازگشت به اندازه آرایه اعداد است.

179
00:13:01,680 --> 00:13:10,060
و که می شود با این حال بسیاری از اعداد صحیح بار به اندازه یک عدد صحیح وجود دارد

180
00:13:10,060 --> 00:13:14,050
از آن چه مقدار حافظه در واقع مصرف تا.

181
00:13:14,050 --> 00:13:17,630
پس اگر من می خواهم تعدادی از چیزهایی در آرایه،

182
00:13:17,630 --> 00:13:20,560
پس از آن من می خواهم به اندازه یک عدد صحیح تقسیم است.

183
00:13:22,820 --> 00:13:26,010
باشه. به طوری که به شما اجازه می دهد تا من در اندازه منتقل نمائید.

184
00:13:26,010 --> 00:13:29,430
چرا من باید به اندازه عبور در همه؟

185
00:13:29,430 --> 00:13:38,570
چرا من نمی توانم فقط اینجا اندازه نوع int = sizeof (انبار کاه) / sizeof (هوشمند)؟

186
00:13:38,570 --> 00:13:41,490
چرا این کار نمی کند؟

187
00:13:41,490 --> 00:13:44,470
[دانشجو] آن را یک متغیر جهانی نیست.

188
00:13:44,470 --> 00:13:51,540
[Bowden] کومه علف خشک وجود دارد و ما در حال عبور در اعداد به عنوان انبار کاه،

189
00:13:51,540 --> 00:13:54,700
و این نوع foreshadowing از آنچه که برای آمدن به راه است. آره.

190
00:13:54,700 --> 00:14:00,170
[دانشجو] کومه علف خشک فقط اشاره به آن است، پس از آن باز خواهد گشت چقدر بزرگ است که مرجع است.

191
00:14:00,170 --> 00:14:02,150
آره.

192
00:14:02,150 --> 00:14:09,000
من در سخنرانی شک دارند که شما را دیده ام پشته اما واقعا، درست است؟

193
00:14:09,000 --> 00:14:11,270
ما فقط در مورد آن سخن گفته شده است.

194
00:14:11,270 --> 00:14:16,090
پس پشته می باشد که در آن تمامی متغیر ها ذخیره می شود.

195
00:14:16,090 --> 00:14:19,960
>> هر حافظه اختصاص داده شده است که برای متغیرهای محلی در پشته،

196
00:14:19,960 --> 00:14:24,790
و هر تابع می شود، فضای خود را در پشته ها، قاب پشته خود را همان چیزی است که آن را به نام.

197
00:14:24,790 --> 00:14:31,590
بنابراین اصلی دارای قاب پشته آن است، و در داخل آن وجود دارد این آرایه اعداد،

198
00:14:31,590 --> 00:14:34,270
و آن را به sizeof (شماره) خواهد بود.

199
00:14:34,270 --> 00:14:38,180
رفتن به اندازه عدد تقسیم بر اساس اندازه از عناصر،

200
00:14:38,180 --> 00:14:42,010
اما این همه زندگی در قاب پشته اصلی.

201
00:14:42,010 --> 00:14:45,190
وقتی ما تماس جستجو، جستجو می شود قاب پشته خود را،

202
00:14:45,190 --> 00:14:48,840
فضای خود را برای ذخیره تمام متغیرهای محلی خود را.

203
00:14:48,840 --> 00:14:56,420
اما این استدلال - تا انبار کاه یک کپی از کل این آرایه نیست.

204
00:14:56,420 --> 00:15:00,990
ما را در کل آرایه به عنوان یک کپی به جستجو منتقل نکنید.

205
00:15:00,990 --> 00:15:04,030
فقط عبور یک مرجع به آن آرایه می باشد.

206
00:15:04,030 --> 00:15:11,470
جستجو می تواند این تعداد از طریق این مرجع دسترسی داشته باشید.

207
00:15:11,470 --> 00:15:17,100
این هنوز هم دسترسی به چیزهایی که در داخل قاب پشته اصلی زندگی می کنند،

208
00:15:17,100 --> 00:15:22,990
اما در واقع، هنگامی که ما را به اشاره گر، که به زودی باید،

209
00:15:22,990 --> 00:15:24,980
این همان چیزی است که اشاره گر هستند.

210
00:15:24,980 --> 00:15:29,400
اشاره گرها فقط به چیزهایی است، و شما می توانید اشاره گر برای دسترسی به چیزهایی استفاده کنید

211
00:15:29,400 --> 00:15:32,030
که در قاب پشته چیزهای دیگر هستند.

212
00:15:32,030 --> 00:15:37,660
بنابراین حتی اگر اعداد به بخش اصلی محلی است، ما هنوز هم می توانید آن را از طریق این اشاره گر دسترسی داشته باشید.

213
00:15:37,660 --> 00:15:41,770
اما از آنجا که این فقط یک اشاره گر است و آن را فقط به یک مرجع،

214
00:15:41,770 --> 00:15:45,040
sizeof (انبار کاه) فقط به اندازه از مرجع خود را بر می گرداند.

215
00:15:45,040 --> 00:15:47,950
این کار به اندازه چیزی که آن را با اشاره به بازگشت نیست.

216
00:15:47,950 --> 00:15:51,110
اندازه واقعی از اعداد را بر نمی گرداند.

217
00:15:51,110 --> 00:15:55,660
و بنابراین این است که رفتن به کار به عنوان ما می خواهیم آن را به.

218
00:15:55,660 --> 00:15:57,320
>> سوالات مطرح شده در آن؟

219
00:15:57,320 --> 00:16:03,250
اشاره گرها خواهد شد در جزئیات به طور معناداری بیشتر لخته در هفته های رفته آمده است.

220
00:16:06,750 --> 00:16:13,740
و به همین دلیل است که بسیاری از چیزهایی که شما را مشاهده کنید، بسیاری از چیزهایی جستجو و یا همه چیز مرتب سازی بر اساس،

221
00:16:13,740 --> 00:16:16,990
تقریبا همه آنها در حال رفتن به نیاز را به اندازه واقعی آرایه،

222
00:16:16,990 --> 00:16:20,440
چرا که در C، ما هیچ ایده چه اندازه از آرایه است.

223
00:16:20,440 --> 00:16:22,720
شما با عضویت در این سایت باید به صورت دستی آن را رد شوید.

224
00:16:22,720 --> 00:16:27,190
و شما دستی در کل آرایه نمی تواند عبور زیرا شما فقط در مرجع عبور

225
00:16:27,190 --> 00:16:30,390
و آن را می توانید از مرجع می کنید.

226
00:16:30,390 --> 00:16:32,300
باشه.

227
00:16:32,300 --> 00:16:38,160
بنابراین در حال حاضر ما می خواهیم برای پیاده سازی آنچه که قبلا توضیح داده شد.

228
00:16:38,160 --> 00:16:41,530
شما می توانید برای یک دقیقه بر روی آن کار می کنند،

229
00:16:41,530 --> 00:16:45,250
و شما لازم نیست که به نگرانی در مورد همه چیز کاملا 100٪ کار می کند.

230
00:16:45,250 --> 00:16:51,410
فقط تا ارسال شبه نصف چگونه فکر می کنید که باید کار.

231
00:16:52,000 --> 00:16:53,630
باشه.

232
00:16:53,630 --> 00:16:56,350
بدون نیاز به طور کامل انجام نشده است.

233
00:16:56,350 --> 00:17:02,380
اما آیا هر کسی احساس راحتی با آنچه که تا کنون،

234
00:17:02,380 --> 00:17:05,599
مانند چیزی است که ما می توانیم با هم کار می کنند؟

235
00:17:05,599 --> 00:17:09,690
آیا کسی داوطلب؟ یا من به طور تصادفی انتخاب کنید.

236
00:17:12,680 --> 00:17:18,599
این را ندارد که حق با هر اقدام، اما چیزی است که ما می توانیم به یک دولت کار را تغییر دهید.

237
00:17:18,599 --> 00:17:20,720
[دانشجو] مطمئنا. >> درست است.

238
00:17:20,720 --> 00:17:27,220
بنابراین می تواند تجدید نظر را ذخیره کنید با کلیک بر روی آیکون کوچک ذخیره شده است.

239
00:17:27,220 --> 00:17:29,950
تو Ramya، درست است؟ >> [دانشجو] آره. >> [Bowden] باشه.

240
00:17:29,950 --> 00:17:35,140
بنابراین در حال حاضر من می توانم تجدید نظر خود را مشاهده و هر کس می تواند جلو و تجدید نظر است.

241
00:17:35,140 --> 00:17:38,600
و در اینجا ما باید - باشه.

242
00:17:38,600 --> 00:17:43,160
بنابراین Ramya رفت و با راه حل بازگشتی، که قطعا یک راه حل معتبر است.

243
00:17:43,160 --> 00:17:44,970
دو راه وجود دارد شما می توانید این مشکل را انجام دهد.

244
00:17:44,970 --> 00:17:48,060
شما هم می توانید آن را مکررا و یا به صورت بازگشتی انجام دهد.

245
00:17:48,060 --> 00:17:53,860
اکثر مشکلات شما روبرو می شوند که می تواند انجام شود به صورت بازگشتی نیز می تواند انجام شود تکرار شونده است.

246
00:17:53,860 --> 00:17:58,510
بنابراین در اینجا ما آن را به صورت بازگشتی انجام می شود.

247
00:17:58,510 --> 00:18:03,730
>> آیا کسی می خواهید به تعریف آنچه در آن به معنی ایجاد یک تابع بازگشتی؟

248
00:18:07,210 --> 00:18:08,920
[دانشجو] هنگامی که شما یک تابع خود تماس بگیرید

249
00:18:08,920 --> 00:18:13,470
و پس از آن خود را تا زمانی که بیرون می آید درست است تماس بگیرید. >> آره.

250
00:18:13,470 --> 00:18:17,680
تابع بازگشتی تابعی که خود را فرا می خواند.

251
00:18:17,680 --> 00:18:24,140
سه چیز بزرگ وجود دارد که یک تابع بازگشتی باید.

252
00:18:24,140 --> 00:18:27,310
برای اولین بار است که به وضوح، آن را به خود فرا می خواند.

253
00:18:27,310 --> 00:18:29,650
دوم، در مورد پایه است.

254
00:18:29,650 --> 00:18:33,390
بنابراین در برخی از نقطه تابع نیاز برای جلوگیری از تماس خود،

255
00:18:33,390 --> 00:18:35,610
و این چیزی است که برای مورد پایه است.

256
00:18:35,610 --> 00:18:43,860
بنابراین در اینجا ما می دانیم که ما باید به توقف، ما را در ما جستجو

257
00:18:43,860 --> 00:18:48,150
زمانی که شروع به پایان برابر است - و ما رو به چه معنی می دهد.

258
00:18:48,150 --> 00:18:52,130
اما در نهایت، آخرین چیزی که مهم است از توابع بازگشتی:

259
00:18:52,130 --> 00:18:59,250
توابع به نحوی باید در مورد پایه نزدیک شود.

260
00:18:59,250 --> 00:19:04,140
مانند اگر شما در واقع به روز رسانی هر زمانی که شما را به تماس دوم بازگشتی،

261
00:19:04,140 --> 00:19:07,880
اگر شما به معنای واقعی کلمه فقط فراخوانی تابع با استدلال مشابه

262
00:19:07,880 --> 00:19:10,130
و هیچ متغیر های جهانی تغییر کرده است و یا هر چیزی،

263
00:19:10,130 --> 00:19:14,430
به شما خواهد شد در مورد پایه برسد، که در آن مورد که بد است.

264
00:19:14,430 --> 00:19:17,950
بازگشت بی نهایت و یک سرریز پشته خواهد بود.

265
00:19:17,950 --> 00:19:24,330
اما در اینجا ما می بینیم که به روز رسانی در حال وقوع است از آنجایی که ما در حال به روز رسانی شروع + پایان / 2،

266
00:19:24,330 --> 00:19:28,180
ما در حال به روز رسانی استدلال نهایی در اینجا، ما در حال به روز رسانی استدلال شروع کنید.

267
00:19:28,180 --> 00:19:32,860
بنابراین در تمام تماس های بازگشتی چیزی است که ما در حال به روز رسانی است. باشه.

268
00:19:32,860 --> 00:19:38,110
آیا شما می خواهید به ما راه رفتن را از طریق راه حل های خود را؟ >> مطمئنا.

269
00:19:38,110 --> 00:19:44,270
من با استفاده از SearchHelp به طوری که هر بار که من را به این فراخوانی تابع

270
00:19:44,270 --> 00:19:47,910
من شروع از جایی که من به دنبال در آرایه و پایان

271
00:19:47,910 --> 00:19:49,380
از جایی که من هستم به دنبال آرایه.

272
00:19:49,380 --> 00:19:55,330
>> در هر مرحله که در آن گفت که این عنصر میانه، که شروع + پایان / 2،

273
00:19:55,330 --> 00:19:58,850
است که برابر به آنچه ما به دنبال آن هستید؟

274
00:19:58,850 --> 00:20:04,650
و اگر چنین باشد، پس از آن که ما آن را در بر داشت، و من حدس می زنم که می شود منتقل می شود تا به سطح بازگشت.

275
00:20:04,650 --> 00:20:12,540
و در صورتی که این درست نیست، و سپس بررسی کنید که آیا مقدار متوسط ​​از آرایه بسیار بزرگ است،

276
00:20:12,540 --> 00:20:19,320
که در این صورت ما در نیمه سمت چپ آرایه با رفتن از آغاز تا شاخص متوسط ​​نگاه کنید.

277
00:20:19,320 --> 00:20:22,710
و در غیر این صورت ما در نیمه نهایی.

278
00:20:22,710 --> 00:20:24,740
[Bowden] باشه.

279
00:20:24,740 --> 00:20:27,730
خیلی خوب است.

280
00:20:27,730 --> 00:20:36,640
خوب، پس همه چیز یک زن و شوهر، و در واقع، این یک چیز بسیار سطح بالا

281
00:20:36,640 --> 00:20:41,270
که شما هرگز نیاز به این دوره می دانم، اما درست است.

282
00:20:41,270 --> 00:20:46,080
توابع بازگشتی، شما همیشه می شنویم که آنها به یک معامله بد

283
00:20:46,080 --> 00:20:51,160
چرا که اگر شما به صورت بازگشتی تماس خود را بیش از حد بسیاری از بار، شما سرریز پشته

284
00:20:51,160 --> 00:20:54,990
از آنجا که، همانطور که قبلا گفتم، هر تابع می شود قاب پشته خاص خود را دارد.

285
00:20:54,990 --> 00:20:59,500
بنابراین هر فراخوانی تابع بازگشتی می شود قاب پشته خاص خود را دارد.

286
00:20:59,500 --> 00:21:04,140
بنابراین اگر شما 1،000 تماس بازگشتی، شما 1000 فریم پشته،

287
00:21:04,140 --> 00:21:08,390
و به سرعت شما را به داشتن بیش از حد بسیاری از قاب پشته و همه چیز فقط شکستن منجر شود.

288
00:21:08,390 --> 00:21:13,480
بنابراین به همین دلیل است که توابع بازگشتی به طور کلی بد هستند.

289
00:21:13,480 --> 00:21:19,370
اما یک زیر مجموعه خوب از توابع بازگشتی وجود دارد به نام دم توابع بازگشتی،

290
00:21:19,370 --> 00:21:26,120
و این اتفاق می افتد به عنوان مثال از یک جایی که اگر کامپایلر متوجه این

291
00:21:26,120 --> 00:21:29,920
و آن را باید، من فکر می کنم - در صدای جرنگ جرنگ اگر شما منتقل-O2 پرچم

292
00:21:29,920 --> 00:21:33,250
سپس آن را متوجه خواهید شد این دم بازگشتی است و همه چیز خوب است.

293
00:21:33,250 --> 00:21:40,050
>> این قاب پشته همان بارها و بارها استفاده مجدد برای هر تماس بازگشتی.

294
00:21:40,050 --> 00:21:47,010
و بنابراین از آنجایی که شما با استفاده از همان قاب پشته، شما لازم نیست که به نگرانی در مورد

295
00:21:47,010 --> 00:21:51,690
همیشه سرشار، پشته و در همان زمان، مثل شما قبل از گفت،

296
00:21:51,690 --> 00:21:56,380
جایی که شما را به راست، سپس آن را به بازگشت از این قاب پشته

297
00:21:56,380 --> 00:22:01,740
و تماس 10 به SearchHelp به بازگشت به 9، به بازگشت به 8 است.

298
00:22:01,740 --> 00:22:05,360
به طوری که نیازی نیست که اتفاق می افتد هنگامی که توابع دم بازگشتی.

299
00:22:05,360 --> 00:22:13,740
و بنابراین، آنچه باعث می شود این دم تابع بازگشتی است توجه داشته باشید که برای هر تماس داده شده به searchHelp

300
00:22:13,740 --> 00:22:18,470
تماس بازگشتی که آن را ساخت، آن چیزی است که آن را بازگشت.

301
00:22:18,470 --> 00:22:25,290
بنابراین در اولین تماس به SearchHelp، ما یا بلافاصله بازگشت کاذب،

302
00:22:25,290 --> 00:22:29,590
بلافاصله به راست، و یا ما را به یک تماس بازگشتی به SearchHelp

303
00:22:29,590 --> 00:22:33,810
که در آن چیزی است که ما در حال بازگشت به همان چیزی است که تماس در حال بازگشت است.

304
00:22:33,810 --> 00:22:51,560
و ما می توانیم این کار را انجام دهند که اگر ما چیزی شبیه به نوع int x = SearchHelp، بازگشت X * 2،

305
00:22:51,560 --> 00:22:55,440
فقط برخی از تغییرات تصادفی.

306
00:22:55,440 --> 00:23:01,470
>> بنابراین در حال حاضر این بازگشتی تماس بگیرید، این نوع int x = تماس SearchHelp بازگشتی،

307
00:23:01,470 --> 00:23:05,740
دیگر دم بازگشتی به دلیل آن را در واقع مجبور به بازگشت

308
00:23:05,740 --> 00:23:10,400
برگشت به یک قاب پشته قبلی به طوری که که در تماس قبلی به تابع

309
00:23:10,400 --> 00:23:13,040
می تواند پس از آن انجام کاری با مقدار بازگشتی.

310
00:23:13,040 --> 00:23:22,190
پس این دم بازگشتی نیست، اما آنچه که ما تا به حال قبل از سادگی دم بازگشتی. آره.

311
00:23:22,190 --> 00:23:27,000
[دانشجو] باید مورد پایه دوم در ابتدا چک می شود

312
00:23:27,000 --> 00:23:30,640
زیرا می تواند وضعیت وجود دارد که در آن وقتی که از تو بگذرد این بحث

313
00:23:30,640 --> 00:23:35,770
شما شروع پایان، اما آنها ارزش سوزن.

314
00:23:35,770 --> 00:23:47,310
سوال را می توان به این مورد ما اجرا نمی که پایان ارزش سوزن

315
00:23:47,310 --> 00:23:52,000
یا شروع به پایان =، مناسب، شروع پایان =

316
00:23:52,000 --> 00:23:59,480
و شما در واقع بررسی نشده که ارزش خاصی ندارد،

317
00:23:59,480 --> 00:24:03,910
سپس شروع به + پایان / 2 رفتن به همان مقدار است.

318
00:24:03,910 --> 00:24:07,890
اما ما قبلا هم بازگشته نادرست و ما در واقع هرگز بررسی ارزش است.

319
00:24:07,890 --> 00:24:14,240
بنابراین حداقل، در تماس اول، اگر اندازه 0 است، پس از آن ما می خواهیم به بازگشت غلط است.

320
00:24:14,240 --> 00:24:17,710
اما اگر اندازه 1، پس از آن شروع شده است برای پایان دادن برابر نیست،

321
00:24:17,710 --> 00:24:19,820
و ما حداقل به بررسی یک عنصر است.

322
00:24:19,820 --> 00:24:26,750
اما من فکر می کنم شما درست می گویید که ما می توانیم تا پایان در یک مورد که در آن شروع به + پایان / 2،

323
00:24:26,750 --> 00:24:31,190
آغاز به پایان می رسد تا اینکه همان راه + پایان / 2،

324
00:24:31,190 --> 00:24:35,350
اما ما در واقع هرگز به بررسی آن عنصر است.

325
00:24:35,350 --> 00:24:44,740
>> بنابراین اگر ما ابتدا عنصر وسط ارزش است که ما به دنبال آن هستید،

326
00:24:44,740 --> 00:24:47,110
پس از آن ما می تواند بلافاصله به راست.

327
00:24:47,110 --> 00:24:50,740
دیگری اگر آنها برابر است، پس از آن هیچ نقطه ای در ادامه وجود دارد

328
00:24:50,740 --> 00:24:58,440
از آنجایی که ما فقط می خواهم برای به روز رسانی به صورت که در آن ما را در یک آرایه تک عنصری است.

329
00:24:58,440 --> 00:25:01,110
در صورتی که عنصر تنها یکی از ما به دنبال نمی باشد،

330
00:25:01,110 --> 00:25:03,530
پس از آن همه چیز اشتباه است. آره.

331
00:25:03,530 --> 00:25:08,900
[دانشجو] چیزی است که از آنجا که اندازه است که در واقع بزرگتر از تعداد عناصر موجود در آرایه،

332
00:25:08,900 --> 00:25:13,070
در حال حاضر وجود دارد افست - >> اندازه -

333
00:25:13,070 --> 00:25:19,380
[دانشجو] بگو: اگر آرایه به اندازه 0 بود، پس از آن SearchHelp واقع خواهد شد کومه علف خشک از 0 بررسی

334
00:25:19,380 --> 00:25:21,490
در اولین تماس است.

335
00:25:21,490 --> 00:25:25,300
آرایه اندازه 0 تا 0 است - >> آره.

336
00:25:25,300 --> 00:25:30,750
چیز دیگری که وجود دارد - ممکن است خوب باشد. بیایید فکر می کنم.

337
00:25:30,750 --> 00:25:40,120
بنابراین اگر آرایه به حال 10 عناصر و یکی از میانه ما قصد داریم برای بررسی شاخص 5،

338
00:25:40,120 --> 00:25:45,700
بنابراین ما در حال بررسی 5، و اجازه دهید بگویم که این مقدار کمتر است.

339
00:25:45,700 --> 00:25:50,720
بنابراین ما در حال پرتاب همه چیز را از 5 به بعد.

340
00:25:50,720 --> 00:25:54,030
بنابراین شروع به + پایان / 2 به پایان جدید ما،

341
00:25:54,030 --> 00:25:57,450
بنابراین آره، آن را همیشه به فراتر از انتهای آرایه باقی بماند.

342
00:25:57,450 --> 00:26:03,570
اگر این مورد است، اگر آن را و یا حتی عجیب و غریب بود، و سپس ما را چک کنید، می گویند، 4،

343
00:26:03,570 --> 00:26:05,770
اما ما هنوز دور انداختن -

344
00:26:05,770 --> 00:26:13,500
پس بله، پایان است که همیشه رفتن به فراتر از پایان واقعی از آرایه باشد.

345
00:26:13,500 --> 00:26:18,350
پس ما تمرکز بر روی پایان است که همواره برای رفتن به یکی از پس از آن است.

346
00:26:18,350 --> 00:26:24,270
و بنابراین، اگر آغاز تا کنون پایان برابر، ما را در آرایه ای از اندازه 0.

347
00:26:24,270 --> 00:26:35,600
>> چیز دیگری که من فکر کردم این است که ما در حال به روز رسانی شروع به شروع به + پایان / 2،

348
00:26:35,600 --> 00:26:44,020
بنابراین این مورد است که من با مشکل روبرو شد، که در آن شروع به + پایان / 2

349
00:26:44,020 --> 00:26:46,820
عنصر ما در حال بررسی است.

350
00:26:46,820 --> 00:26:58,150
بیایید می گویند که ما تا به حال 10 عنصر این آرایه است. هر چیز دیگری.

351
00:26:58,150 --> 00:27:03,250
بنابراین شروع به + پایان / 2 است به چیزی مثل این یکی،

352
00:27:03,250 --> 00:27:07,060
و در صورتی که ارزش نیست، می گویند ما می خواهیم برای به روز رسانی.

353
00:27:07,060 --> 00:27:10,060
مقدار بزرگتر است، به طوری که ما می خواهیم در این نیمه از آرایه.

354
00:27:10,060 --> 00:27:15,910
پس چگونه ما در حال به روز رسانی شروع، ما در حال به روز رسانی شروع به در حال حاضر این عنصر است.

355
00:27:15,910 --> 00:27:23,790
اما این هنوز هم ممکن است، کار و یا حداقل، شما می توانید شروع به + پایان / 2 + 1.

356
00:27:23,790 --> 00:27:27,850
[دانشجو] شما لازم نیست که برای پایان دادن به + شروع [نامفهوم] >> آره.

357
00:27:27,850 --> 00:27:33,240
ما در حال حاضر بررسی این عنصر و می دانم که این یکی از ما به دنبال.

358
00:27:33,240 --> 00:27:36,800
بنابراین ما نیاز به به روز رسانی شروع می شود این عنصر است.

359
00:27:36,800 --> 00:27:39,560
ما فقط می تواند آن را و بروید به روز رسانی شروع می شود این عنصر است.

360
00:27:39,560 --> 00:27:46,060
وجود داشته است که تا کنون یک مورد، اجازه دهید بگویم که این پایان بود،

361
00:27:46,060 --> 00:27:53,140
بنابراین پس از شروع خواهد بود + پایان، شروع / 2 خواهد بود.

362
00:27:53,140 --> 00:28:00,580
شروع پایان + - بله، من فکر می کنم می توان آن را در نهایت در بازگشت نامحدود.

363
00:28:00,580 --> 00:28:12,690
بیایید می گویند این فقط یک آرایه با اندازه 2 یا آرایه ای از اندازه 1. من فکر می کنم این کار خواهد کرد.

364
00:28:12,690 --> 00:28:19,490
بنابراین در حال حاضر، راه این است که عنصر و پایان 1 فراتر از آن است.

365
00:28:19,490 --> 00:28:24,110
بنابراین این عنصر است که ما قصد داریم برای بررسی این یکی،

366
00:28:24,110 --> 00:28:29,400
و پس از آن زمانی که شروع ما به روز رسانی ما در حال به روز رسانی شروع می شود 0 + 1/2،

367
00:28:29,400 --> 00:28:33,160
است که به ما در نهایت با شروع این عنصر است.

368
00:28:33,160 --> 00:28:36,210
>> بنابراین ما در حال بررسی عنصر مشابه بارها و بارها.

369
00:28:36,210 --> 00:28:43,310
پس این مورد که در آن هر تماس بازگشتی در واقع چیزی است که باید به روز رسانی است.

370
00:28:43,310 --> 00:28:48,370
بنابراین ما نیاز به شروع + پایان / 2 + 1، و یا دیگری یک مورد وجود دارد

371
00:28:48,370 --> 00:28:50,710
جایی که ما در واقع نه به روز رسانی شروع می شود.

372
00:28:50,710 --> 00:28:53,820
هر کس می بینیم که؟

373
00:28:53,820 --> 00:28:56,310
باشه.

374
00:28:56,310 --> 00:29:03,860
آیا کسی سوال در مورد این راه حل و یا بیشتر نظرات؟

375
00:29:05,220 --> 00:29:10,280
باشه. آیا کسی راه حل تکرار شونده است که همه ما می توانید در نگاه است؟

376
00:29:17,400 --> 00:29:20,940
آیا همه ما آن را به صورت بازگشتی انجام دهید؟

377
00:29:20,940 --> 00:29:25,950
و همچنین من حدس می زنم اگر شما ... او را باز کرد، و سپس شما ممکن است مجبور بازنویسی قبلی خود را.

378
00:29:25,950 --> 00:29:28,810
آیا آن را به طور خودکار ذخیره کنید؟ من مثبت نیست.

379
00:29:35,090 --> 00:29:39,130
آیا کسی تکراری؟

380
00:29:39,130 --> 00:29:42,430
ما می توانیم از طریق آن راه رفتن با هم اگر نه.

381
00:29:46,080 --> 00:29:48,100
ایده این است که رفتن به همان.

382
00:30:00,260 --> 00:30:02,830
تکراری راه حل.

383
00:30:02,830 --> 00:30:07,140
ما قصد داریم تا به همان ایده اساسا

384
00:30:07,140 --> 00:30:16,530
که در آن ما می خواهیم به نگه داشتن مسیر از انتهای آرایه و آغاز جدیدی از آرایه

385
00:30:16,530 --> 00:30:18,510
و انجام این کار بارها و بارها.

386
00:30:18,510 --> 00:30:22,430
و اگر آنچه که ما در حال پیگیری به عنوان شروع و پایان هر چه از وسط قطع کردن،

387
00:30:22,430 --> 00:30:29,020
سپس ما آن را پیدا نمی کند و ما می توانیم بازگشت غلط.

388
00:30:29,020 --> 00:30:37,540
پس چگونه است که من کاری انجام دهید؟ کسی پیشنهاد و یا کد برای من به جلو؟

389
00:30:42,190 --> 00:30:47,450
[دانشجو] آیا در حالی که حلقه. >> آره.

390
00:30:47,450 --> 00:30:49,450
شما در حال رفتن می خواهم به انجام یک حلقه است.

391
00:30:49,450 --> 00:30:51,830
>> آیا کدی که من می تواند بالا بکشد، و یا آنچه که شما قرار شد به پیشنهاد؟

392
00:30:51,830 --> 00:30:56,340
[دانشجو] من فکر می کنم تا. >> همه حق است. این باعث می شود همه چیز آسان تر است. نام و نام خانوادگی شما چه بوده است؟

393
00:30:56,340 --> 00:30:57,890
[دانشجوی] لوکاس.

394
00:31:00,140 --> 00:31:04,190
ویرایشهای 1. باشه.

395
00:31:04,190 --> 00:31:13,200
پایین همان چیزی است که ما به نام شروع قبل از.

396
00:31:13,200 --> 00:31:17,080
تا کاملا آنچه که ما به نام آنکه پایان کار را پیش از.

397
00:31:17,080 --> 00:31:22,750
در واقع، در حال حاضر در داخل آرایه. این یک عنصر ما باید در نظر است.

398
00:31:22,750 --> 00:31:26,890
بسیار پایین 0 است، تا اندازه آرایه - 1،

399
00:31:26,890 --> 00:31:34,780
و در حال حاضر ما در حال حلقه، و ما در حال بررسی -

400
00:31:34,780 --> 00:31:37,340
من حدس می زنم شما می توانید از طریق آن راه رفتن است.

401
00:31:37,340 --> 00:31:41,420
چه تفکر خود را از طریق این؟ پیاده روی ما را از طریق کد شما.

402
00:31:41,420 --> 00:31:49,940
[دانشجو] مطمئنا. نگاهی به ارزش کومه علف خشک در وسط و مقایسه آن را به سوزن.

403
00:31:49,940 --> 00:31:58,520
پس اگر آن را بیش از سوزن خود را، پس از آن شما می خواهید به - آه، در واقع، که به عقب باید.

404
00:31:58,520 --> 00:32:05,180
شما می خواهم به دور انداختن نیمه سمت راست، و آره، که باید راه است.

405
00:32:05,180 --> 00:32:08,830
[Bowden] بنابراین این باید کمتر؟ این است که آنچه به شما گفت؟ >> [دانشجو] آره.

406
00:32:08,830 --> 00:32:10,390
[Bowden] باشه. کمتر.

407
00:32:10,390 --> 00:32:15,700
بنابراین اگر آنچه که ما در حال نگاه کردن به کوچکتر از آنچه ما می خواهیم،

408
00:32:15,700 --> 00:32:19,410
سپس آره، ما می خواهیم به دور انداختن نیمه سمت چپ،

409
00:32:19,410 --> 00:32:22,210
که بدان معنی است که ما در حال به روز رسانی ما با توجه به همه چیز

410
00:32:22,210 --> 00:32:26,610
با حرکت کم به سمت راست از آرایه.

411
00:32:26,610 --> 00:32:30,130
این به نظر می رسد خوب است.

412
00:32:30,130 --> 00:32:34,550
من فکر می کنم آن است که مسئله همان است که ما در یکی از قبلی گفت،

413
00:32:34,550 --> 00:32:49,760
جایی که اگر پایین است 0 و تا 1، و سپس پایین + بالا / 2 رفتن به راه اندازی همان چیزی که به دوباره است.

414
00:32:49,760 --> 00:32:53,860
>> و حتی در صورتی که این مورد نیست، آن است که هنوز هم کارآمد تر است و حداقل

415
00:32:53,860 --> 00:32:57,630
فقط به دور انداختن این عنصر ما فقط نگاه کرد که در آن ما می دانیم اشتباه است.

416
00:32:57,630 --> 00:33:03,240
بسیار پایین + بالا / 2 + 1 - >> [دانشجو] است که باید راه دیگری است.

417
00:33:03,240 --> 00:33:05,900
[Bowden] یا این باید باشد - 1 و یکی دیگر باید باشد + 1.

418
00:33:05,900 --> 00:33:09,580
[دانشجو] و باید وجود داشته باشد دو برابر ورود به سیستم. >> [Bowden] آره.

419
00:33:09,580 --> 00:33:11,340
[دانشجوی] آره.

420
00:33:14,540 --> 00:33:15,910
باشه.

421
00:33:15,910 --> 00:33:21,280
و در نهایت، در حال حاضر که ما این 1 + 1 - چیزی،

422
00:33:21,280 --> 00:33:31,520
- آن را نمی ممکن است - آن است که همیشه ممکن است برای کم تا پایان با یک مقدار بزرگتر از تا؟

423
00:33:35,710 --> 00:33:40,320
من فکر می کنم تنها راهی است که می تواند رخ دهد - آیا ممکن است؟ >> [دانشجو] من نمی دانم.

424
00:33:40,320 --> 00:33:45,220
اما اگر آن را کوتاه می شود و پس از آن می شود منهای 1 و پس از آن - >> آره.

425
00:33:45,220 --> 00:33:47,480
[دانشجو] آن را احتمالا می خراب گرفتن.

426
00:33:49,700 --> 00:33:53,940
من فکر می کنم آن را باید فقط به این دلیل خوب است

427
00:33:53,940 --> 00:33:58,800
برای آن برای پایان دادن به پایین آنها می باید برابر، من فکر می کنم.

428
00:33:58,800 --> 00:34:03,070
اما اگر آنها با هم برابر هستند، پس از آن ما می توانست انجام نمی شود در حالی که حلقه برای شروع

429
00:34:03,070 --> 00:34:06,670
و ما فقط می بازگشته اند ارزش است. بنابراین من فکر می کنم ما در حال حاضر.

430
00:34:06,670 --> 00:34:11,530
توجه کنید که حتی اگر این مشکل این است که دیگر بازگشتی،

431
00:34:11,530 --> 00:34:17,400
همان نوع از ایده ها اعمال می شود که در آن ما می توانید ببینید که چگونه به راحتی خود را lends

432
00:34:17,400 --> 00:34:23,659
برای راه حل بازگشتی توسط این واقعیت است که ما فقط به روز رسانی شاخص ها بارها و بارها،

433
00:34:23,659 --> 00:34:29,960
ما در حال ساخت مشکل کوچکتر و کوچکتر، ما در حال تمرکز بر روی یک زیر مجموعه از آرایه.

434
00:34:29,960 --> 00:34:40,860
[دانشجو] اگر کم است 0 و 1 است، آنها هر دو در 0 + 1/2، که می تواند تا 0،

435
00:34:40,860 --> 00:34:44,429
و پس از آن خواهد بود + 1 خواهد بود - 1.

436
00:34:47,000 --> 00:34:50,870
[دانشجو] ما داریم به کجا چک کردن برابری؟

437
00:34:50,870 --> 00:34:55,100
مثل اگر یکی از متوسط ​​است که در واقع سوزن؟

438
00:34:55,100 --> 00:34:58,590
ما در حال انجام این کار؟ آه!

439
00:35:00,610 --> 00:35:02,460
اگر it's -

440
00:35:05,340 --> 00:35:13,740
بله. ما می توانیم نه فقط انجام آزمون را در اینجا به دلیل اجازه دهید می گویند وسط اول -

441
00:35:13,740 --> 00:35:16,430
[دانشجو] این در واقع مثل پرتاب نمی کند و دور متصل.

442
00:35:16,430 --> 00:35:20,220
بنابراین اگر شما دور انداختن محدود، شما باید آن را چک کنید یا هر چیز دیگری.

443
00:35:20,220 --> 00:35:23,350
ق. آره. >> [دانشجو] آره.

444
00:35:23,350 --> 00:35:29,650
بنابراین در حال حاضر ما یکی از ما در حال حاضر در نگاه دور انداخته،

445
00:35:29,650 --> 00:35:33,260
به این معنی است که ما در حال حاضر نیاز به همچنین دارای

446
00:35:33,260 --> 00:35:44,810
اگر (کومه علف خشک (کم + تا) / 2] == سوزن)، و سپس ما می توانیم بازگشت درست است.

447
00:35:44,810 --> 00:35:52,070
و آیا من را دیگری و یا فقط در صورتی که، به معنای همان چیزی که

448
00:35:52,070 --> 00:35:57,110
زیرا این درست بازگشته اند.

449
00:35:57,110 --> 00:36:01,450
بنابراین من دیگری خواهید قرار دهید اگر، اما مهم نیست.

450
00:36:01,450 --> 00:36:10,440
>> بنابراین اگر دیگری، دیگری این است، و این یک چیز مشترک من انجام می دهم

451
00:36:10,440 --> 00:36:14,340
جایی که حتی اگر این مورد است که در آن همه چیز اینجا خوب است،

452
00:36:14,340 --> 00:36:22,780
مانند کم هرگز نمی تواند بیشتر از بالا، آن را استدلال ارزش در مورد اینکه آیا این درست نیست.

453
00:36:22,780 --> 00:36:28,010
بنابراین شما را به عنوان ممکن است به خوبی می گویند در حالی که کم است کمتر از یا مساوی با

454
00:36:28,010 --> 00:36:30,720
یا در حالی که کم است کمتر از

455
00:36:30,720 --> 00:36:35,300
بنابراین اگر آنها همیشه برابر یا پایین اتفاق می افتد به تصویب،

456
00:36:35,300 --> 00:36:40,130
پس از آن ما می توانیم از این حلقه است.

457
00:36:41,410 --> 00:36:44,630
پرسش ها، نگرانی ها، نظرات؟

458
00:36:47,080 --> 00:36:49,270
باشه. این به نظر می رسد خوب است.

459
00:36:49,270 --> 00:36:52,230
حالا ما می خواهیم به انجام مرتب سازی بر اساس.

460
00:36:52,230 --> 00:37:04,030
اگر ما را به تجدید نظر دوم من، ما می بینیم این همان تعداد،

461
00:37:04,030 --> 00:37:07,550
اما در حال حاضر آنها دیگر به منظور طبقه بندی شده اند.

462
00:37:07,550 --> 00:37:12,840
و ما می خواهیم برای پیاده سازی مرتب سازی بر اساس استفاده از هر الگوریتم O n log n استفاده است.

463
00:37:12,840 --> 00:37:17,240
بنابراین الگوریتم آیا شما فکر می کنید ما در اینجا باید پیاده سازی؟ >> [دانشجو] مرتب سازی بر اساس ادغام خواهند شد.

464
00:37:17,240 --> 00:37:23,810
[Bowden] آره. ادغام مرتب کردن بر اساس O (n log n است) است، به طوری که این چیزی است که ما قصد داریم برای انجام این کار است.

465
00:37:23,810 --> 00:37:26,680
و مشکل این است که به صورت کاملا مشابه،

466
00:37:26,680 --> 00:37:31,920
جایی که آن را به آسانی خود را به یک راه حل بازگشتی آشنایی.

467
00:37:31,920 --> 00:37:35,580
ما همچنین می توانیم با یک راه حل تکرار شونده صورت می گیرد که ما می خواهیم،

468
00:37:35,580 --> 00:37:42,540
اما بازگشتی ساده تر خواهد شد و ما باید بازگشت.

469
00:37:45,120 --> 00:37:49,530
من حدس می زنم ما را از طریق مرتب کردن بر اساس ادغام راه رفتن اول،

470
00:37:49,530 --> 00:37:54,280
اگر چه یک فیلم دوست داشتنی در مرتب کردن بر اساس ادغام حال حاضر وجود دارد. [خنده]

471
00:37:54,280 --> 00:37:59,780
بنابراین مرتب کردن بر اساس ادغام وجود دارد - من به هدر رفتن خیلی از این مقاله است.

472
00:37:59,780 --> 00:38:02,080
آه، فقط یک سمت چپ وجود دارد.

473
00:38:02,080 --> 00:38:03,630
بنابراین ادغام خواهند شد.

474
00:38:08,190 --> 00:38:12,470
اوه، 1، 3، 5.

475
00:38:26,090 --> 00:38:27,440
باشه.

476
00:38:29,910 --> 00:38:33,460
ادغام دو آرایه جداگانه به طول می انجامد.

477
00:38:33,460 --> 00:38:36,780
فردی این دو آرایه ها هم طبقه بندی شده اند.

478
00:38:36,780 --> 00:38:40,970
بنابراین این آرایه، 1، 3، 5، طبقه بندی شده اند. این آرایه، 0، 2، 4، طبقه بندی شده اند.

479
00:38:40,970 --> 00:38:46,710
در حال حاضر آنچه ادغام باید انجام دهید این است که ترکیب آنها را در یک آرایه است که خود طبقه بندی شده اند.

480
00:38:46,710 --> 00:38:57,130
بنابراین ما می خواهیم مجموعه ای از اندازه 6 است که رفتن به این عناصر در داخل از آن

481
00:38:57,130 --> 00:38:59,390
به منظور طبقه بندی شده اند.

482
00:38:59,390 --> 00:39:03,390
>> و بنابراین ما می توانیم با استفاده از این واقعیت است که این دو آرایه مرتب را

483
00:39:03,390 --> 00:39:06,800
برای انجام این کار را در زمان خطی،

484
00:39:06,800 --> 00:39:13,510
معنای زمان خطی اگر این آرایه X اندازه و Y اندازه،

485
00:39:13,510 --> 00:39:20,970
سپس الگوریتم در کل باید O (x + y). باشه.

486
00:39:20,970 --> 00:39:23,150
بنابراین پیشنهادات.

487
00:39:23,150 --> 00:39:26,030
[دانشجو] می تواند ما را از سمت چپ شروع می شود؟

488
00:39:26,030 --> 00:39:30,150
بنابراین شما 0 پایین اول و سپس از شماره 1 قرار داده و پس از آن در اینجا شما در 2 هستید.

489
00:39:30,150 --> 00:39:33,320
پس از آن نوع از مثل شما یک تب است که در حال حرکت به سمت راست است. >> [Bowden] آره.

490
00:39:33,320 --> 00:39:41,070
هر دو از این آرایه اگر ما فقط تمرکز بر روی عنصر سمت چپ.

491
00:39:41,070 --> 00:39:43,530
از آنجا که هر دو آرایه مرتب شده باشد، ما می دانیم که این 2 عنصر

492
00:39:43,530 --> 00:39:46,920
کوچکترین عناصر در هر دو آرایه.

493
00:39:46,920 --> 00:39:53,500
به طوری که بدان معنی است که 1 از 2 عنصر باید کوچکترین عنصر در آرایه ادغام شده ما است.

494
00:39:53,500 --> 00:39:58,190
این فقط اتفاق می افتد که کوچکترین است که در سمت راست این زمان است.

495
00:39:58,190 --> 00:40:02,580
بنابراین 0 ما را، قرار دادن آن در سمت چپ به دلیل 0 این است که کمتر از 1

496
00:40:02,580 --> 00:40:08,210
بنابراین، 0، آن را به موقعیت اول ما را وارد، و پس از آن ما به روز رسانی

497
00:40:08,210 --> 00:40:12,070
در حال حاضر تمرکز بر روی عنصر اول.

498
00:40:12,070 --> 00:40:14,570
و در حال حاضر ما تکرار کنید.

499
00:40:14,570 --> 00:40:20,670
بنابراین در حال حاضر 2 مقایسه کنیم و 1. 1 است کوچکتر، بنابراین خواهیم 1 وارد است.

500
00:40:20,670 --> 00:40:25,300
این اشاره گر به روز رسانی ما برای اشاره به این پسر.

501
00:40:25,300 --> 00:40:33,160
در حال حاضر ما دوباره آن را انجام دهد، بنابراین 2. این به روز رسانی خواهد شد، مقایسه این 2، 3.

502
00:40:33,160 --> 00:40:37,770
این به روز رسانی، و سپس 4 و 5.

503
00:40:37,770 --> 00:40:42,110
به طوری که ادغام خواهند شد.

504
00:40:42,110 --> 00:40:49,010
>> این باید بسیار واضح است که وقت آن است که خطی از آنجایی که ما فقط در سراسر هر یک از عناصر یک بار.

505
00:40:49,010 --> 00:40:55,980
و این بزرگترین گام برای پیاده سازی مرتب سازی بر اساس ادغام در حال انجام این کار است.

506
00:40:55,980 --> 00:40:59,330
و از آن است که سخت نیست.

507
00:40:59,330 --> 00:41:15,020
دو چیز نگران است بیایید می گویند که ما ادغام 1، 2، 3، 4، 5، 6.

508
00:41:15,020 --> 00:41:30,930
در این حالت ما تا پایان در سناریویی که در آن این یکی برای رفتن به کوچکتر،

509
00:41:30,930 --> 00:41:36,160
پس از این اشاره گر ما به روز رسانی، این یکی برای رفتن به کوچکتر، به روز رسانی،

510
00:41:36,160 --> 00:41:41,280
این یکی کوچکتر، و در حال حاضر شما به رسمیت شناختن

511
00:41:41,280 --> 00:41:44,220
هنگامی که شما در واقع اجرا کردن عناصر در مقایسه با.

512
00:41:44,220 --> 00:41:49,400
از آنجا که ما در حال حاضر استفاده می شود کل این آرایه،

513
00:41:49,400 --> 00:41:55,190
همه چیز در این آرایه در حال حاضر فقط به اینجا وارد می شود.

514
00:41:55,190 --> 00:42:02,040
بنابراین اگر ما تا به حال به نقطه ای که یکی از آرایه های ما به طور کامل با هم ادغام شدند در حال حاضر اجرا می شود،

515
00:42:02,040 --> 00:42:06,510
پس ما فقط تمام عناصر آرایه دیگر و قرار دادن آنها را در پایان از آرایه.

516
00:42:06,510 --> 00:42:13,630
بنابراین ما فقط می تواند 4، قرار دادن 5، 6. باشه.

517
00:42:13,630 --> 00:42:18,070
این یک چیز را به مراقب است.

518
00:42:22,080 --> 00:42:26,120
پیاده سازی است که باید مرحله 1.

519
00:42:26,120 --> 00:42:32,600
ادغام مرتب سازی و سپس بر اساس آن، این 2 گام، 2 مرحله احمقانه است.

520
00:42:38,800 --> 00:42:42,090
بیایید فقط این آرایه را به من بدهید.

521
00:42:57,920 --> 00:43:05,680
بنابراین ادغام مرتب کردن بر اساس، مرحله 1 را به صورت بازگشتی آرایه به نیمه شکستن.

522
00:43:05,680 --> 00:43:09,350
بنابراین این آرایه را به دو نیمه تقسیم می شود.

523
00:43:09,350 --> 00:43:22,920
ما در حال حاضر 4، 15، 16، 50 و 8، 23، 42، 108.

524
00:43:22,920 --> 00:43:25,800
و در حال حاضر ما این کار را انجام دوباره و ما این کار را به دو نیمه تقسیم شده است.

525
00:43:25,800 --> 00:43:27,530
من آن را در این سمت انجام درست.

526
00:43:27,530 --> 00:43:34,790
SO 4، 15 و 16، 50.

527
00:43:34,790 --> 00:43:37,440
ما می خواهیم به همان چیزی که در اینجا انجام دهید.

528
00:43:37,440 --> 00:43:40,340
و در حال حاضر ما آن را به دو نیمه تقسیم شده دوباره.

529
00:43:40,340 --> 00:43:51,080
و در حال حاضر 4، 15، 16، 50.

530
00:43:51,080 --> 00:43:53,170
به طوری که مورد پایگاه ما.

531
00:43:53,170 --> 00:44:00,540
هنگامی که آرایه از اندازه 1 هستند، پس ما را با تقسیم به دو نیمه متوقف شود.

532
00:44:00,540 --> 00:44:03,190
>> حالا چه ما این کار را انجام دهند؟

533
00:44:03,190 --> 00:44:15,730
ما تا پایان این نیز خواهد شد شکستن به 8، 23، 42، و 108.

534
00:44:15,730 --> 00:44:24,000
بنابراین در حال حاضر که ما در این نقطه هستیم، در حال حاضر دو تا از مرتب کردن بر اساس ادغام ادغام جفت به لیست گام.

535
00:44:24,000 --> 00:44:27,610
بنابراین ما می خواهیم به ادغام این. ما فقط ادغام تماس بگیرید.

536
00:44:27,610 --> 00:44:31,410
ما می دانیم که ادغام خواهد شد این کار را به منظور طبقه بندی شده اند بازگشت.

537
00:44:31,410 --> 00:44:33,920
4، 15.

538
00:44:33,920 --> 00:44:41,440
حالا ما می خواهیم به این ادغام، و این فهرست را با کسانی که به منظور طبقه بندی شده اند بازگشت،

539
00:44:41,440 --> 00:44:44,160
16، 50.

540
00:44:44,160 --> 00:44:57,380
ما ادغام آن - من نمی توانم نوشتن - 8، 23 و 42، 108.

541
00:44:57,380 --> 00:45:02,890
بنابراین ما باید جفت ادغام یک بار.

542
00:45:02,890 --> 00:45:05,140
در حال حاضر ما فقط دوباره ادغام خواهند شد.

543
00:45:05,140 --> 00:45:10,130
توجه داشته باشید که هر یک از این لیست طبقه بندی شده اند را در خود دارد،

544
00:45:10,130 --> 00:45:15,220
و پس از آن ما فقط می تواند این لیست یک لیست از اندازه 4 است که طبقه بندی شده اند را به ادغام

545
00:45:15,220 --> 00:45:19,990
و ادغام این دو لیست برای به دست آوردن یک لیست از اندازه 4 است که طبقه بندی شده اند.

546
00:45:19,990 --> 00:45:25,710
و در نهایت، ما می توانیم یک لیست از اندازه 8 است که طبقه بندی شده اند به این دو لیست از اندازه 4 ادغام خواهند شد.

547
00:45:25,710 --> 00:45:34,030
بنابراین برای دیدن این است که به طور کلی n log n استفاده، ما در حال حاضر را دیدم که ادغام خطی است،

548
00:45:34,030 --> 00:45:40,390
بنابراین، هنگامی که ما در حال خرید و فروش با ادغام این پس مانند هزینه های کلی از ادغام

549
00:45:40,390 --> 00:45:43,410
برای این دو لیست فقط 2 - به دلیل

550
00:45:43,410 --> 00:45:49,610
یا خوب، آن O از N، N در اینجا این است که فقط این 2 عنصر، پس از آن، 2.

551
00:45:49,610 --> 00:45:52,850
و این 2 خواهد بود (2) و این 2 خواهد بود 2 و این 2 خواهد بود 2.

552
00:45:52,850 --> 00:45:58,820
تا سراسر همه از ادغام است که ما باید انجام دهیم، ما تا پایان انجام N.

553
00:45:58,820 --> 00:46:03,210
مانند 2 + 2 + 2 + 2 8 است، که N،

554
00:46:03,210 --> 00:46:08,060
بنابراین هزینه ادغام در این مجموعه N.

555
00:46:08,060 --> 00:46:10,810
و سپس همان چیز در اینجا.

556
00:46:10,810 --> 00:46:16,980
خواهیم این 2، ادغام، سپس این 2 و به صورت جداگانه این ادغام چهار عملیات را انجام دهید،

557
00:46:16,980 --> 00:46:23,610
این ادغام چهار عملیات را، اما بار دیگر، در بین تمام این،

558
00:46:23,610 --> 00:46:29,030
ما تا پایان ادغام N چیزهای کل، و در این مرحله طول می کشد N.

559
00:46:29,030 --> 00:46:33,670
و به این ترتیب هر سطح، طول می کشد n عنصر با هم ادغام شدند.

560
00:46:33,670 --> 00:46:36,110
>> و چگونه بسیاری از سطوح وجود دارد؟

561
00:46:36,110 --> 00:46:40,160
در هر سطح، آرایه ما رشد می کند به اندازه 2.

562
00:46:40,160 --> 00:46:44,590
آرایه ما از اندازه 1 هستند، در اینجا آنها را با اندازه 2 هستید، در اینجا آنها از اندازه 4 هستید،

563
00:46:44,590 --> 00:46:46,470
و در نهایت، آنها از اندازه 8 هستید.

564
00:46:46,470 --> 00:46:56,450
پس از آن دو برابر شده است، قصد دارد به عنوان یک کل از ورود نفر از این سطوح است.

565
00:46:56,450 --> 00:47:02,090
بنابراین با ورود N سطح، هر سطح فردی در عملیات کل،

566
00:47:02,090 --> 00:47:05,720
ورود N N الگوریتم.

567
00:47:05,720 --> 00:47:07,790
پرسش و پاسخ؟

568
00:47:08,940 --> 00:47:13,320
مردم در حال حاضر در مورد چگونگی اجرای این پیشرفت؟

569
00:47:13,320 --> 00:47:18,260
هر کسی که در حال حاضر در دولت که در آن من فقط می توانید کدهای خود را بالا بکشد؟

570
00:47:20,320 --> 00:47:22,260
من می توانم یک دقیقه به من بدهید.

571
00:47:24,770 --> 00:47:27,470
این یکی برای رفتن به دیگر.

572
00:47:27,470 --> 00:47:28,730
من به شدت توصیه عود -

573
00:47:28,730 --> 00:47:30,510
شما لازم نیست که برای انجام این کار بازگشت برای ادغام

574
00:47:30,510 --> 00:47:33,750
به خاطر بازگشت برای ادغام، شما در حال رفتن به یک دسته از اندازه های مختلف به تصویب.

575
00:47:33,750 --> 00:47:37,150
شما می توانید، اما آن را آزار دهنده است.

576
00:47:37,150 --> 00:47:43,720
اما بازگشت برای مرتب کردن بر اساس خود بسیار آسان است.

577
00:47:43,720 --> 00:47:49,190
شما فقط به معنای واقعی کلمه در نیمه سمت چپ تماس، مرتب کردن بر روی نیمه راست. باشه.

578
00:47:51,770 --> 00:47:54,860
هر کس هر چیزی می توانید بکشید تا هنوز؟

579
00:47:54,860 --> 00:47:57,540
وگرنه من یک دقیقه به من بدهید.

580
00:47:58,210 --> 00:47:59,900
باشه.

581
00:47:59,900 --> 00:48:02,970
هر کس چیزی است که ما می توانیم با آن کار کنند؟

582
00:48:05,450 --> 00:48:09,680
وگرنه ما فقط با این کار و پس از آن از آنجا گسترش.

583
00:48:09,680 --> 00:48:14,050
>> هر کس بیش از این که من می تواند بالا بکشد؟

584
00:48:14,050 --> 00:48:17,770
[دانشجوی] آره. شما می توانید بکشید تا مال من است. >> همه حق است.

585
00:48:17,770 --> 00:48:19,730
بله!

586
00:48:22,170 --> 00:48:25,280
[دانشجو] بسیاری از شرایط وجود دارد. >> آه، ساقه. آیا می توانم به شما -

587
00:48:25,280 --> 00:48:28,110
[دانشجو] من باید آن را ذخیره کنید. >> آره.

588
00:48:32,420 --> 00:48:35,730
بنابراین ما انجام ادغام به طور جداگانه.

589
00:48:35,730 --> 00:48:38,570
آه، اما از آن است که بد نیست.

590
00:48:39,790 --> 00:48:41,650
باشه.

591
00:48:41,650 --> 00:48:47,080
بنابراین مرتب کردن بر اساس خود فقط خواستار mergeSortHelp.

592
00:48:47,080 --> 00:48:49,530
به ما توضیح دهید چه mergeSortHelp می کند.

593
00:48:49,530 --> 00:48:55,700
[دانشجوی] MergeSortHelp تا حد زیادی می کند دو مرحله ی اصلی،

594
00:48:55,700 --> 00:49:01,270
است که به مرتب کردن بر اساس هر یک از نیمی از آرایه و سپس به ادغام هر دو آنها است.

595
00:49:04,960 --> 00:49:08,050
[Bowden] بسیار خوب، من یک لحظه هم به من بدهید.

596
00:49:10,850 --> 00:49:13,210
من فکر می کنم این - >> [دانشجو] من نیاز به -

597
00:49:17,100 --> 00:49:19,400
آره. من گم شده چیزی.

598
00:49:19,400 --> 00:49:23,100
در ادغام، من می دانم که من نیاز به ایجاد یک آرایه جدید

599
00:49:23,100 --> 00:49:26,530
زیرا من می توانم آن را در جای خود انجام نمی دهد. >> بله. شما می توانید نیست. درست است.

600
00:49:26,530 --> 00:49:28,170
[دانشجو] بنابراین یک آرایه جدید ایجاد کنم.

601
00:49:28,170 --> 00:49:31,510
من در پایان از ادغام دوباره تغییر را فراموش کرده است.

602
00:49:31,510 --> 00:49:34,490
باشه. ما نیاز به یک آرایه جدید.

603
00:49:34,490 --> 00:49:41,000
مرتب کردن بر اساس ادغام، این است که تقریبا همیشه درست است.

604
00:49:41,000 --> 00:49:44,340
بخشی از هزینه از یک الگوریتم بهتر و زرنگ

605
00:49:44,340 --> 00:49:47,310
تقریبا همیشه نیاز به استفاده از حافظه کمی بیشتر است.

606
00:49:47,310 --> 00:49:51,570
بنابراین در اینجا، مهم نیست که چگونه شما انجام دهد ادغام مرتب کردن بر اساس:

607
00:49:51,570 --> 00:49:54,780
شما ناگزیر به استفاده از برخی از حافظه اضافی نیاز دارند.

608
00:49:54,780 --> 00:49:58,240
او یک آرایه جدید است.

609
00:49:58,240 --> 00:50:03,400
و پس از آن به شما می گویند در پایان ما تنها نیاز داریم برای کپی کردن آرایه به آرایه اصلی.

610
00:50:03,400 --> 00:50:04,830
[دانشجو] من فکر می کنم، آره.

611
00:50:04,830 --> 00:50:08,210
من نمی دانم در صورتی که در شمارش توسط مرجع یا هر چیز دیگری کار می کند -

612
00:50:08,210 --> 00:50:11,650
آره، آن را به کار می کنند. >> [دانشجو] باشه.

613
00:50:20,620 --> 00:50:24,480
آیا شما سعی می کنید اجرای این؟ >> [دانشجو] نه، هنوز نه. >> درست است.

614
00:50:24,480 --> 00:50:28,880
سعی کنید با اجرای آن، و سپس من در مورد آن را برای یک ثانیه صحبت کنید.

615
00:50:28,880 --> 00:50:35,200
[دانشجو] من نیاز به داشتن تمام نمونه های عملکرد و همه چیز، هر چند، درست است؟

616
00:50:37,640 --> 00:50:40,840
نمونه های تابع. بله - آه، تو مثل بود.

617
00:50:40,840 --> 00:50:43,040
مرتب سازی بر اساس خواستار mergeSortHelp.

618
00:50:43,040 --> 00:50:47,390
>> بنابراین به منظور مرتب سازی بر به تماس mergeSortHelp، mergeSortHelp یا باید شده است را تعریف

619
00:50:47,390 --> 00:50:56,370
قبل از مرتب کردن بر اساس و یا ما فقط نیاز به نمونه است. فقط و کپی پیست کنید که.

620
00:50:56,370 --> 00:50:59,490
و به همین ترتیب، mergeSortHelp خواستار ادغام،

621
00:50:59,490 --> 00:51:03,830
اما ادغام هنوز تعریف نشده است، بنابراین ما فقط می تواند mergeSortHelp می دانیم

622
00:51:03,830 --> 00:51:08,700
که این چیزی است که ادغام شبیه، و این که.

623
00:51:09,950 --> 00:51:15,730
بنابراین mergeSortHelp.

624
00:51:22,770 --> 00:51:32,660
در حال حاضر موضوع در اینجا جایی که در حال حاضر هیچ مورد پایه.

625
00:51:32,660 --> 00:51:38,110
MergeSortHelp بازگشتی است، بنابراین هر تابع بازگشتی

626
00:51:38,110 --> 00:51:42,610
رفتن به نیاز برخی از مرتب کردن بر اساس مورد پایه می دانم که زمانی که برای متوقف کردن صورت بازگشتی خود خواستار است.

627
00:51:42,610 --> 00:51:45,590
آنچه که مورد پایگاه ما را از رفتن به اینجا؟ آره.

628
00:51:45,590 --> 00:51:49,110
[دانشجوی] اگر به اندازه 1؟ >> [Bowden] بله.

629
00:51:49,110 --> 00:51:56,220
پس چون ما را دیدم در سمت راست وجود دارد، ما را متوقف آرایه تقسیم

630
00:51:56,220 --> 00:52:01,850
زمانی که ما به آرایه از اندازه (1)، که به ناچار خود را طبقه بندی شده اند.

631
00:52:01,850 --> 00:52:09,530
بنابراین اگر اندازه برابر با 1، ما می دانیم که آرایه در حال حاضر طبقه بندی شده اند،

632
00:52:09,530 --> 00:52:12,970
بنابراین ما فقط می تواند بازگشت.

633
00:52:12,970 --> 00:52:16,880
>> توجه داشته باشید که از درجه اعتبار ساقط است، بنابراین ما هیچ چیز خاصی نمی گرداند، ما فقط بازگشت.

634
00:52:16,880 --> 00:52:19,580
باشه. به طوری که مورد پایگاه ما است.

635
00:52:19,580 --> 00:52:27,440
من حدس می زنم در مورد پایگاه ما همچنین می تواند اگر ما اتفاق می افتد به ادغام مجموعه ای از اندازه 0،

636
00:52:27,440 --> 00:52:30,030
ما احتمالا می خواهید به توقف در برخی از نقطه،

637
00:52:30,030 --> 00:52:33,610
بنابراین ما فقط می تواند به اندازه کمتر از 2 یا کمتر از یا برابر با 1 می گویند

638
00:52:33,610 --> 00:52:37,150
به طوری که این کار برای هر آرایه است.

639
00:52:37,150 --> 00:52:38,870
باشه.

640
00:52:38,870 --> 00:52:42,740
به طوری که مورد پایگاه ما است.

641
00:52:42,740 --> 00:52:45,950
حالا شما می خواهید به ما از طریق ادغام راه رفتن؟

642
00:52:45,950 --> 00:52:49,140
همه این موارد به چه معنی است؟

643
00:52:49,140 --> 00:52:54,480
به اینجا ما فقط به انجام همان ایده، -

644
00:52:56,970 --> 00:53:02,470
[دانشجو] من نیاز به عبور از اندازه با تمام تماس های mergeSortHelp.

645
00:53:02,470 --> 00:53:10,080
من به اندازه اولیه اضافی اضافه شده است و آن وجود ندارد، مانند اندازه 2 /.

646
00:53:10,080 --> 00:53:16,210
[Bowden: اوه، اندازه / 2، اندازه 2 /. >> [دانشجوی] آره، و همچنین در تابع فوق را به عنوان است.

647
00:53:16,210 --> 00:53:21,320
[Bowden] در اینجا؟ >> [دانش آموز فقط اندازه. >> [Bowden] آه. حجم، اندازه؟ >> [دانشجو] آره.

648
00:53:21,320 --> 00:53:23,010
[Bowden] باشه.

649
00:53:23,010 --> 00:53:26,580
اجازه دهید من فکر می کنم برای یک ثانیه.

650
00:53:26,580 --> 00:53:28,780
آیا ما به یک مسئله اجرا شود؟

651
00:53:28,780 --> 00:53:33,690
ما همیشه درمان سمت چپ را با 0. >> [دانشجوی] شماره

652
00:53:33,690 --> 00:53:36,340
که اشتباه است بیش از حد. متأسفم. باید شروع می شود. آره.

653
00:53:36,340 --> 00:53:39,230
[Bowden] باشه. من دوست دارم که بهتر است.

654
00:53:39,230 --> 00:53:43,880
و پایان. باشه.

655
00:53:43,880 --> 00:53:47,200
بنابراین در حال حاضر شما می خواهید به ما از طریق ادغام راه رفتن؟ >> [دانشجو] باشه.

656
00:53:47,200 --> 00:53:52,150
من فقط راه رفتن را از طریق این آرایه جدید است که من ایجاد کرده اید.

657
00:53:52,150 --> 00:53:57,420
اندازه آن به اندازه بخشی از آرایه است که ما می خواهیم طبقه بندی شده اند

658
00:53:57,420 --> 00:54:03,460
و در تلاش برای پیدا کردن این عنصر است که من باید در مرحله آرایه جدید قرار داده است.

659
00:54:03,460 --> 00:54:10,140
بنابراین برای انجام این کار، ابتدا من چک کردن اگر در نیمه سمت چپ آرایه ادامه می دهد، به عناصر هر

660
00:54:10,140 --> 00:54:14,260
و اگر آن را ندارد، پس از آن شما به پایین که به بیماری دیگری، که فقط می گوید:

661
00:54:14,260 --> 00:54:20,180
خوب، باید آن را در آرایه درست می شود، و ما که در شاخص فعلی newArray قرار داده است.

662
00:54:20,180 --> 00:54:27,620
>> و پس از آن در غیر این صورت، من چک کردن اگر در سمت راست از آرایه نیز به پایان رسید،

663
00:54:27,620 --> 00:54:30,630
که در این صورت من فقط در سمت چپ قرار داده است.

664
00:54:30,630 --> 00:54:34,180
است که در واقع ممکن است لازم باشد. مطمئن نیستم.

665
00:54:34,180 --> 00:54:40,970
اما به هر حال، دو نفر دیگر چک کدام یک از این دو کوچکتر در سمت چپ و یا سمت راست.

666
00:54:40,970 --> 00:54:49,770
و همچنین در هر مورد، من افزایش هر کدام از مکان نگه دار من افزایش است.

667
00:54:49,770 --> 00:54:52,040
[Bowden] باشه.

668
00:54:52,040 --> 00:54:53,840
که به نظر می رسد خوب است.

669
00:54:53,840 --> 00:54:58,800
آیا کسی نظر و یا نگرانی و یا سوالات؟

670
00:55:00,660 --> 00:55:07,720
بنابراین چهار مورد که در حال حاضر به آوردن همه چیز را به تنها بودن - و یا آن را حدود پنج به نظر می رسد -

671
00:55:07,720 --> 00:55:13,100
اما ما مجبور به در نظر گرفتن که آیا آرایه سمت چپ است از چیزهایی که ما نیاز به ادغام اداره،

672
00:55:13,100 --> 00:55:16,390
آیا آرایه راست است از چیزهایی که ما نیاز به ادغام اداره -

673
00:55:16,390 --> 00:55:18,400
اشاره من در هیچ چیز.

674
00:55:18,400 --> 00:55:21,730
به طوری که آیا آرایه سمت چپ است که از چیزهایی که اجرا و یا آرایه حق است از همه چیز اجرا شده است.

675
00:55:21,730 --> 00:55:24,320
این دو مورد است.

676
00:55:24,320 --> 00:55:30,920
ما همچنین باید در مورد بی اهمیت که آیا چیزی که سمت چپ کمتر از چیزی که درست است.

677
00:55:30,920 --> 00:55:33,910
سپس ما می خواهیم به چیزی که سمت چپ را انتخاب کنید.

678
00:55:33,910 --> 00:55:37,630
اینها موارد است.

679
00:55:37,630 --> 00:55:40,990
پس این درست بود، به طوری که که.

680
00:55:40,990 --> 00:55:46,760
آرایه را ترک کردند. 1، 2، 3. باشه. پس بله، کسانی هستند که چهار چیز را ما در صورت تمایل به انجام.

681
00:55:50,350 --> 00:55:54,510
و ما نمی خواهد بیش از یک تکرار شونده راه حل.

682
00:55:54,510 --> 00:55:55,980
من توصیه می کنم -

683
00:55:55,980 --> 00:56:03,070
ادغام مرتب سازی بر اساس عنوان مثال از یک تابع است که هر دو دم نه بازگشتی است،

684
00:56:03,070 --> 00:56:07,040
کار آسانی نیست به آن دم بازگشتی،

685
00:56:07,040 --> 00:56:13,450
بلکه آن را بسیار آسان نیست، آن را به تکراری.

686
00:56:13,450 --> 00:56:16,910
این بسیار آسان است.

687
00:56:16,910 --> 00:56:19,170
این پیاده سازی مرتب سازی بر اساس ادغام،

688
00:56:19,170 --> 00:56:22,140
ادغام، بدون توجه به آنچه شما انجام دهد، شما در حال رفتن برای ساخت ادغام شده است.

689
00:56:22,140 --> 00:56:29,170
>> بنابراین به صورت بازگشتی مرتب سازی بر اساس ساخته شده در بالا از ادغام فقط ادغام این سه خط است.

690
00:56:29,170 --> 00:56:34,700
مکررا، آن است که بیشتر آزار دهنده و مشکل تر به فکر کردن در مورد.

691
00:56:34,700 --> 00:56:41,860
اما توجه کنید که آن دم بازگشتی از سال mergeSortHelp نیست - هنگامی که آن را می نامد، خود -

692
00:56:41,860 --> 00:56:46,590
هنوز نیاز به انجام کارهای پس از این تماس بازده بازگشتی.

693
00:56:46,590 --> 00:56:50,830
پس این قاب پشته باید ادامه یابد تا حتی پس از فراخوانی این وجود داشته باشد.

694
00:56:50,830 --> 00:56:54,170
و پس از آن زمانی که شما این قاب پشته باید به وجود

695
00:56:54,170 --> 00:56:57,780
زیرا حتی پس از این تماس، ما هنوز نیاز به ادغام.

696
00:56:57,780 --> 00:57:01,920
و آن است که کوچک اما نه بیاهمیت است که این دم را بازگشتی.

697
00:57:04,070 --> 00:57:06,270
پرسش و پاسخ؟

698
00:57:08,300 --> 00:57:09,860
بسیار خوب.

699
00:57:09,860 --> 00:57:13,400
بنابراین رفتن به مرتب سازی - آه، دو چیز من می خواهم برای نشان دادن وجود دارد. باشه.

700
00:57:13,400 --> 00:57:17,840
بازگشت به مرتب کردن بر اساس، ما از این به سرعت انجام دهد.

701
00:57:17,840 --> 00:57:21,030
و یا جستجو. مرتب سازی بر اساس؟ مرتب سازی بر اساس. آره.

702
00:57:21,030 --> 00:57:22,730
بازگشت به آغاز مرتب سازی بر.

703
00:57:22,730 --> 00:57:29,870
ما می خواهیم برای ایجاد یک الگوریتم که نوع آرایه با استفاده از هر الگوریتم

704
00:57:29,870 --> 00:57:33,660
O از N.

705
00:57:33,660 --> 00:57:40,860
پس این چگونه ممکن است؟ آیا هر کسی که هر نوع -

706
00:57:40,860 --> 00:57:44,300
من قبل از اینکه در اشاره کرد -

707
00:57:44,300 --> 00:57:48,300
اگر ما در مورد بهبود از ورود N N به O از N،

708
00:57:48,300 --> 00:57:51,450
ما را بهبود الگوریتم ما به زمان عاقل،

709
00:57:51,450 --> 00:57:55,250
که به معنی چیزی است که می خواهیم به نیاز به انجام به را تشکیل می دهند که برای؟

710
00:57:55,250 --> 00:57:59,520
[دانشجو] فضا. >> آره. ما قصد داریم تا با استفاده از فضای بیشتری است.

711
00:57:59,520 --> 00:58:04,490
و نه حتی فقط فضای بیشتر، از آن نمایی فضای بیشتری است.

712
00:58:04,490 --> 00:58:14,320
بنابراین من فکر می کنم این نوع از الگوریتم چیزی است که شبه، polynom شبه -

713
00:58:14,320 --> 00:58:18,980
شبه - من نمی توانم به یاد داشته باشید. چیزی شبه.

714
00:58:18,980 --> 00:58:22,210
اما این دلیل است که ما نیاز به استفاده از فضای بسیار

715
00:58:22,210 --> 00:58:28,610
که این دست یافتنی است، اما واقع بینانه نیست.

716
00:58:28,610 --> 00:58:31,220
>> و چگونه انجام این کار ما رسیدن به؟

717
00:58:31,220 --> 00:58:36,810
ما می توانیم این کار را در صورتی که ما را تضمین دستیابی به آن است که هر عنصر در آرایه

718
00:58:36,810 --> 00:58:39,600
در زیر به یک اندازه خاص است.

719
00:58:42,070 --> 00:58:44,500
بنابراین اجازه دهید فقط می گویند که اندازه 200،

720
00:58:44,500 --> 00:58:48,130
هر عنصر در یک آرایه زیر اندازه 200.

721
00:58:48,130 --> 00:58:51,080
و این است که در واقع بسیار واقع بینانه است.

722
00:58:51,080 --> 00:58:58,660
شما به راحتی می توانید یک آرایه است که شما می دانید همه چیز در آن

723
00:58:58,660 --> 00:59:00,570
رفتن به کمتر از برخی از شماره.

724
00:59:00,570 --> 00:59:07,400
مثل این می مونه که شما باید برخی از بردار کاملا گسترده و یا چیزی

725
00:59:07,400 --> 00:59:11,810
اما شما می دانید همه چیز را بین 0 و 5،

726
00:59:11,810 --> 00:59:14,790
سپس آن را به میزان قابل توجهی سریعتر برای انجام این کار است.

727
00:59:14,790 --> 00:59:17,930
و در هر یک از عناصر محدود 5 است،

728
00:59:17,930 --> 00:59:21,980
بنابراین این محدود، که این است که چه مقدار از حافظه شما استفاده خواهیم نمود.

729
00:59:21,980 --> 00:59:26,300
بنابراین محدود 200 است.

730
00:59:26,300 --> 00:59:32,960
در تئوری این است که همیشه وجود دارد محدود از یک عدد صحیح تنها می تواند تا 4 میلیارد دلار باشد،

731
00:59:32,960 --> 00:59:40,600
اما این غیر واقعی از آن پس ما می شود با استفاده از فضا

732
00:59:40,600 --> 00:59:44,400
منظور از 4 میلیارد. به طوری که غیر واقعی است.

733
00:59:44,400 --> 00:59:47,060
اما در اینجا، ما محدود به ما می گویند 200 است.

734
00:59:47,060 --> 00:59:59,570
ترفند برای انجام آن را در O از N است که ما یک آرایه به نام شمارش از اندازه محدود است.

735
00:59:59,570 --> 01:00:10,470
پس در واقع، این یک میانبر برای - من واقعا نمی دانم اگر صدای جرنگ جرنگ می کند این است.

736
01:00:11,150 --> 01:00:15,330
اما در GCC حداقل - I'm فرض صدای جرنگ جرنگ آن را بیش از حد -

737
01:00:15,330 --> 01:00:18,180
این فقط کل آرایه را به 0s و مقداردهی اولیه.

738
01:00:18,180 --> 01:00:25,320
بنابراین اگر من نمی خواهم به انجام این کار، پس از آن من به طور جداگانه می تواند برای انجام (اعضای هیات من = 0؛

739
01:00:25,320 --> 01:00:31,500
I <متصل به، من + +) و تعداد [من] = 0؛

740
01:00:31,500 --> 01:00:35,260
بنابراین در حال حاضر همه چیز تا 0، مقداردهی اولیه می شود.

741
01:00:35,260 --> 01:00:39,570
من بیش از آرایه تکرار،

742
01:00:39,570 --> 01:00:51,920
و آنچه من انجام می دهند این است که من شمارش تعداد هر یک از - اجازه دهید در اینجا به پایین.

743
01:00:51,920 --> 01:00:55,480
در حال حاضر 4، 15، 16، 50، 8، 23، 42، 108.

744
01:00:55,480 --> 01:01:00,010
چیزی که من شمارش تعداد تکرار هر یک از این عناصر است.

745
01:01:00,010 --> 01:01:03,470
اجازه دهید در واقع اضافه کردن یک زن و شوهر بیشتر در اینجا با برخی از تکرار.

746
01:01:03,470 --> 01:01:11,070
بنابراین ارزش ما در اینجا، ارزش آن در حال رفتن به آرایه های [i].

747
01:01:11,070 --> 01:01:14,850
بنابراین وال می تواند 4 یا 8 یا هر چیز دیگری.

748
01:01:14,850 --> 01:01:18,870
و در حال حاضر من به شمارش چه بسیاری که ارزش من دیده ام،

749
01:01:18,870 --> 01:01:21,230
به طوری که تعداد [VAL] + +؛

750
01:01:21,230 --> 01:01:29,430
بعد از این انجام شده است، مهم است این است که به دنبال چیزی شبیه به 0001 است.

751
01:01:29,430 --> 01:01:42,190
اجازه دهید شمارش [VAL] - مکلف + 1.

752
01:01:42,190 --> 01:01:48,230
>> حالا که فقط برای این واقعیت است که ما در حال شروع از 0 حساب.

753
01:01:48,230 --> 01:01:50,850
بنابراین اگر 200 است که برای رفتن به بزرگترین ما شماره،

754
01:01:50,850 --> 01:01:54,720
و سپس 0 تا 200 201 چیز است.

755
01:01:54,720 --> 01:02:01,540
بنابراین شمارش، آن را مانند 00،001 زیرا ما یکی از 4.

756
01:02:01,540 --> 01:02:10,210
سپس خواهیم 0001 که در آن ما یک 1 در صفحه اول 8 تعداد را داشته باشند.

757
01:02:10,210 --> 01:02:14,560
خواهیم 2 در شاخص از 23rd تعداد را داشته باشند.

758
01:02:14,560 --> 01:02:17,630
خواهیم 2 در 42 شاخص از تعداد را داشته باشند.

759
01:02:17,630 --> 01:02:21,670
بنابراین ما می توانیم به تعداد استفاده کنید.

760
01:02:34,270 --> 01:02:44,920
بنابراین num_of_item = شمارش های [i].

761
01:02:44,920 --> 01:02:52,540
و بنابراین اگر num_of_item 2، این بدان معناست که ما می خواهیم برای وارد کردن 2 شماره من

762
01:02:52,540 --> 01:02:55,290
به ما آرایه طبقه بندی شده اند.

763
01:02:55,290 --> 01:03:02,000
بنابراین ما نیاز به پیگیری تا چه حد ما را به آرایه.

764
01:03:02,000 --> 01:03:05,470
بنابراین شاخص = 0.

765
01:03:05,470 --> 01:03:09,910
آرایه - من فقط آن را بنویسید.

766
01:03:16,660 --> 01:03:18,020
شمارش -

767
01:03:19,990 --> 01:03:28,580
آرایه [فهرست مطالب + +] = من؛

768
01:03:28,580 --> 01:03:32,490
این است که آنچه را که من می خواهم؟ من فکر می کنم این چیزی است که من می خواهم.

769
01:03:35,100 --> 01:03:38,290
بله، این به نظر می رسد خوب است. باشه.

770
01:03:38,290 --> 01:03:43,050
پس آیا همه درک چه هدف از آرایه شمارش من است؟

771
01:03:43,050 --> 01:03:48,140
شمارش تعداد تکرار هر یک از این اعداد است.

772
01:03:48,140 --> 01:03:51,780
سپس من به تکرار بیش از آن آرایه شمارش،

773
01:03:51,780 --> 01:03:57,190
و موقعیت i ام در آرایه شمارش

774
01:03:57,190 --> 01:04:01,930
از من این است که باید در درون آرایه مرتب شده ظاهر می شود.

775
01:04:01,930 --> 01:04:06,840
به همین دلیل است که تعداد از 4 رفتن به (1)

776
01:04:06,840 --> 01:04:11,840
و تعداد از 8 رفتن به (1)، شمارش از 23 به 2 است.

777
01:04:11,840 --> 01:04:16,900
به طوری که بسیاری از آنها من می خواهم به من آرایه ای طبقه بندی شده اند وارد است.

778
01:04:16,900 --> 01:04:19,200
پس من فقط انجام دهد.

779
01:04:19,200 --> 01:04:28,960
من قرار دادن num_of_item من به من آرایه ای طبقه بندی شده اند.

780
01:04:28,960 --> 01:04:31,670
>> پرسش و پاسخ؟

781
01:04:32,460 --> 01:04:43,100
و به این ترتیب باز هم، این زمان خطی است که از آنجا که ما بیش از این تکرار یک بار،

782
01:04:43,100 --> 01:04:47,470
اما آن را نیز خطی در آنچه در این شماره اتفاق می افتد،

783
01:04:47,470 --> 01:04:50,730
و پس از آن به شدت در مورد آنچه متصل به خود را دارد.

784
01:04:50,730 --> 01:04:53,290
با متصل از 200، که آن بد نیست.

785
01:04:53,290 --> 01:04:58,330
اگر متصل به خود را در حال رفتن به 10،000، پس از آن که کمی بدتر،

786
01:04:58,330 --> 01:05:01,360
اما اگر متصل به خود را در حال رفتن به 4 میلیارد دلار، که کاملا غیر واقعی است

787
01:05:01,360 --> 01:05:07,720
و این آرایه به اندازه 4 میلیارد دلار، که غیر واقعی است.

788
01:05:07,720 --> 01:05:10,860
به طوری که که. پرسش و پاسخ؟

789
01:05:10,860 --> 01:05:13,270
[پاسخ دانش آموز نامفهوم] >> درست است.

790
01:05:13,270 --> 01:05:15,710
من متوجه شدم یک چیز دیگر هنگامی که ما به رفتن را از طریق.

791
01:05:17,980 --> 01:05:23,720
من فکر می کنم مشکل این بود که در لوکاس و احتمالا هر یکی از ما را دیده ام.

792
01:05:23,720 --> 01:05:26,330
من کاملا فراموش کرده.

793
01:05:26,330 --> 01:05:31,040
تنها چیزی که من می خواستم به اظهار نظر در مورد این است که زمانی که شما در حال خرید و فروش با چیزهایی مانند شاخص،

794
01:05:31,040 --> 01:05:38,320
شما واقعا هرگز دیدن این زمانی که شما در حال نوشتن یک حلقه for،

795
01:05:38,320 --> 01:05:41,120
اما از نظر فنی، هر زمان که شما در حال خرید و فروش با این شاخص،

796
01:05:41,120 --> 01:05:45,950
شما خیلی باید همیشه با اعداد صحیح بدون علامت رسیدگی کند.

797
01:05:45,950 --> 01:05:53,850
دلیل این کار این است که زمانی که شما در حال خرید و فروش با اعداد صحیح امضا شده،

798
01:05:53,850 --> 01:05:56,090
بنابراین اگر شما دارای 2 امضا شده اعداد صحیح و به آنها اضافه کنید با هم

799
01:05:56,090 --> 01:06:00,640
و آنها در نهایت بیش از حد بزرگ است، سپس شما را تا پایان با یک عدد منفی است.

800
01:06:00,640 --> 01:06:03,410
به طوری که سرریز عدد صحیح است.

801
01:06:03,410 --> 01:06:10,500
>> اگر من اضافه کردن 2 میلیارد و 1 میلیارد، من در نهایت با منفی 1 میلیارد است.

802
01:06:10,500 --> 01:06:15,480
که چگونه اعداد صحیح بر روی کامپیوتر کار می کنند.

803
01:06:15,480 --> 01:06:17,510
بنابراین این مشکل با استفاده از -

804
01:06:17,510 --> 01:06:23,500
خوب مگر اینکه پایین اتفاق می افتد می شود 2 میلیارد دلار و تا اتفاق می افتد می شود 1 میلیارد،

805
01:06:23,500 --> 01:06:27,120
پس از آن این است که رفتن به منفی 1 میلیارد است و پس از آن ما در حال رفتن به تقسیم آن را در 2

806
01:06:27,120 --> 01:06:29,730
و در نهایت با منفی 500 میلیون است.

807
01:06:29,730 --> 01:06:33,760
پس این تنها یک مسئله اگر شما اتفاق می افتد را از طریق یک آرایه است

808
01:06:33,760 --> 01:06:38,070
از میلیاردها از چیزها.

809
01:06:38,070 --> 01:06:44,050
اما اگر + پایین تا سرریز اتفاق می افتد، پس از آن که یک مشکل است.

810
01:06:44,050 --> 01:06:47,750
به محض این که ما آنها را بدون علامت، و سپس 2 میلیارد به علاوه 1 میلیارد 3 میلیارد دلار است.

811
01:06:47,750 --> 01:06:51,960
3 میلیارد تقسیم بر 2 1.5 میلیارد دلار است.

812
01:06:51,960 --> 01:06:55,670
بنابراین به محض این که آنها بدون علامت، همه چیز کامل است.

813
01:06:55,670 --> 01:06:59,900
و به طوری که موضوع زمانی که شما در حال نوشتن خود را برای حلقه ها،

814
01:06:59,900 --> 01:07:03,940
و در واقع، آن را احتمالا از آن به صورت خودکار.

815
01:07:09,130 --> 01:07:12,330
در واقع فقط به شما داد.

816
01:07:12,330 --> 01:07:21,610
بنابراین اگر این عدد را بیش از حد بزرگ است فقط در یک عدد صحیح باشد، اما آن را در یک عدد صحیح بدون علامت مناسب،

817
01:07:21,610 --> 01:07:24,970
آن را در شما داد، به طوری که به همین دلیل شما به این موضوع واقعا هرگز اجرا است.

818
01:07:29,150 --> 01:07:34,820
شما می توانید ببینید که یک شاخص است هرگز به منفی باشد،

819
01:07:34,820 --> 01:07:39,220
و تا زمانی که شما در حال تکرار بیش از یک آرایه،

820
01:07:39,220 --> 01:07:43,970
شما می توانید به تقریبا همیشه بدون علامت اعضای هیات من می گویند، اما شما واقعا لازم نیست که.

821
01:07:43,970 --> 01:07:47,110
چیزهایی که در حال رفتن به محل کار بسیار خوبی است.

822
01:07:48,740 --> 01:07:50,090
باشه. [زمزمه] چه زمانی است؟

823
01:07:50,090 --> 01:07:54,020
آخرین چیزی که من می خواستم برای نشان دادن - و من فقط آن را انجام دهید واقعا سریع است.

824
01:07:54,020 --> 01:08:03,190
شما می دانید که ما چگونه # تعریف، بنابراین ما # می تواند حداکثر 5 یا چیزی تعریف کنید؟

825
01:08:03,190 --> 01:08:05,940
بیایید MAX نمی کنند. # محدود به 200 تعریف کنیم. این چیزی است که ما قبل از انجام.

826
01:08:05,940 --> 01:08:10,380
است که به تعریف یک ثابت است که فقط برای رفتن به کپی و جا به جا

827
01:08:10,380 --> 01:08:13,010
هر جا که اتفاق می افتد به نوشتن مکلف.

828
01:08:13,010 --> 01:08:18,189
>> بنابراین، ما در واقع می تواند با # تعریف می کند انجام دهد.

829
01:08:18,189 --> 01:08:21,170
# ما می توانید توابع را تعریف کنیم.

830
01:08:21,170 --> 01:08:23,410
آنها واقعا نمی توابع، اما ما آنها را توابع.

831
01:08:23,410 --> 01:08:36,000
به عنوان مثال می تواند چیزی شبیه به MAX (x، y) را به عنوان (؟: X X <Y Y) تعریف شده است. باشه.

832
01:08:36,000 --> 01:08:40,660
بنابراین شما باید به نحو عملگر سه تایی استفاده می شود،

833
01:08:40,660 --> 01:08:49,029
اما X کمتر از Y است؟ بازگشت Y، دیگری X بازگشت.

834
01:08:49,029 --> 01:08:54,390
بنابراین شما می توانید ببینید که شما می توانید این تابع را جداگانه،

835
01:08:54,390 --> 01:09:01,399
و تابع می تواند مانند بولی MAX طول می کشد 2 استدلال، بازگشت.

836
01:09:01,399 --> 01:09:08,340
این یکی از آنهایی که شایع ترین که من می بینم مثل این انجام شده است. ما آنها را ماکروها.

837
01:09:08,340 --> 01:09:11,790
این یک ماکرو است.

838
01:09:11,790 --> 01:09:15,859
این نحو برای آن است.

839
01:09:15,859 --> 01:09:18,740
شما می توانید یک ماکرو برای انجام هر آنچه می خواهید بنویسید.

840
01:09:18,740 --> 01:09:22,649
شما غالبا ماکرو برای اشکال زدایی printfs و چیزهای ها را ببینید.

841
01:09:22,649 --> 01:09:29,410
بنابراین یک نوع از printf، ثابت ویژه در C مانند زیرین به خط زیرین به وجود دارد،

842
01:09:29,410 --> 01:09:31,710
2 تأکید LINE تأکید،

843
01:09:31,710 --> 01:09:37,550
و همچنین من فکر می کنم 2 تأکید تابع وجود دارد. که ممکن است آن را. چیزی شبیه به آن.

844
01:09:37,550 --> 01:09:40,880
کسانی که همه چیز را با نام تابع جایگزین خواهد شد

845
01:09:40,880 --> 01:09:42,930
یا شماره خط است که شما در آن هستید.

846
01:09:42,930 --> 01:09:48,630
اغلب، شما ارسال اشکال زدایی printfs که پایین در اینجا من می تواند فقط بنویسید

847
01:09:48,630 --> 01:09:54,260
اشکال زدایی و آن را به شماره خط و تابع که من اتفاق می افتد به چاپ

848
01:09:54,260 --> 01:09:57,020
که آن را بیانیه ای که DEBUG مواجه می شوند.

849
01:09:57,020 --> 01:09:59,550
و شما همچنین می توانید چیزهای دیگر را چاپ کنید.

850
01:09:59,550 --> 01:10:05,990
بنابراین یک چیز شما باید مراقب این است اگر من به اتفاق # تعریف DOUBLE_MAX

851
01:10:05,990 --> 01:10:11,380
به عنوان چیزی شبیه به 2 * Y و 2 * X.

852
01:10:11,380 --> 01:10:14,310
بنابراین دلیل هر چیز دیگری، شما اتفاق می افتد که بسیاری انجام دهد.

853
01:10:14,310 --> 01:10:16,650
پس از آن یک ماکرو را.

854
01:10:16,650 --> 01:10:18,680
این است که در واقع شکسته شده است.

855
01:10:18,680 --> 01:10:23,050
من می خواهم آن را با انجام کاری مانند DOUBLE_MAX (3، 6) تماس بگیرید.

856
01:10:23,050 --> 01:10:27,530
بنابراین آنچه که باید می گردد؟

857
01:10:28,840 --> 01:10:30,580
[دانشجو] 12.

858
01:10:30,580 --> 01:10:34,800
بله، 12 باید بازگشت، و 12 بازگشته است.

859
01:10:34,800 --> 01:10:43,350
3 می شود برای x جایگزین، 6 می شود سالانه برای جایگزین، و ما بازگشت 2 * 6، 12.

860
01:10:43,350 --> 01:10:47,710
در حال حاضر آنچه در مورد این؟ چه باید می گردد؟

861
01:10:47,710 --> 01:10:50,330
[دانشجو] 14. >> در حالت ایده آل، 14.

862
01:10:50,330 --> 01:10:55,290
این موضوع این است که کار چگونه مخلوط را تعریف می کند، به یاد داشته باشید آن را یک کپی تحت اللفظی و رب

863
01:10:55,290 --> 01:11:00,160
از همه چیز تا حد زیادی، پس چه این به عنوان تفسیر

864
01:11:00,160 --> 01:11:11,270
است 3 کمتر از 1 به علاوه 6، 2 بار در 1 به علاوه 6، 2 بار 3.

865
01:11:11,270 --> 01:11:19,780
>> بنابراین به همین دلیل شما تقریبا همیشه بپیچید همه چیز را در پرانتز.

866
01:11:22,180 --> 01:11:25,050
هر متغیر شما تقریبا همیشه در پرانتز بپیچید.

867
01:11:25,050 --> 01:11:29,570
مواردی که شما لازم نیست که در وجود دارد، مثل من می دانم که من لازم نیست که برای انجام این کار در اینجا

868
01:11:29,570 --> 01:11:32,110
زیرا کمتر از است که تقریبا همیشه فقط رفتن به محل کار،

869
01:11:32,110 --> 01:11:34,330
هر چند که حتی ممکن است درست باشد.

870
01:11:34,330 --> 01:11:41,870
اگر چیزی است که مسخره مانند DOUBLE_MAX (1 == 2) وجود دارد،

871
01:11:41,870 --> 01:11:49,760
پس از آن که با 3 کمتر از 1 جایگزین برابر برابر 2،

872
01:11:49,760 --> 01:11:53,460
و به همین ترتیب پس از آن که آن را به انجام 3 کمتر از 1، کند که برابر 2،

873
01:11:53,460 --> 01:11:55,620
که آن چیزی نیست که ما می خواهیم.

874
01:11:55,620 --> 01:12:00,730
لذا به منظور جلوگیری از هر گونه مشکلات اولویت عملگر،

875
01:12:00,730 --> 01:12:02,870
همیشه در پرانتز بپیچید.

876
01:12:03,290 --> 01:12:07,700
باشه. و آن را، 5:30.

877
01:12:08,140 --> 01:12:12,470
اگر شما هر گونه سوال در مورد pset، به ما اطلاع دهید.

878
01:12:12,470 --> 01:12:18,010
باید سرگرم کننده است، و نسخه هکر نیز بسیار واقعی تر است

879
01:12:18,010 --> 01:12:22,980
از نسخه هکر از سال گذشته است، بنابراین ما امیدواریم که بسیاری از شما آن را امتحان کنید.

880
01:12:22,980 --> 01:12:26,460
سال گذشته بسیار سخت و طاقت فرسا بود.

881
01:12:28,370 --> 01:12:30,000
>> [CS50.TV]