1 00:00:00,000 --> 00:00:11,100 >> [Musiqi ifa] 2 00:00:11,100 --> 00:00:11,490 >> DAVID J. Malan: Yaxşı. 3 00:00:11,490 --> 00:00:12,170 Belə ki, geri salamlayıram. 4 00:00:12,170 --> 00:00:15,180 Bu CS50, və deyil Həftənin üç sonu. 5 00:00:15,180 --> 00:00:17,770 >> Belə ki, son bir neçə həftə geri biz kifayət qədər bir az sərf etdik 6 00:00:17,770 --> 00:00:20,820 C, proqramlaşdırma üzrə, sintaksis zaman. 7 00:00:20,820 --> 00:00:24,680 Siz hələ değilseniz və bu, olduqca normal olmaq, Problem Set 2 ilə mübarizə 8 00:00:24,680 --> 00:00:25,950 divar qarşı baş tarpıltı. 9 00:00:25,950 --> 00:00:28,310 Bu sirli-looking hata mesajları var və hataları ki, 10 00:00:28,310 --> 00:00:29,220 olduqca aşağı Chase bilməz. 11 00:00:29,220 --> 00:00:32,310 Çünki arxayın ki, yalnız bir bir neçə həftə vaxt geri baxmaq lazımdır 12 00:00:32,310 --> 00:00:35,930 Sezar kimi şeylər, və [? V-genair?] bəlkə Crack və 13 00:00:35,930 --> 00:00:40,050 siz gəldiniz yalnız nə qədər həyata qısa müddət ərzində. 14 00:00:40,050 --> 00:00:43,670 Hər hansı bir təsəlli var Belə ki, İndi orada asmaq. 15 00:00:43,670 --> 00:00:46,610 >> Bu gün, baxmayaraq ki, biz keçid başlayır şeyi yüksək səviyyədə. 16 00:00:46,610 --> 00:00:49,820 Və biz verilən etmək başlamaq uşaqlar proqram necə və ya 17 00:00:49,820 --> 00:00:52,090 əvvəlindən az ki, rahatlıq səviyyəsi. 18 00:00:52,090 --> 00:00:56,520 Və biz necə biz hesab başlarsınız daha çox proqram hazırlanması haqqında getmək 19 00:00:56,520 --> 00:00:57,440 səmərəli. 20 00:00:57,440 --> 00:01:01,090 Biz optimize haqqında getmək necə bizim alqoritmlər səmərəliliyinin və 21 00:01:01,090 --> 00:01:03,110 ümumiyyətlə həlli maraqlı problemləri. 22 00:01:03,110 --> 00:01:06,850 Və ki, verilən almaq üçün başlanğıc biz istəyirdi, biz bir qədər kod bilər 23 00:01:06,850 --> 00:01:08,350 biz nəzərə nümunələr. 24 00:01:08,350 --> 00:01:11,430 Bu gün Beləliklə, biz klaviatura toxunmayın kodu hər hansı bir formada üçün. 25 00:01:11,430 --> 00:01:15,150 Bu, çox yüksək səviyyədə olacaq, olacaq nəticə etibarilə, problem həll haqqında. 26 00:01:15,150 --> 00:01:20,490 >> Belə ki nöqtəsinə almaq üçün, mənə təklif bildirin ki, aşağıdakı yeddi 27 00:01:20,490 --> 00:01:24,290 düzbucaqlı arxasında, yeddi qapı təmsil olan bütün dəstə var 28 00:01:24,290 --> 00:01:26,340 ədəd, onlardan sayı 50-dir. 29 00:01:26,340 --> 00:01:30,470 Mənə bu bu layihə edək burada da ekran. 30 00:01:30,470 --> 00:01:36,770 Və biz könüllü lazımdır ki, təklif Qarşımda bir sıra tapmaq 31 00:01:36,770 --> 00:01:38,140 görmək üçün burada internet. 32 00:01:38,140 --> 00:01:40,755 Çəhrayı ilə qədər Hadi. 33 00:01:40,755 --> 00:01:43,050 Bütün hüquqlar. 34 00:01:43,050 --> 00:01:43,930 Sizin adınız nədir? 35 00:01:43,930 --> 00:01:44,850 >> Jennifer: [işitilemez] 36 00:01:44,850 --> 00:01:45,170 >> DAVID J. Malan: Üzr istəyirik? 37 00:01:45,170 --> 00:01:45,860 >> Jennifer: Jennifer. 38 00:01:45,860 --> 00:01:46,390 >> DAVID J. Malan: Jennifer. 39 00:01:46,390 --> 00:01:46,980 Bütün sağ, Jennifer. 40 00:01:46,980 --> 00:01:47,630 Cavab gözəl. 41 00:01:47,630 --> 00:01:48,370 Up Hadi. 42 00:01:48,370 --> 00:01:52,430 Belə ki, bu burada yeddi qapı var, və nə Mən burada bizim üçün nə istediğiniz 43 00:01:52,430 --> 00:01:56,560 Sizin sinif yoldaşları bütün qarşısında, Bizə sayı 50 tap. 44 00:01:56,560 --> 00:02:00,860 Bir sıra tapmaq üçün, peek arxasında bilərsiniz sadəcə tıqqıltı ilə bu qapıların hər hansı 45 00:02:00,860 --> 00:02:03,030 qapıları biri və bu onun nömrəsi aşkar edəcək. 46 00:02:03,030 --> 00:02:06,080 Və nin görək necə tez Bizə sayı 50 tapa bilərsiniz. 47 00:02:06,080 --> 00:02:09,979 48 00:02:09,979 --> 00:02:11,229 >> 15. 49 00:02:11,229 --> 00:02:13,110 50 00:02:13,110 --> 00:02:14,360 16. 51 00:02:14,360 --> 00:02:16,270 52 00:02:16,270 --> 00:02:16,530 50. 53 00:02:16,530 --> 00:02:17,350 Qəşəng edilir. 54 00:02:17,350 --> 00:02:18,040 Bütün hüquqlar. 55 00:02:18,040 --> 00:02:19,906 Jennifer üçün alqış dəyirmi. 56 00:02:19,906 --> 00:02:21,530 >> [Alqış] 57 00:02:21,530 --> 00:02:22,320 >> Bütün hüquqlar. 58 00:02:22,320 --> 00:02:25,254 Belə ki, strategiya nə idi , 50 sayı tapmaq? 59 00:02:25,254 --> 00:02:27,222 >> Jennifer: Um, bəlkə əgər fikir - 60 00:02:27,222 --> 00:02:27,714 [Işitilemez] 61 00:02:27,714 --> 00:02:28,206 >> DAVID J. Malan: Oh. 62 00:02:28,206 --> 00:02:29,630 Bu bir ikinci verin. 63 00:02:29,630 --> 00:02:32,420 Belə ki, strategiya üçün idi , 50 sayı tapmaq? 64 00:02:32,420 --> 00:02:34,760 >> Jennifer: Belə ki, yalnız-da başlayacaq görmək başlayan nə ilk sayı 65 00:02:34,760 --> 00:02:38,590 bəlkə, əgər, sonra fikirləşdim onlar sorted edirik, yalnız davam edəcəyik 66 00:02:38,590 --> 00:02:39,970 up yüksək tıqqıltı? 67 00:02:39,970 --> 00:02:40,140 >> DAVID J. Malan: OK. 68 00:02:40,140 --> 00:02:42,910 Və biz gördük görünür halda olması. 69 00:02:42,910 --> 00:02:45,670 Baxmayaraq ki, geri soymaq qat edək bir az bit, və siz getmək istəyirəm 70 00:02:45,670 --> 00:02:47,640 irəli və digər qapıları aşkar seçdiyiniz bilər? 71 00:02:47,640 --> 00:02:50,400 72 00:02:50,400 --> 00:02:51,712 >> Jennifer: Oh, əziz. 73 00:02:51,712 --> 00:02:53,128 >> DAVID J. Malan: Ah. 74 00:02:53,128 --> 00:02:54,280 >> Jennifer: Belə ki, Mən yalnız şanslı var. 75 00:02:54,280 --> 00:02:55,270 >> DAVID J. Malan: Beləliklə, siz xoşbəxt var. 76 00:02:55,270 --> 00:02:55,710 Bütün hüquqlar. 77 00:02:55,710 --> 00:02:56,795 Belə ki, pis deyil. 78 00:02:56,795 --> 00:02:58,750 Amma bir Maraqlıdır fikir, sağ? 79 00:02:58,750 --> 00:03:01,870 , Siz ehtimal və siz almaq əgər Həqiqətən, bir az orada uğurlu. 80 00:03:01,870 --> 00:03:05,350 Amma nömrələri ki, güman əgər sorted, daha dəqiq ola bilər 81 00:03:05,350 --> 00:03:08,750 ki, təsir necə Sizin davranış? 82 00:03:08,750 --> 00:03:11,715 >> Jennifer: onlar sıralanır idi, mən iri bəlkə kiçik düşündüm. 83 00:03:11,715 --> 00:03:11,970 >> DAVID J. Malan: OK. 84 00:03:11,970 --> 00:03:15,260 >> Jennifer: Yoxsa bu qədər başa əgər olan kiçik sonra böyük, həqiqətən böyük. 85 00:03:15,260 --> 00:03:15,540 >> DAVID J. Malan: OK. 86 00:03:15,540 --> 00:03:18,170 Belə ki, kiçik ən böyük, və ya ən böyük kiçik. 87 00:03:18,170 --> 00:03:21,990 Amma mənə təklif ki, siz idi Güman uğursuz kazanılmış və güman ki, onlar 88 00:03:21,990 --> 00:03:26,840 , əslində, sorted deyil, necə bir çox o qapı siz peek idi bilər 89 00:03:26,840 --> 00:03:28,590 ki, pis halda arxasında? 90 00:03:28,590 --> 00:03:29,860 >> Jennifer: Hamısı. 91 00:03:29,860 --> 00:03:30,420 >> DAVID J. Malan: Hamısı. 92 00:03:30,420 --> 00:03:31,740 Elə ümumiləşdirmək edək n kimi. 93 00:03:31,740 --> 00:03:34,790 Orada 7 olmaq olur, lakin qoy daha çox ümumiyyətlə var n qapı var demək 94 00:03:34,790 --> 00:03:35,650 burada ekran. 95 00:03:35,650 --> 00:03:40,110 Belə ki, ən pis halda, siz var ki, 7 qapılar, və ya n qapılar arxasında baxmaq. 96 00:03:40,110 --> 00:03:44,140 Və bu, həqiqətən bir az var ki, uğurlar bu gün, ancaq həqiqətən xətti var 97 00:03:44,140 --> 00:03:46,440 növ alqoritm belə olsa ətrafında atlama cür idi. 98 00:03:46,440 --> 00:03:47,080 Ədalətli mi? 99 00:03:47,080 --> 00:03:47,500 >> Jennifer: Bəli. 100 00:03:47,500 --> 00:03:50,000 >> DAVID J. Malan: Bəli, mənə görək əgər strategiya dəyişikliklər bizə hərəkət əgər 101 00:03:50,000 --> 00:03:52,190 Burada bizim ikinci misal 7 müxtəlif qapılar. 102 00:03:52,190 --> 00:03:55,240 Eyni nömrələri, lakin bu vaxt ayrılır. 103 00:03:55,240 --> 00:03:58,350 Olacaq burada strategiyası nədir fikrinizi yerinə qoymaq üçün çalışırıq nə 104 00:03:58,350 --> 00:03:59,310 Digər nömrələr idi - 105 00:03:59,310 --> 00:03:59,930 >> Jennifer: OK. 106 00:03:59,930 --> 00:04:02,290 >> DAVID J. Malan: - əvvəllər? 107 00:04:02,290 --> 00:04:03,180 >> Jennifer: başlanğıc edək birinci ilə. 108 00:04:03,180 --> 00:04:03,540 >> DAVID J. Malan: Yaxşı. 109 00:04:03,540 --> 00:04:05,190 Birinci ilə başlayın. 110 00:04:05,190 --> 00:04:05,960 4. 111 00:04:05,960 --> 00:04:08,810 İndi harada getmək gedən və niyə? 112 00:04:08,810 --> 00:04:10,040 >> Jennifer: 4 həqiqətən kiçik. 113 00:04:10,040 --> 00:04:12,500 Onlar sort bəlkə kiçik istəyirik, əgər böyük, bu olmalıdır 114 00:04:12,500 --> 00:04:13,290 - iki dəfə ki, ola bilər. 115 00:04:13,290 --> 00:04:13,670 >> DAVID J. Malan: OK. 116 00:04:13,670 --> 00:04:15,990 Gəlin hesab edirəm ki, bax? 117 00:04:15,990 --> 00:04:19,050 >> Jennifer: son bir cəhd edin. 118 00:04:19,050 --> 00:04:19,500 Gözəl. 119 00:04:19,500 --> 00:04:20,880 >> DAVID J. Malan: Çox gözəl işlər. 120 00:04:20,880 --> 00:04:21,860 Bütün hüquqlar. 121 00:04:21,860 --> 00:04:23,010 >> [Alqış] 122 00:04:23,010 --> 00:04:24,310 >> DAVID J. Malan: OK. 123 00:04:24,310 --> 00:04:26,790 Belə ki, əslində bu yapýyorsun sen horribly, çünki 124 00:04:26,790 --> 00:04:27,700 çox yaxşı edir. 125 00:04:27,700 --> 00:04:31,150 Hansı bizə iqtidarında yarpağı müəyyən xal etmək. 126 00:04:31,150 --> 00:04:32,565 Belə ki, burada geri gəzmək üçün cəhd edək. 127 00:04:32,565 --> 00:04:34,560 >> Jennifer: OK. 128 00:04:34,560 --> 00:04:35,980 >> DAVID J. Malan: Çox yaxşı Buna baxmayaraq, işlər. 129 00:04:35,980 --> 00:04:39,060 Belə ki, ilin əvvəlində başlayıb siz onu sonra, siz 4 olduğunu gördüm 130 00:04:39,060 --> 00:04:40,240 sonuna köçürülüb. 131 00:04:40,240 --> 00:04:42,320 Amma xoşbəxt əldə etməyib Güman , orada Güman 50 132 00:04:42,320 --> 00:04:42,890 başqa bir yerdə idi. 133 00:04:42,890 --> 00:04:46,190 Sizin Üçüncü addım olub? 134 00:04:46,190 --> 00:04:47,680 >> Jennifer: əvvəlinə qayıt. 135 00:04:47,680 --> 00:04:48,320 >> DAVID J. Malan: geri dön əvvəlinə. 136 00:04:48,320 --> 00:04:51,320 OK, belə ki, toxunub sonra ki, 8 olan bu qapı. 137 00:04:51,320 --> 00:04:51,660 Bütün hüquqlar. 138 00:04:51,660 --> 00:04:52,650 Belə ki, 50 deyil. 139 00:04:52,650 --> 00:04:55,380 Harada növbəti olardı? 140 00:04:55,380 --> 00:04:56,720 >> Jennifer: Mən olmasaydı onlar çeşidlənir bilirik. 141 00:04:56,720 --> 00:04:57,005 >> DAVID J. Malan: Doğru. 142 00:04:57,005 --> 00:04:58,490 Bəli, əgər bilmək onlar sıralanır idi - 143 00:04:58,490 --> 00:04:58,700 >> Jennifer: Oh, evet, bilirdinizmi. 144 00:04:58,700 --> 00:05:00,910 >> DAVID J. Malan: - amma siz yox idi 50 hələ idi bilirsinizmi? 145 00:05:00,910 --> 00:05:01,785 >> Jennifer: Just davam. 146 00:05:01,785 --> 00:05:02,130 >> DAVID J. Malan: Yaxşı. 147 00:05:02,130 --> 00:05:02,520 OK. 148 00:05:02,520 --> 00:05:03,800 Davam edin. 149 00:05:03,800 --> 00:05:05,270 OK, Mən ilə işləyə bilər. 150 00:05:05,270 --> 00:05:05,610 >> Jennifer: OK. 151 00:05:05,610 --> 00:05:07,210 >> DAVID J. Malan: İndi, yalnız değilseniz davam etmək niyyətindədir, nə sizin 152 00:05:07,210 --> 00:05:09,680 alqoritm daxil dəstək devolving. 153 00:05:09,680 --> 00:05:10,740 >> Jennifer: xətti -. 154 00:05:10,740 --> 00:05:11,820 >> DAVID J. Malan: Bu xətti növü deyil. 155 00:05:11,820 --> 00:05:13,480 Amma qoy, mənə təklif bildirin Mənə yerində qoydu. 156 00:05:13,480 --> 00:05:14,900 Mənə səhifəni yenileyin edək. 157 00:05:14,900 --> 00:05:17,120 eyni sayda eyni təşkili, Eyni qapılar. 158 00:05:17,120 --> 00:05:21,350 Amma ki, ilk gün geri edirəm biz bir telefon kitab parçaladı zaman sinfi 159 00:05:21,350 --> 00:05:25,480 yarım növ, və nə idi bizim strategiyası? 160 00:05:25,480 --> 00:05:26,450 >> Jennifer: ortasında başlayın. 161 00:05:26,450 --> 00:05:26,690 >> DAVID J. Malan: OK. 162 00:05:26,690 --> 00:05:27,610 Belə ki, orta-da başlanır. 163 00:05:27,610 --> 00:05:28,790 Elə davam və simülasyonu imkan verir. 164 00:05:28,790 --> 00:05:30,720 Tərəfindən orta Start ki, qapı aşkar. 165 00:05:30,720 --> 00:05:31,660 Belə ki, 16 saylı. 166 00:05:31,660 --> 00:05:35,290 Belə ki, güclü oğlan nə olardı, edən yarısında telefon kitab parçaladı 167 00:05:35,290 --> 00:05:38,450 növbəti qonağı almaq? 168 00:05:38,450 --> 00:05:39,400 >> Jennifer: Bu yarısında gedin. 169 00:05:39,400 --> 00:05:41,700 >> DAVID J. Malan: Və niyə sağa? 170 00:05:41,700 --> 00:05:43,900 >> Jennifer: onlar olsaydı növ kiçik iri, 50 olmalıdır 171 00:05:43,900 --> 00:05:44,720 ki, sonunda. 172 00:05:44,720 --> 00:05:44,920 >> DAVID J. Malan: Yaxşı. 173 00:05:44,920 --> 00:05:45,390 Ümumilikdə ağlabatan. 174 00:05:45,390 --> 00:05:48,380 Belə ki, bir telefon kitab kimi, siz getmək hüququ kimi sol fərqli, lakin burada 175 00:05:48,380 --> 00:05:49,500 əsas paket edir. 176 00:05:49,500 --> 00:05:53,930 İndi, tullamaq və ya qoparmaq bilər Bu problemin yarısı, siz tərk 177 00:05:53,930 --> 00:05:55,970 7 qapı, lakin həqiqətən, yalnız 3. 178 00:05:55,970 --> 00:05:57,870 Hansı təxminən yarısı Problemin ölçüsü. 179 00:05:57,870 --> 00:05:58,350 Bütün hüquqlar. 180 00:05:58,350 --> 00:06:01,890 Belə ki, indi siz nə sağ getmək sonra həyata? 181 00:06:01,890 --> 00:06:05,870 >> Jennifer: Yəni 16, hələ olduqca kiçik 50 nisbi, belə ki, bəlkə mən cəhd edəcəyik 182 00:06:05,870 --> 00:06:06,700 bu bir kimi. 183 00:06:06,700 --> 00:06:07,890 >> DAVID J. Malan: Yaxşı. 184 00:06:07,890 --> 00:06:08,720 42. 185 00:06:08,720 --> 00:06:10,830 Bütün sağ, indi nə üçün belirten instinkt? 186 00:06:10,830 --> 00:06:12,100 >> Jennifer: I üz atmaq olar Bu və sonra yalnız - 187 00:06:12,100 --> 00:06:12,360 >> DAVID J. Malan: OK. 188 00:06:12,360 --> 00:06:14,212 Yaxşı, Əgər üz atmaq olar orada sol yarısı. 189 00:06:14,212 --> 00:06:14,890 >> Jennifer: - Bu bir seçin. 190 00:06:14,890 --> 00:06:15,530 >> DAVID J. Malan: Və hüququ. 191 00:06:15,530 --> 00:06:15,760 >> Jennifer: Bəli. 192 00:06:15,760 --> 00:06:17,820 >> DAVID J. Malan: çətin belə olsa belə, yalnız var zaman, bəlkə də görmək üçün 193 00:06:17,820 --> 00:06:21,320 7 qapılar, indi haqqında düşünmək Bu ardıcıllıq 194 00:06:21,320 --> 00:06:22,620 yalnız tətbiq alqoritmi. 195 00:06:22,620 --> 00:06:24,510 Əvvəlki halda, etdi böyük idi ki, uğurlu olsun. 196 00:06:24,510 --> 00:06:26,540 Amma bir Heuristic istifadə etdi Mən deyərdim. 197 00:06:26,540 --> 00:06:29,150 Siz instinktlərdən növ istifadə və bu olduqca varsa, bu sıralanır bilmədən 198 00:06:29,150 --> 00:06:31,600 əvvəlində kiçik, təbii ki, biz var sağ üçün daha getmək üçün var. 199 00:06:31,600 --> 00:06:34,990 Amma bəzi mənada, siz xoşbəxt var bəlkə bu sayı 100 idi 200 00:06:34,990 --> 00:06:36,220 və bəlkə 50 ortada çox idi. 201 00:06:36,220 --> 00:06:37,910 Bəlkə 50-burada belə idi. 202 00:06:37,910 --> 00:06:40,960 >> Amma fərqli bir az nə etdi bu dəfə, eyni şey idi 203 00:06:40,960 --> 00:06:42,150 təkrar. 204 00:06:42,150 --> 00:06:45,310 Və mən iddia edirəm ki, nə yalnız olsa telefon təsir etməyib 205 00:06:45,310 --> 00:06:48,100 kitab, məsələn, çox şeydir daha alqoritmik və çox 206 00:06:48,100 --> 00:06:49,930 az xüsusi cased. 207 00:06:49,930 --> 00:06:51,620 Daha az instinktiv. 208 00:06:51,620 --> 00:06:57,160 Belə ki, günün sonunda, necə ki, Siz səmərəliliyini təsvir 209 00:06:57,160 --> 00:07:00,530 Siz getdiyi ilk alqoritm, ki, qarşı, sağ 210 00:07:00,530 --> 00:07:03,430 Burada ikinci alqoritm? 211 00:07:03,430 --> 00:07:06,460 >> Jennifer: Bu bir olmalıdır kimi, bəlkə vaxt yarı bölmək, və ya daha çox, evet. 212 00:07:06,460 --> 00:07:07,320 >> DAVID J. Malan: OK, bəlkə də daha çox. 213 00:07:07,320 --> 00:07:10,150 Ki, bir az daha təkan edək. 214 00:07:10,150 --> 00:07:13,030 Həqiqətən nə, biz bu davam edərsə, məntiq, biz mütləq halved 215 00:07:13,030 --> 00:07:15,830 Bu ikinci alqoritmi vaxt çalışan Bu yarım üz ataraq 216 00:07:15,830 --> 00:07:18,470 nömrələri, ancaq yanında nə idi Jennifer aşkar zaman iteration, 217 00:07:18,470 --> 00:07:20,615 ikinci nömrəsinin? 218 00:07:20,615 --> 00:07:22,830 >> Biz yenə qapı nömrələri halved. 219 00:07:22,830 --> 00:07:25,270 Və sonra, biz bundan sonra nə idi əgər ilə oynamaq daha çox qapı var idi? 220 00:07:25,270 --> 00:07:27,520 Biz onları yenidən yarı bölmək, və ki, və yenidən və yenidən. 221 00:07:27,520 --> 00:07:30,420 Və bu, yalnız sizin uşaqlar kimi idi ilk həftəsində dayanan 222 00:07:30,420 --> 00:07:33,000 aşağı oturan sinif, yarısı, yarım Siz, siz yarım oturaraq 223 00:07:33,000 --> 00:07:35,440 bir tək qədər, oturaraq soul durmuşdu. 224 00:07:35,440 --> 00:07:39,050 Və dedi ki, çalışan zaman ki, etdi addımların sayı 225 00:07:39,050 --> 00:07:40,430 nə sifariş haqqında? 226 00:07:40,430 --> 00:07:41,230 >> HOPARLÖR 1: [işitilemez] 227 00:07:41,230 --> 00:07:43,970 >> DAVID J. Malan: Belə ki, log baza n 2- və ya daha çox sadəcə, n daxil. 228 00:07:43,970 --> 00:07:45,060 Belə ki, loqarifmik bir şey. 229 00:07:45,060 --> 00:07:48,380 Və graph bir düz xətt deyil yalnız pis və pis var ki, o, 230 00:07:48,380 --> 00:07:52,490 deyil ki bu maraqlı curve zaman keçdikcə belə pis almaq. 231 00:07:52,490 --> 00:07:53,910 Belə ki, bu fikir yapışmağa imkan verir. 232 00:07:53,910 --> 00:07:54,690 Nin Jennifer minnətdarlığımı bildirirəm. 233 00:07:54,690 --> 00:07:56,150 Up gələn üçün təşəkkür edirik qədər. 234 00:07:56,150 --> 00:07:57,400 Və, san biridir. 235 00:07:57,400 --> 00:08:00,170 236 00:08:00,170 --> 00:08:02,925 No masa lampaları bu gün, lakin biz CS50 stress toplar var. 237 00:08:02,925 --> 00:08:03,420 >> Jennifer: Yay. 238 00:08:03,420 --> 00:08:04,410 >> DAVID J. Malan: Bütün sağ, burada. 239 00:08:04,410 --> 00:08:06,545 Tətbiq üçün təşəkkür edirik burada stress up. 240 00:08:06,545 --> 00:08:07,350 Bütün hüquqlar. 241 00:08:07,350 --> 00:08:10,620 Elə görək biz indi əgər bir az daha bu rəsmiləşdirilməsi. 242 00:08:10,620 --> 00:08:14,820 Belə ki, yenə, biz yalnız nə idi biz kimi mahiyyətcə eyni şey 243 00:08:14,820 --> 00:08:16,660 ilk həftə. 244 00:08:16,660 --> 00:08:23,780 Əksinə sonunda yalnız xətti ilə biz təsvir edən alqoritm, 245 00:08:23,780 --> 00:08:27,210 əvvəl bu düz xətt kimi, qovuşdurmağımız, biz daha bir qapı qoymaq 246 00:08:27,210 --> 00:08:29,610 ekran, sonra Jennifer ki, potensial baxmaq idi 247 00:08:29,610 --> 00:08:30,600 daha bir qapı arxasında. 248 00:08:30,600 --> 00:08:33,490 Biz daha iki qapı qoymaq, o, ola bilər daha iki qapılar arxasında baxmaq. 249 00:08:33,490 --> 00:08:35,990 >> Belə ki, bu xətti var idi nın ölçüsü arasında əlaqələr 250 00:08:35,990 --> 00:08:39,059 X-ox, demək, problem və bu alır vaxt məbləği 251 00:08:39,059 --> 00:08:40,440 y üzərində həll edir. 252 00:08:40,440 --> 00:08:43,330 Amma mən alluding edilib şəkil Bu yaşıl xətt idi. 253 00:08:43,330 --> 00:08:45,970 Green qəsdən, çünki yalnız daha yaxşı hiss etdim. 254 00:08:45,970 --> 00:08:49,790 Nəzəri olaraq, biz bu alqoritm, nə zaman telefon kitab ilə, biz bunu 255 00:08:49,790 --> 00:08:52,420 Uşaqlar bir-birinə hesablanması, və ikinci halda, zaman Jennifer yalnız 256 00:08:52,420 --> 00:08:55,250 burada o qədər idi ki, bu cür idi əsaslı daha yaxşı. 257 00:08:55,250 --> 00:08:57,180 Yalnız iki dəfə sürətli kimi deyildi. 258 00:08:57,180 --> 00:08:58,870 Bu sürətli kimi hətta dörd dəfə deyildi. 259 00:08:58,870 --> 00:09:03,290 Bu nə tamamilə asılı idi giriş ölçüsü kimi idi, nə qədər 260 00:09:03,290 --> 00:09:05,220 etibarilə etdi addımlar. 261 00:09:05,220 --> 00:09:08,040 >> Və biz bütün etmişdir ki, bu sadə ideya telefon kitab ilə verilən, 262 00:09:08,040 --> 00:09:10,200 eyni tətbiq oluna bilər bu kimi bir şey üçün. 263 00:09:10,200 --> 00:09:12,380 Bu daha Təsadüfi ola bilər Əgər güc kimi, kimi tanınan 264 00:09:12,380 --> 00:09:13,940 uçurum və fəth, təsəvvür edin. 265 00:09:13,940 --> 00:09:16,390 Biz nə fərqli olaraq, əlbəttə, telefon kitab. 266 00:09:16,390 --> 00:09:18,300 >> Amma pseudocode, geri bu idi. 267 00:09:18,300 --> 00:09:21,800 Beləliklə, biz yenidən, lakin geri deyil ilk həftə, hamımız ayağa qalxıb 268 00:09:21,800 --> 00:09:25,140 və sonra yarısı yarısı oturdu siz oturdu, siz yarım oturdu. 269 00:09:25,140 --> 00:09:29,280 Bu alqoritm bir həyata keçirilmişdir ki, bir aldadıcı şəkildə bit, o, 270 00:09:29,280 --> 00:09:32,870 Mənə yalnız bir, sayılması deyil əsaslı, daha səmərəli. 271 00:09:32,870 --> 00:09:35,830 Bu halda, mən yararlanarak edilib ikinci resurs. 272 00:09:35,830 --> 00:09:39,470 Növ, çox CPU'lar, çox beyinləri də çox ağıllı insanlar 273 00:09:39,470 --> 00:09:42,740 otaq mənə bir şey almaq yardım edildi bir şey üçün xətti 274 00:09:42,740 --> 00:09:45,190 bir şey, loqarifmik bir şey yaşıl qırmızı. 275 00:09:45,190 --> 00:09:48,650 >> Amma bu halda, Jennifer tək bilərsiniz fundamental olaraq inkişaf 276 00:09:48,650 --> 00:09:52,370 onun ilk alqoritm icrası ilə yenidən, yalnız bir az daha düşünürük. 277 00:09:52,370 --> 00:09:56,650 İndi, onu həyata keçirmək üçün vaxt gəldiyi zaman bu şeyi həyata figuring 278 00:09:56,650 --> 00:10:00,670 Əgər belə yaza nə kodu xətləri yenə təkrar edə bilərsiniz ki, 279 00:10:00,670 --> 00:10:03,350 yenə və yenə növ bir loop moda. 280 00:10:03,350 --> 00:10:06,370 Siz var etmək fikrində deyilik Çünki Jennifer kimi lüks, üçün, ilk etdi 281 00:10:06,370 --> 00:10:10,460 yalnız IFS bütün dəstə var və demək hmm, bu ilk sayı 4 olduqda, 282 00:10:10,460 --> 00:10:11,800 Mənə sonuna bütün yol jump imkan verir. 283 00:10:11,800 --> 00:10:14,180 Ki sayı çox böyük varsa, Ooh, mənə özbaşına geri hərəkət edək 284 00:10:14,180 --> 00:10:15,220 İkinci element üçün. 285 00:10:15,220 --> 00:10:18,210 Siz bir çox olacaq ki, tapa bilərsiniz daha rəsmiləşdirmək üçün nə biz insanların 286 00:10:18,210 --> 00:10:21,270 çox ağlabatan kimi verilən almaq deneysel çalışmalarını, lakin bir kompüter yalnız 287 00:10:21,270 --> 00:10:23,260 Siz demək nə gedir. 288 00:10:23,260 --> 00:10:25,280 >> İndi bu çox maraqlı var təsiri. 289 00:10:25,280 --> 00:10:29,950 Bu şəklin növ növ deməkdir vizual qorxudaraq, lakin bildiriş, harada 290 00:10:29,950 --> 00:10:32,230 bu diaqramda düz xətt var? 291 00:10:32,230 --> 00:10:35,330 Xətti graph harada biz n zəng ki? 292 00:10:35,330 --> 00:10:37,580 Bəli, bu alt doğru sort var Bu şəkil, sağ? 293 00:10:37,580 --> 00:10:40,500 Biz etdik biz bütün növ var belə X-ox və həyata zoomed 294 00:10:40,500 --> 00:10:44,780 y-ox hansı bir mənada almaq üçün cəhd əyriləri digər növləri kimi baxırıq. 295 00:10:44,780 --> 00:10:47,760 >> Və riyazi xüsusiyyətləri ifadələr bu gün məsələ deyil 296 00:10:47,760 --> 00:10:52,440 çox, lakin bir çox var fark çox pis olduğunu alqoritmlər 297 00:10:52,440 --> 00:10:53,470 Xətti ki, bir şey. 298 00:10:53,470 --> 00:10:55,410 Həqiqətən, Cubed n olduqca pis görünür. 299 00:10:55,410 --> 00:10:58,400 2 n olduqca pis görünür. kvadrat n olduqca pis görünür. 300 00:10:58,400 --> 00:11:01,630 Və biz görəcəksiniz nə o bəzi Əslində bu gün ola bilər. 301 00:11:01,630 --> 00:11:05,430 Və log n pis hiss deyil, n daha yaxşı n daxil baza 2-dir. 302 00:11:05,430 --> 00:11:08,080 Amma bilirsiniz, hətta olardı daha gözəl əgər Jennifer, və ya əgər, 303 00:11:08,080 --> 00:11:12,910 ilk həftə ilə gəlmişdi n daxil daxil ki, bir şey. 304 00:11:12,910 --> 00:11:15,880 >> Belə ki, başqa sözlə, bu bütün var mümkün həllər çeşidini 305 00:11:15,880 --> 00:11:18,570 problemlər, hətta burada, bildiriş nə olacaq. 306 00:11:18,570 --> 00:11:22,910 Bu əyriləri I Uzaklaştırmak zaman, hansı mütləq ola gedir 307 00:11:22,910 --> 00:11:26,630 İndi ekranda isə pis? 308 00:11:26,630 --> 00:11:28,680 Belə n Cubed olduqca görünür an pis. 309 00:11:28,680 --> 00:11:32,470 Amma biz həyata zoom və daha çox görmək əgər olacaq olan x və y-ox, 310 00:11:32,470 --> 00:11:34,550 nəticədə hakim? 311 00:11:34,550 --> 00:11:37,120 Belə ki, həqiqətən ki, 2 çıxır n, və yalnız bu anlamaq olar 312 00:11:37,120 --> 00:11:39,990 bəzi getdikcə böyük sayede nömrələri və görürsünüz ki, 2 ilə 313 00:11:39,990 --> 00:11:42,070 n, həqiqətən, böyük çox daha sürətli olur. 314 00:11:42,070 --> 00:11:45,530 Biz həqiqətən, bir 2 Uzaklaştırmak edin n alqoritm tamamilə gücünü zaptetti. 315 00:11:45,530 --> 00:11:48,170 Mən bu gedir demək üçün vaxt kifayət qədər bir az 316 00:11:48,170 --> 00:11:49,460 kompüter vasitəsilə nehrə etmək. 317 00:11:49,460 --> 00:11:52,500 >> Amma xüsusilə, zamanla görürsünüz gələcək problem dəstləri ilə və hətta 318 00:11:52,500 --> 00:11:55,600 son layihələr, veri edir set, bütün doğru böyük olur? 319 00:11:55,600 --> 00:11:58,300 Hətta Facebook ilk versiyası, dostları sayı, və kimi 320 00:11:58,300 --> 00:12:01,840 qeydiyyatdan keçmiş istifadəçilər sayı, böyük var Əgər telefon bu sort edə bilərsiniz 321 00:12:01,840 --> 00:12:05,530 , xətti axtarış şey həyata və ya çox sadə çeşidlənməsi 322 00:12:05,530 --> 00:12:07,030 biz bu gün görəcəksiniz kimi alqoritmi. 323 00:12:07,030 --> 00:12:09,280 Siz daha düşünür başlamaq üçün və bu problemlər haqqında çətindir. 324 00:12:09,280 --> 00:12:12,070 Və problemlər yerlərdə növləri kimi Facebook və Google və Microsoft, 325 00:12:12,070 --> 00:12:16,350 və iş s məhz sual böyük data növ sort 326 00:12:16,350 --> 00:12:18,530 getdikcə bu gün. 327 00:12:18,530 --> 00:12:18,900 >> Bütün hüquqlar. 328 00:12:18,900 --> 00:12:23,800 Ki, ikinci Jennifer müvəffəqiyyəti Belə ki, alqoritm, səmimi, o qəribə etdi 329 00:12:23,800 --> 00:12:26,110 də ilk dəfə, lakin edək bu uğurlar kimi yazmaq ki, biz 330 00:12:26,110 --> 00:12:27,000 Bu baxımdan edə bilərsiniz. 331 00:12:27,000 --> 00:12:30,970 İkinci halda, o kullanılarak geliştirilebiliyor təkrar və alqoritmi 332 00:12:30,970 --> 00:12:34,670 verilən təkrar, lakin o, etdi biz icazə müəyyən ehtimal 333 00:12:34,670 --> 00:12:39,370 öz, lakin o, bəzi ətraflı istismar o yox idi ki, ikinci dəfə 334 00:12:39,370 --> 00:12:39,840 ilk dəfə. 335 00:12:39,840 --> 00:12:41,800 Nə idi? 336 00:12:41,800 --> 00:12:43,050 >> Siyahısı sorted idi. 337 00:12:43,050 --> 00:12:46,350 Siyahısı sıralaması belə kimi, biz Jennifer edə idi ki, iddia 338 00:12:46,350 --> 00:12:47,480 əsaslı yaxşı. 339 00:12:47,480 --> 00:12:51,450 7 qapılar, bəli ki, maraqlı deyil lakin biz 7 milyon Qapı istəyirik bunu nəzərdə tutur. 340 00:12:51,450 --> 00:12:54,080 N daxil mütləq gedir çox, çox yerinə yetirmək üçün 341 00:12:54,080 --> 00:12:55,610 uzun vadede daha sürətli. 342 00:12:55,610 --> 00:12:58,880 Amma o var idi qapıları onun üçün sıralanacaktır. 343 00:12:58,880 --> 00:13:02,320 İndi bunu azadlığı etdi kompüter ekranında əvvəlcədən 344 00:13:02,320 --> 00:13:05,160 Burada, lakin Jennifer Güman özü bunu etmək idi? 345 00:13:05,160 --> 00:13:10,120 Fərz edək ki, sözügedən qapılarını təmsil bir verilənlər bazası məlumat, və ya 346 00:13:10,120 --> 00:13:14,260 Facebook üçün qeydiyyatdan dostlar, və ya internet hər hansı bir web pages ki, 347 00:13:14,260 --> 00:13:16,880 müxtəlif saytlarda oluna bilər indeks və ya üzərində axtarış. 348 00:13:16,880 --> 00:13:20,940 >> Yalnız bir xammal məlumat var idi ki, Güman müəyyən və sizə qalmış, və ya 349 00:13:20,940 --> 00:13:23,010 Jennifer ki, çeşidlənməsi etməliyəm? 350 00:13:23,010 --> 00:13:26,950 Yəni, daha doğrusu, biz cavab tələb edir ki, sualına, yaxşı, nə qədər vaxt 351 00:13:26,950 --> 00:13:31,080 Jennifer, hətta məni qəbul etdilər ki, əvvəlcədən həmin nömrələri düzmək üçün belə 352 00:13:31,080 --> 00:13:32,680 O yararlana bilərlər ki? 353 00:13:32,680 --> 00:13:32,880 Sağ? 354 00:13:32,880 --> 00:13:36,620 Ki, ima, əlbəttə, Çünki bu düzmək üçün mənə çox bir müddət alır, əgər 355 00:13:36,620 --> 00:13:40,800 the heck siz önem verir ki, kim nömrələri, qədər sürətli 50 kimi bir sıra tapa bilərsiniz, 356 00:13:40,800 --> 00:13:44,850 daha Gökhan halda, sanki daha çox cəmi müddəti overwhelmed 357 00:13:44,850 --> 00:13:46,920 əvvəlcədən şeyi çeşidlənməsi ilə etdi? 358 00:13:46,920 --> 00:13:49,320 >> Belə ki, biz mümkün olmadıqda, Bakalým burada şəkil çəkmək. 359 00:13:49,320 --> 00:13:51,370 Mən bütün dəstə daha çox stress var top, kömək edir ki, əgər 360 00:13:51,370 --> 00:13:52,270 burada buz qırmaq. 361 00:13:52,270 --> 00:13:55,690 Və ağla deyil ki, biz yeddi könüllü lazımdır - 362 00:13:55,690 --> 00:13:57,060 OK, haqqında. 363 00:13:57,060 --> 00:13:57,240 Wow. 364 00:13:57,240 --> 00:13:59,250 Beləliklə, biz sərf yoxdur masa lampaları haqqında, görünür. 365 00:13:59,250 --> 00:13:59,690 Bütün hüquqlar. 366 00:13:59,690 --> 00:14:01,530 Belə ki, necə qarşısında iki haqqında. 367 00:14:01,530 --> 00:14:04,160 Geri iki uşaqlar necə haqqında. 368 00:14:04,160 --> 00:14:04,870 Belə ki, dörd var. 369 00:14:04,870 --> 00:14:09,890 Necə haqqında qarşısında beş, altı və yeddi. 370 00:14:09,890 --> 00:14:10,320 Sağ var. 371 00:14:10,320 --> 00:14:13,260 Sizin dost, siz işarə oldu belə ki, mükafat almaq. 372 00:14:13,260 --> 00:14:13,700 >> Bütün hüquqlar. 373 00:14:13,700 --> 00:14:14,410 Up Hadi. 374 00:14:14,410 --> 00:14:17,120 Və niyə biz sizə yoxdur uşaqlar üzərində burada gəlir. 375 00:14:17,120 --> 00:14:18,960 Mən sizə hər bir sıra gedirəm. 376 00:14:18,960 --> 00:14:22,150 Və irəli getmək və özünüzü təşkil eynilə nə üçün 377 00:14:22,150 --> 00:14:25,180 ekranda təsvir etmişdir. 378 00:14:25,180 --> 00:14:26,530 >> [SƏSLƏRİ INTERPOSING] 379 00:14:26,530 --> 00:14:28,160 >> DAVID J. Malan: Oop, sorry. 380 00:14:28,160 --> 00:14:30,210 Bug. 381 00:14:30,210 --> 00:14:32,180 Bütün hüquqlar. 382 00:14:32,180 --> 00:14:32,750 Yaxşı, burada biz gedin. 383 00:14:32,750 --> 00:14:34,180 Sayı beş. 384 00:14:34,180 --> 00:14:35,136 Altı nömrəni. 385 00:14:35,136 --> 00:14:37,770 Bir, iki, üç, dörd, beş, altı, yeddi. 386 00:14:37,770 --> 00:14:39,410 Oh, bu yöndəmsiz. 387 00:14:39,410 --> 00:14:41,210 >> HOPARLÖR 2: Mən yalnız bir almaq lazımdır -. 388 00:14:41,210 --> 00:14:41,900 >> DAVID J. Malan: Yaxşı iş. 389 00:14:41,900 --> 00:14:43,130 Bütün hüquqlar. 390 00:14:43,130 --> 00:14:44,611 Qoşulduğunuz üçün təşəkkür edirik. 391 00:14:44,611 --> 00:14:47,200 >> [Alqış] 392 00:14:47,200 --> 00:14:48,580 >> OK. 393 00:14:48,580 --> 00:14:48,860 Bütün hüquqlar. 394 00:14:48,860 --> 00:14:51,970 Beləliklə, biz, dörd, iki, altı var bir, üç, yeddi, beş. 395 00:14:51,970 --> 00:14:56,010 Biz yeddi könüllü belə mükəmməl Burada eni bərabər olan 396 00:14:56,010 --> 00:14:57,430 biz oynayırıq ki, array əvvəllər ilə. 397 00:14:57,430 --> 00:14:59,470 Və mən səbəblərdən yeddi seçdi olacaq, yalnız 398 00:14:59,470 --> 00:15:00,840 bir az rahat. 399 00:15:00,840 --> 00:15:04,400 Və mən ilk təklif gidiyorum ki, biz bu yeddi könüllü Sıralama. 400 00:15:04,400 --> 00:15:06,786 Siz ilk istəyirsinizsə baxmayaraq salam. demək 401 00:15:06,786 --> 00:15:08,970 Bu olacaq-ci ildən yöndəmsiz bir neçə dəqiqə. 402 00:15:08,970 --> 00:15:10,370 Özünüzü tətbiq edilməsi. 403 00:15:10,370 --> 00:15:10,980 >> GRACE: Salam, mən Grace edirəm. 404 00:15:10,980 --> 00:15:14,190 Mən Leverett House bir sophomore edirəm. 405 00:15:14,190 --> 00:15:14,620 >> BRANSON: Salam. 406 00:15:14,620 --> 00:15:15,620 Mən Branson edirəm. 407 00:15:15,620 --> 00:15:16,920 Mən Weld bir birinci oldum. 408 00:15:16,920 --> 00:15:19,755 409 00:15:19,755 --> 00:15:20,230 >> Gabe: Salam. 410 00:15:20,230 --> 00:15:21,040 Mən Gabe edirəm. 411 00:15:21,040 --> 00:15:22,300 Mən Cabot kiçik edirəm. 412 00:15:22,300 --> 00:15:24,826 413 00:15:24,826 --> 00:15:25,980 >> NEIL: Mən Neil edirəm. 414 00:15:25,980 --> 00:15:29,090 Mən Matthews bir birinci oldum. 415 00:15:29,090 --> 00:15:29,550 >> JASON: Mən Jason edirəm. 416 00:15:29,550 --> 00:15:32,816 Mən Greenough bir birinci oldum. 417 00:15:32,816 --> 00:15:33,700 >> MIKE: Mən Mike edirəm. 418 00:15:33,700 --> 00:15:37,360 Mən Grays bir birinci oldum. 419 00:15:37,360 --> 00:15:37,990 >> Jess: Mən Jess edirəm. 420 00:15:37,990 --> 00:15:40,313 Mən Leverett bir sophomore edirəm. 421 00:15:40,313 --> 00:15:41,300 >> DAVID J. Malan: Əla. 422 00:15:41,300 --> 00:15:41,850 Bütün hüquqlar. 423 00:15:41,850 --> 00:15:44,190 Yaxşı, bizim bütün təşəkkür edirik İndiyədək burada könüllü. 424 00:15:44,190 --> 00:15:47,110 Və əl-da problem indi gedir Bu uşaqlar düzmək üçün ola bilər, lakin sonra 425 00:15:47,110 --> 00:15:50,250 biz bir az düşünmək lazımdır olacaq necə səmərəli Biz, həqiqətən, haqqında ağır 426 00:15:50,250 --> 00:15:51,110 onlara çeşidlənir. 427 00:15:51,110 --> 00:15:52,580 Belə ki, ilk bu cəhd edək. 428 00:15:52,580 --> 00:15:55,970 Siz uşaqlar bir-birinin nömrələri görə bilərsiniz yalnız guşələrindən ətrafında yerləşdirilməsi ilə. 429 00:15:55,970 --> 00:15:59,380 Irəli getmək və bir neçə saniyə almaq və Sıralama kiçik üzərində edin 430 00:15:59,380 --> 00:16:01,240 doğru ən böyük qalmadı. 431 00:16:01,240 --> 00:16:02,490 Gedin. 432 00:16:02,490 --> 00:16:07,010 433 00:16:07,010 --> 00:16:07,530 >> OK. 434 00:16:07,530 --> 00:16:08,030 Yaxşı. 435 00:16:08,030 --> 00:16:09,370 Ki, həqiqətən darn sürətli idi. 436 00:16:09,370 --> 00:16:14,040 İndi burada kimsə alqoritmi nə idi Bu uşaqlar tətbiq ki? 437 00:16:14,040 --> 00:16:14,900 >> HOPARLÖR 1: böyük ən. 438 00:16:14,900 --> 00:16:15,000 >> DAVID J. Malan: OK. 439 00:16:15,000 --> 00:16:18,070 Böyük ən az həqiqətən növ edir obyektiv, amma ki əmin deyiləm 440 00:16:18,070 --> 00:16:18,890 həqiqətən bir alqoritmi. 441 00:16:18,890 --> 00:16:21,810 Böyük ən az demək deyil Mənə nə addım-addım. 442 00:16:21,810 --> 00:16:22,833 Bəli? 443 00:16:22,833 --> 00:16:24,083 >> HOPARLÖR 1: [işitilemez] 444 00:16:24,083 --> 00:16:26,010 445 00:16:26,010 --> 00:16:26,280 >> DAVID J. Malan: OK. 446 00:16:26,280 --> 00:16:28,920 Sizdən daha bir şəxs kiçik görmək Belə ki, əgər Nömrənizi, sonra hərəkət 447 00:16:28,920 --> 00:16:29,680 onların hüququ. 448 00:16:29,680 --> 00:16:32,800 Belə ki, indi daha ifadəli əldə daha alqoritmi kimi, çünki 449 00:16:32,800 --> 00:16:35,410 o, bu halda, demək olar. 450 00:16:35,410 --> 00:16:37,050 Beləliklə, biz bir növ var şərti tikinti. 451 00:16:37,050 --> 00:16:39,700 Və bu uşaqlar ki, bir neçə etmək görünürdü dəfə, siz bəzi bir az köçürülüb, çünki 452 00:16:39,700 --> 00:16:40,420 bir məsafə. 453 00:16:40,420 --> 00:16:43,410 Belə ki, ehtimalla bir növ var idi onların şüurunda gedən loop. 454 00:16:43,410 --> 00:16:44,610 >> Amma o rəsmiləşdirmək üçün cəhd edək. 455 00:16:44,610 --> 00:16:47,540 Uşaqlar geri sıfırlamak bilər bu tənzimləmə üçün. 456 00:16:47,540 --> 00:16:50,650 Biz bu rəsmiləşdirmək mümkün olmadıqda, Gəlin baxın bit, və sonra sual, yalnız 457 00:16:50,650 --> 00:16:51,580 Bu necə səmərəli edir? 458 00:16:51,580 --> 00:16:54,220 Əlbəttə, biz çox yavaş-yavaş bu nə zaman, bu kimi yaxşı hiss olacaq 459 00:16:54,220 --> 00:16:57,210 alqoritm, lakin nin görək biz əgər dəqiq addımlar bizim barmaqlarını qoymaq. 460 00:16:57,210 --> 00:16:58,670 >> Belə ki, iki uşaqlar dörd və iki edir. 461 00:16:58,670 --> 00:17:01,020 Və ya doğru və ya yanlış qaydada? 462 00:17:01,020 --> 00:17:01,900 Aydındır səhvdir. 463 00:17:01,900 --> 00:17:02,710 Beləliklə, biz dəyişdirildikdə. 464 00:17:02,710 --> 00:17:05,170 İndi kənara hərəkət etmək gidiyorum burada dörd altı, deyirlər. 465 00:17:05,170 --> 00:17:06,240 Əgər doğru və ya yanlış edirsiniz? 466 00:17:06,240 --> 00:17:06,599 >> Gabe: Doğru. 467 00:17:06,599 --> 00:17:07,180 >> DAVID J. Malan: Doğru. 468 00:17:07,180 --> 00:17:08,300 Altı və bir? 469 00:17:08,300 --> 00:17:08,609 Xeyr. 470 00:17:08,609 --> 00:17:09,630 Swap. 471 00:17:09,630 --> 00:17:10,490 Belə ki, iki svop var. 472 00:17:10,490 --> 00:17:11,710 Altı və üç? 473 00:17:11,710 --> 00:17:11,980 Xeyr. 474 00:17:11,980 --> 00:17:13,000 Swap. 475 00:17:13,000 --> 00:17:13,930 Altı və yeddi? 476 00:17:13,930 --> 00:17:14,630 Yaxşı görünür. 477 00:17:14,630 --> 00:17:15,396 Yeddi və beş? 478 00:17:15,396 --> 00:17:16,150 >> Jess: [işitilemez] 479 00:17:16,150 --> 00:17:17,089 >> DAVID J. Malan: OK, dəyişdirmək. 480 00:17:17,089 --> 00:17:19,770 Və çeşidlənir. 481 00:17:19,770 --> 00:17:19,980 Bütün hüquqlar. 482 00:17:19,980 --> 00:17:21,440 Belə ki, açıq-aydın deyil, sağ? 483 00:17:21,440 --> 00:17:22,470 Belə ki, daha orada gedirdi. 484 00:17:22,470 --> 00:17:24,920 Lakin, həqiqətən, bu uşaqlar, hətta yalnız qeyri-iradi. 485 00:17:24,920 --> 00:17:25,450 hərəkət saxlanılır. 486 00:17:25,450 --> 00:17:27,710 Onlar yalnız bir dəfə, dayanmadı onlar bir problem düzəldilməlidir. 487 00:17:27,710 --> 00:17:27,839 Belə ki. 488 00:17:27,839 --> 00:17:29,390 Həqiqətən, Mən gedirəm eyni şey. 489 00:17:29,390 --> 00:17:32,720 Mən geri geri düzmək üçün gidiyorum Bu problemin əvvəlinə, 490 00:17:32,720 --> 00:17:35,630 və ya bu sıra əvvəlində insanlar, onlara zəng başlamaq edək. 491 00:17:35,630 --> 00:17:38,366 >> İndi nə olmalıdır mənim alqoritmi ikinci pass olmaq? 492 00:17:38,366 --> 00:17:39,220 >> HOPARLÖR 1: eyni şey. 493 00:17:39,220 --> 00:17:39,940 >> DAVID J. Malan: eyni şey. 494 00:17:39,940 --> 00:17:41,460 Və bu, mən sağ, istəyirəm baþlýyorum? 495 00:17:41,460 --> 00:17:44,720 Özünüz bunu tapa bilərsiniz tezliklə eyni şey təkrar, var 496 00:17:44,720 --> 00:17:47,890 daha alqoritmi kimi olmaq və daha az insan instinkt. 497 00:17:47,890 --> 00:17:48,680 >> Belə ki, indi, burada biz yenə getmək. 498 00:17:48,680 --> 00:17:49,870 Iki və dörd? 499 00:17:49,870 --> 00:17:50,220 No 500 00:17:50,220 --> 00:17:51,050 Dörd və bir? 501 00:17:51,050 --> 00:17:53,380 Ah, bəzi həqiqətən var idi ediləcək hələ çalışır. 502 00:17:53,380 --> 00:17:53,620 Üçün üç? 503 00:17:53,620 --> 00:17:54,572 Yaxşı. 504 00:17:54,572 --> 00:17:56,000 Dörd və altı? 505 00:17:56,000 --> 00:17:58,380 Altı və beş? 506 00:17:58,380 --> 00:17:59,470 Altı və yeddi? 507 00:17:59,470 --> 00:18:00,970 OK, indi aparılır. 508 00:18:00,970 --> 00:18:01,550 OK, no. 509 00:18:01,550 --> 00:18:02,710 Mən geri getmək üçün var. 510 00:18:02,710 --> 00:18:05,130 >> Belə ki, indi yenə biz bu yapýyorsun bir az daha qəsdən. 511 00:18:05,130 --> 00:18:08,700 İndi, yalnız bir beyin var Bu alqoritm həyata. 512 00:18:08,700 --> 00:18:10,290 Bir CPU, Siz. 513 00:18:10,290 --> 00:18:13,090 Və səmimi, yeganə mənbə var biz imkanına malik olacaq. 514 00:18:13,090 --> 00:18:16,280 Və bir dəfə biz klaviatura geri yoxdur və C kimi bir şey 515 00:18:16,280 --> 00:18:19,600 atılması, biz yalnız bir proqram yazıyorsanız ki, bir zaman bir şey edə bilərsiniz. 516 00:18:19,600 --> 00:18:22,900 Bir an əvvəl bu uşaqlar Halbuki, biz kullanılarak geliştirilebiliyor onların kollektiv brainpower 517 00:18:22,900 --> 00:18:24,180 uşaqlar həftə sıfır ilə nə kimi. 518 00:18:24,180 --> 00:18:24,980 Belə ki, bunu davam edək. 519 00:18:24,980 --> 00:18:26,260 >> İki və bir. 520 00:18:26,260 --> 00:18:26,945 Iki və üç. 521 00:18:26,945 --> 00:18:27,460 Üç və dörd. 522 00:18:27,460 --> 00:18:28,310 Dörd və beş. 523 00:18:28,310 --> 00:18:28,620 Beş və altı. 524 00:18:28,620 --> 00:18:30,510 Altı və yeddi. 525 00:18:30,510 --> 00:18:31,880 Bitti? 526 00:18:31,880 --> 00:18:34,560 Beləliklə, mən deyiləm, lakin mənə oynamaq edək Şeytanın vəkili. 527 00:18:34,560 --> 00:18:37,950 Mən, kompüter Sıralama olan yalnız Bu array vasitəsilə ötürmə etdi 528 00:18:37,950 --> 00:18:40,225 insanlar, mən bitirdim ki, bilirsinizmi? 529 00:18:40,225 --> 00:18:40,670 >> HOPARLÖR 1: Xeyr 530 00:18:40,670 --> 00:18:41,050 >> DAVID J. Malan: Belə ki, niyə? 531 00:18:41,050 --> 00:18:46,900 Mən üçün nə etmək olardı Mən görülən edirəm ki, qəti qənaətə? 532 00:18:46,900 --> 00:18:48,230 Yəqin ki, daha bir keçir. 533 00:18:48,230 --> 00:18:48,430 Sağ? 534 00:18:48,430 --> 00:18:51,760 Çünki əvvəlki bilirik bütün pass bir səhv korrektə edir. 535 00:18:51,760 --> 00:18:53,920 Və o deməkdir ki, bəlkə var hələ də başqa səhv 536 00:18:53,920 --> 00:18:54,840 Mən düzəltmək lazımdır. 537 00:18:54,840 --> 00:18:58,680 Belə ki, mən yalnız rewinding ilə əmin ola bilər, bilər sonra, nəzarət bir-iki, iki və 538 00:18:58,680 --> 00:19:00,940 üç, üç və dörd, dörd və beş, beş və altı, altı və yeddi. 539 00:19:00,940 --> 00:19:02,510 OK, indi heç bir iş etdi. 540 00:19:02,510 --> 00:19:05,990 >> Mən, əlbəttə, Mən heç etdi ki, yadda bilər bir dəyişən kimi bir şey ilə işləmək 541 00:19:05,990 --> 00:19:06,975 bir int kimi. 542 00:19:06,975 --> 00:19:12,490 Bu svop zəng və svop bir dəfə 0 əgər burada almaq və sonra, 0 başladı 543 00:19:12,490 --> 00:19:15,520 Mən davam axmaq olardı geri və irəli, yenidən yoxlanılması və 544 00:19:15,520 --> 00:19:16,450 yenidən və yenidən, sağ? 545 00:19:16,450 --> 00:19:18,450 Bəzi ilə takılıyorum Çünki sonsuz loop növü. 546 00:19:18,450 --> 00:19:21,250 0 svop var Belə ki, tezliklə biz ki, bu tələb edə bilər 547 00:19:21,250 --> 00:19:23,810 alqoritm həqiqətən sona çatdı. 548 00:19:23,810 --> 00:19:25,400 >> İndi bu barədə bir ad qoymaq bildirin. 549 00:19:25,400 --> 00:19:28,930 Mən yalnız biz təklif alqoritmi bubble deyilən bir şey həyata keçirilir 550 00:19:28,930 --> 00:19:32,800 mənada kimi tanınan sort ki, böyük cür ki, nömrələri 551 00:19:32,800 --> 00:19:37,990 qədər üst bubble yol, və ya ədəd serialın sonuna. 552 00:19:37,990 --> 00:19:40,270 Amma bu alqoritm necə səmərəli oldu? 553 00:19:40,270 --> 00:19:44,600 Mən fiziki Neçə addımlar var idi Bu düzmək üçün, məsələn, almaq 554 00:19:44,600 --> 00:19:45,850 yeddi insanlar? 555 00:19:45,850 --> 00:19:48,560 556 00:19:48,560 --> 00:19:49,550 >> Dörd-beş? 557 00:19:49,550 --> 00:19:51,420 OK, çox sonda edir cavab olacaq. 558 00:19:51,420 --> 00:19:54,960 Lakin, sonra xüsusi sayı qədər maraqlı deyil. 559 00:19:54,960 --> 00:19:56,670 İT n kimi ümumiləşdirmək edək. 560 00:19:56,670 --> 00:20:00,520 Burada insanlar N, və onlar ki, əgər at təsadüfi qaydada növ idi 561 00:20:00,520 --> 00:20:02,180 ki, orijinal məqsədilə başlayan. 562 00:20:02,180 --> 00:20:04,910 Yaxşı, nə qədər addımlar var idi ilk pass almaq üçün? 563 00:20:04,910 --> 00:20:09,810 Bu, bir, iki, üç, dörd, beş idi belə altı, onlar yeddi nəfər istəyirik, 564 00:20:09,810 --> 00:20:13,670 ki, altı yeddi var -, n var, belə ki, minus bir ilk dəfə addımlar. 565 00:20:13,670 --> 00:20:16,280 >> İndi neçə addımlar var idi Mən rewound zaman etmək olar? 566 00:20:16,280 --> 00:20:19,310 Bəli, biz həqiqətən iki dəfə arta bilər ki, əgər biz, həqiqətən istəyirdim, amma indi üçün, Ben 567 00:20:19,310 --> 00:20:22,300 yalnız, bütün sağ demək gedir başqa n mənfi 1. 568 00:20:22,300 --> 00:20:25,240 Belə ki, n mənfi 1 almaq üçün gedir takip annoying, belə edək 569 00:20:25,240 --> 00:20:26,400 az up dəyirmi. 570 00:20:26,400 --> 00:20:27,770 Belə ki, 2n addımlar. 571 00:20:27,770 --> 00:20:29,310 Belə ki, 14 addımlar, vermək və ya almaq. 572 00:20:29,310 --> 00:20:31,930 >> Mən neçə dəfə almaq idi bir addım növbəti dəfə? 573 00:20:31,930 --> 00:20:33,740 Bəli, bu Zadaça 3n var. 574 00:20:33,740 --> 00:20:34,510 həqiqətən. 575 00:20:34,510 --> 00:20:37,920 İndi, ən pis halda, üçün Məsələn, neçə dəfə mən var ki, 576 00:20:37,920 --> 00:20:41,730 geri və irəli, geri və irəli getdi dəyişdirmə, bu alqoritm həyata 577 00:20:41,730 --> 00:20:44,620 hər pass insanların təxminən? 578 00:20:44,620 --> 00:20:47,720 579 00:20:47,720 --> 00:20:50,010 Bu, faktiki olaraq, sağ kvadrat n var? 580 00:20:50,010 --> 00:20:53,000 >> Ən pis halda, siz cür bilər, çünki daxilən bu barədə düşünürəm, 581 00:20:53,000 --> 00:20:54,800 bir az ola bilər, baxmayaraq ki, da batmağa vaxt bit 582 00:20:54,800 --> 00:20:57,590 Ən pis halda, hansı ki, bu yeddi adam kimi baxdı 583 00:20:57,590 --> 00:21:00,230 müqavilənin şərtləri onların nömrələri? 584 00:21:00,230 --> 00:21:01,460 Tamamilə geri, sağ? 585 00:21:01,460 --> 00:21:02,815 Və yalnız ki, biclik Adınızı yenidən nə idi? 586 00:21:02,815 --> 00:21:03,360 >> MIKE: Mike. 587 00:21:03,360 --> 00:21:03,640 >> DAVID J. Malan: Mike? 588 00:21:03,640 --> 00:21:08,100 OK, Mike, yalnız mənə artıq qoşula bilər burada yalnız bir ikinci üçün? 589 00:21:08,100 --> 00:21:08,880 Əslində, yox. 590 00:21:08,880 --> 00:21:10,150 Bağışlayın Mike, alaq geri. 591 00:21:10,150 --> 00:21:10,910 Adınız ne yenidən? 592 00:21:10,910 --> 00:21:11,180 >> NEIL: Neil. 593 00:21:11,180 --> 00:21:11,640 >> DAVID J. Malan: Neil. 594 00:21:11,640 --> 00:21:13,750 OK, Neil, siz ilə gəlmək mənim, sənin ağla deyil əgər. 595 00:21:13,750 --> 00:21:17,150 Beləliklə, mən yalnız təklif gidiyorum sadəlik ki, Neil onun indi 596 00:21:17,150 --> 00:21:18,510 ən pis halda mümkün. 597 00:21:18,510 --> 00:21:20,720 Amma həyata necə xatırlayıram mənim alqoritmi. 598 00:21:20,720 --> 00:21:24,530 Mən müqayisə müqayisə müqayisə alıram oh, müqayisə, müqayisə. 599 00:21:24,530 --> 00:21:26,640 İndi bu uşaqlar həyata sifariş, mən düzeltmek. 600 00:21:26,640 --> 00:21:27,980 Belə ki, uşaqlar Swap. 601 00:21:27,980 --> 00:21:31,630 Amma nə qədər uzaq, indi hesab Neil getmək var? 602 00:21:31,630 --> 00:21:32,690 Bu təxminən n oldu. 603 00:21:32,690 --> 00:21:33,570 Bilirsiniz, bu, həqiqətən n deyil. 604 00:21:33,570 --> 00:21:36,040 Bu kimi, n mənfi 1, amma alıram ki, az rahatsız saxlanması track 605 00:21:36,040 --> 00:21:37,550 sayı, elə yalnız N zəng edək. 606 00:21:37,550 --> 00:21:42,860 >> Neil maksimum bir addım hər hərəkət Belə ki, əgər vaxtı və Neil bir addım hərəkət etmək üçün, 607 00:21:42,860 --> 00:21:46,580 Mən bu həqiqətən yorucu pass etmək lazımdır geri və irəli, bu kobud deyil 608 00:21:46,580 --> 00:21:52,080 Bunu, n addımlar, n dəfə cəmi, mənə etmək niyyətindədir, çünki 609 00:21:52,080 --> 00:21:55,820 çox addımlar Neil bütün almaq üçün o aid olduğu yol. 610 00:21:55,820 --> 00:21:58,620 Başqa hər kəs tək edək uşaqlar əgər bütün yaxşı pis əmri verildi. 611 00:21:58,620 --> 00:22:01,100 >> Elə bubble sırala n kvadrat zəng edək. 612 00:22:01,100 --> 00:22:04,860 Bu alqoritm çalışan zaman, Bu alqoritm performans 613 00:22:04,860 --> 00:22:07,120 Bu alqoritm səmərəliliyi, biz daha çox təsvir edir 614 00:22:07,120 --> 00:22:08,800 n kvadrat ümumiyyətlə kimi. 615 00:22:08,800 --> 00:22:11,650 Mən bilər, çünki ki, gözəl deyil səkkiz nəfər, doqquz ilə eyni misal 616 00:22:11,650 --> 00:22:15,450 insanlar, bir milyon adam ki, cavab dəyişmək niyyətində deyil. 617 00:22:15,450 --> 00:22:18,870 >> Uşaqlar ağla deyil əgər Belə ki, edək Siz açılmış harada sizi yenidən. 618 00:22:18,870 --> 00:22:22,510 Və edək iki digər yanaşmalar cəhd biz əsaslı edə bilməz görmek 619 00:22:22,510 --> 00:22:23,820 Bu daha yaxşı. 620 00:22:23,820 --> 00:22:27,130 Bu dəfə Beləliklə, mən təklif etmək gidiyorum müxtəlif alqoritm bir növ. 621 00:22:27,130 --> 00:22:29,950 Ki, keçən dəfə bizdən çox ağıllı idi və uşaqlar üçün sağ idi 622 00:22:29,950 --> 00:22:32,470 yalnız növ sağ instinktlərdən pairwise dəyişdirmə edir. 623 00:22:32,470 --> 00:22:36,500 Amma həqiqətən bu yaxınlaşmaq istəyirdi sadəcə, mənim məqsədi hərəkət etmək 624 00:22:36,500 --> 00:22:39,800 kiçik nömrələr bütün bu yolu və ki, böyük nömrələr bütün təkan 625 00:22:39,800 --> 00:22:43,030 yol, niyə yalnız ki, yoxdur ən yolu mümkün sadəlövh və görmək əgər mən 626 00:22:43,030 --> 00:22:45,730 bir nə daha yaxşı edə bilərsiniz olduqca kompleks alqoritmi? 627 00:22:45,730 --> 00:22:46,620 >> Elə görək. 628 00:22:46,620 --> 00:22:48,940 Dörd olduqca az sayda, belə ki, mən orada an tərk edəcəyik. 629 00:22:48,940 --> 00:22:50,610 Ooh, sayı iki hətta daha yaxşıdır. 630 00:22:50,610 --> 00:22:52,230 Belə ki, yalnız irəli addım edə bilərsiniz bir an üçün? 631 00:22:52,230 --> 00:22:55,670 Bu, hazırda mənim kiçik nömrələnmiş namizəd, mən yadda gidiyorum 632 00:22:55,670 --> 00:22:57,000 ki, bir dəyişən kimi, ilə. 633 00:22:57,000 --> 00:22:57,930 Amma yoxlanılması saxlamaq üçün gedirəm. 634 00:22:57,930 --> 00:22:59,890 Olan kimsə var nömrə kiçik? 635 00:22:59,890 --> 00:23:00,460 Altı, no. 636 00:23:00,460 --> 00:23:01,390 Oh, yenə Neil var. 637 00:23:01,390 --> 00:23:04,050 >> Mən sizə geri itələmək üçün gidiyorum Sıralama konseptual edir. 638 00:23:04,050 --> 00:23:05,120 Neil irəli gələcək. 639 00:23:05,120 --> 00:23:08,440 İndi, mən dəyişən istifadə alıram ki, kiçik olan takip 640 00:23:08,440 --> 00:23:11,390 sayı üçün yenilənir Neil yer. 641 00:23:11,390 --> 00:23:12,110 Yaxşı, gəlin görək. 642 00:23:12,110 --> 00:23:13,960 Üç, yeddi, beş. 643 00:23:13,960 --> 00:23:15,590 OK, mən Neil kiçik idi. 644 00:23:15,590 --> 00:23:18,110 Sadə şey nədir Mənim üçün indi nə etməli? 645 00:23:18,110 --> 00:23:21,410 Mən yalnız mənim vaxt sərf etmək fikrində deyiləm sol Neil bir ləkə burda. 646 00:23:21,410 --> 00:23:25,350 Niyə yalnız Neil qoymaq deyil o aid, hansı yerləşir əlbəttə var? 647 00:23:25,350 --> 00:23:26,160 >> Əvvəlində bütün yol. 648 00:23:26,160 --> 00:23:27,720 Neil Belə ki, mənimlə gəlir. 649 00:23:27,720 --> 00:23:28,910 Və adı daha nə idi? 650 00:23:28,910 --> 00:23:29,310 >> GRACE: Grace. 651 00:23:29,310 --> 00:23:29,710 >> DAVID J. Malan: Grace. 652 00:23:29,710 --> 00:23:29,920 OK. 653 00:23:29,920 --> 00:23:32,490 Grace Belə ki, təəssüf ki, sen yolu cür. 654 00:23:32,490 --> 00:23:34,290 Belə ki, necə biz bu problemi həll edir? 655 00:23:34,290 --> 00:23:34,490 Sağ? 656 00:23:34,490 --> 00:23:37,500 Bu bir sıra deyil, var yalnız yeddi yer. 657 00:23:37,500 --> 00:23:40,830 Rob ilə Xatırladaq ki, biz danışdıq yaş elan və biz yalnız idi 658 00:23:40,830 --> 00:23:41,740 yaş məhdud sayı? 659 00:23:41,740 --> 00:23:42,535 Burada eyni fikri. 660 00:23:42,535 --> 00:23:44,300 Biz yalnız ints bir məhdud var. 661 00:23:44,300 --> 00:23:47,590 Grace bizim növ edir yol, biz necə düzeltirim? 662 00:23:47,590 --> 00:23:49,555 >> Ən sadə yolu kimi deyil Grace, sorry. 663 00:23:49,555 --> 00:23:51,870 Siz artıq getmək olacaq belə ki, biz var edə bilərsiniz. 664 00:23:51,870 --> 00:23:55,290 İndi, bəlkə bu barədə düşünüyorsanız Biz yalnız problem pis etdi. 665 00:23:55,290 --> 00:23:58,510 Və bəlkə biz nə, çünki Grace doğru yerdə idi? 666 00:23:58,510 --> 00:24:01,730 Amma biz o, çünki deyil bilirik başqa, o, olardı 667 00:24:01,730 --> 00:24:03,980 irəli daimi yerinə Bu zaman Neil, sağ? 668 00:24:03,980 --> 00:24:05,550 Biz artıq onun həyata yoxlanılır. 669 00:24:05,550 --> 00:24:05,770 >> Bütün hüquqlar. 670 00:24:05,770 --> 00:24:09,110 Belə ki, indi, Neil doğru yerdə var, Mən bir qədər optimallaşdırılması edə bilərsiniz. 671 00:24:09,110 --> 00:24:11,740 Növbəti dəqiqə, mən ignore gidiyorum Belə kimi birlikdə Neil bütün 672 00:24:11,740 --> 00:24:15,280 onun vaxt sərf, və ya təsadüfən səhv yerdə onu dəyişdirmək. 673 00:24:15,280 --> 00:24:17,805 Belə ki, indi, necə növbəti tapa bilərəm kiçik ki element? 674 00:24:17,805 --> 00:24:18,480 Iki. 675 00:24:18,480 --> 00:24:20,225 Əgər ki, çox yaxşı sıra Əgər irəli addım və istəyirəm 676 00:24:20,225 --> 00:24:21,100 Mən sizə yadda lazımdır. 677 00:24:21,100 --> 00:24:21,980 Altı, heç bir yaxşı. 678 00:24:21,980 --> 00:24:24,820 Dörd, üç, yeddi, beş, heç bir yaxşı. 679 00:24:24,820 --> 00:24:26,800 Beləliklə, siz məni hərəkət edək sağ yer. 680 00:24:26,800 --> 00:24:28,470 Və biz yalnız bu dəfə uğurlu var. 681 00:24:28,470 --> 00:24:31,350 >> İndi bu ignore gidiyorum iki uşaqlar, indi bir daha çox 682 00:24:31,350 --> 00:24:32,260 bu keçir. 683 00:24:32,260 --> 00:24:33,490 Altı ki, olduqca kiçik. 684 00:24:33,490 --> 00:24:34,300 Irəli Hadi. 685 00:24:34,300 --> 00:24:35,220 Oh, sorry. 686 00:24:35,220 --> 00:24:37,640 Grace nömrəsi, daha yaxşıdır belə irəli addım. 687 00:24:37,640 --> 00:24:38,260 Dörd. 688 00:24:38,260 --> 00:24:39,120 Bağışlayın, Grace. 689 00:24:39,120 --> 00:24:39,950 Yenidən geri gedin. 690 00:24:39,950 --> 00:24:41,550 Sayı üç yaxşıdır. 691 00:24:41,550 --> 00:24:42,290 Yeddi. 692 00:24:42,290 --> 00:24:42,720 Beş. 693 00:24:42,720 --> 00:24:43,550 İndi adınızı yenə nə var? 694 00:24:43,550 --> 00:24:44,000 >> JASON: Jason. 695 00:24:44,000 --> 00:24:44,420 >> DAVID J. Malan: Jason. 696 00:24:44,420 --> 00:24:47,050 Belə ki, Jason indi kiçik element mən seçtiniz. 697 00:24:47,050 --> 00:24:49,160 O hara gedir? 698 00:24:49,160 --> 00:24:50,380 Beləliklə, harada altı edir. 699 00:24:50,380 --> 00:24:51,210 Və adı yenə? 700 00:24:51,210 --> 00:24:51,710 >> Gabe: Gabe. 701 00:24:51,710 --> 00:24:52,340 >> DAVID J. Malan: Gabe. 702 00:24:52,340 --> 00:24:53,220 Gabe yolu var. 703 00:24:53,220 --> 00:24:54,640 Etmək asan şey nədir? 704 00:24:54,640 --> 00:24:58,390 Bu iki uşaqlar Swap və davam edir. 705 00:24:58,390 --> 00:24:59,020 Belə ki, indi görək. 706 00:24:59,020 --> 00:25:00,170 Kim kiçik var? 707 00:25:00,170 --> 00:25:01,030 Dörd. 708 00:25:01,030 --> 00:25:01,990 Mənə etmək yalnız cür edək. 709 00:25:01,990 --> 00:25:03,090 Beş kiçik olacaq. 710 00:25:03,090 --> 00:25:05,220 , Siz addım istəyirsinizsə mən növbəti tapmaq irəli, mən nə var 711 00:25:05,220 --> 00:25:06,820 Gabe bu uşaqlar? 712 00:25:06,820 --> 00:25:08,450 Daha Swap. 713 00:25:08,450 --> 00:25:10,740 Belə ki, indi, hələ bir qədər sifariş out. 714 00:25:10,740 --> 00:25:14,140 Mən Gabe ki, kiçik hesab Mən onu həyata pop uşaqlar üzərində hərəkət. 715 00:25:14,140 --> 00:25:15,190 Və etdik. 716 00:25:15,190 --> 00:25:17,200 >> Belə ki, cavab eyni. 717 00:25:17,200 --> 00:25:18,600 Son nəticə eynidir. 718 00:25:18,600 --> 00:25:22,730 Bu iki alqoritmlərin hansı daha yaxşıdır? 719 00:25:22,730 --> 00:25:23,500 İkinci, mən eşitdim. 720 00:25:23,500 --> 00:25:24,252 Niyə? 721 00:25:24,252 --> 00:25:25,900 >> HOPARLÖR 3: Bu addımlar [işitilemez] N oldu. 722 00:25:25,900 --> 00:25:27,600 >> DAVID J. Malan: Bu ən n addımlar var. 723 00:25:27,600 --> 00:25:28,490 Maraqlı. 724 00:25:28,490 --> 00:25:30,610 Belə ki, olsa? 725 00:25:30,610 --> 00:25:33,630 Belə ki, necə mən almısan kiçik element? 726 00:25:33,630 --> 00:25:37,060 Neçə addımlar mənim üçün idi Bu kiçik element tapmaq? 727 00:25:37,060 --> 00:25:39,220 Mən bütün yol baxmaq idi sonunda, sağ? 728 00:25:39,220 --> 00:25:41,530 Ki, ən pis halda, nə Çünki Neil burada olsaydı? 729 00:25:41,530 --> 00:25:45,700 Belə ki, yalnız ən kiçik element tapmaq Mənə n addımlar, və ya n mənfi 1 edir. 730 00:25:45,700 --> 00:25:46,100 Lakin, OK. 731 00:25:46,100 --> 00:25:46,980 Belə ki, Neil düzeltmek. 732 00:25:46,980 --> 00:25:48,740 , Bir dəqiqə və ya belə əvvəl unutmayın. 733 00:25:48,740 --> 00:25:51,680 >> Amma necə Mən növbəti almısan kiçik element? 734 00:25:51,680 --> 00:25:54,830 Bu n mənfi 1, və ya n minus həqiqətən 2, var addımların sayı. 735 00:25:54,830 --> 00:25:55,440 Belə ki, OK. 736 00:25:55,440 --> 00:25:57,390 Belə ki, I 2 minus n idi. 737 00:25:57,390 --> 00:25:57,600 Bütün hüquqlar. 738 00:25:57,600 --> 00:25:59,130 Belə ki, bir az daha yaxşı hiss edir. 739 00:25:59,130 --> 00:25:59,730 Bütün hüquqlar. 740 00:25:59,730 --> 00:26:03,270 Növbəti dəfə Neçə addımlar sayı üç tapmaq olar? 741 00:26:03,270 --> 00:26:04,420 Belə ki, n minus 4. 742 00:26:04,420 --> 00:26:07,670 Belə ki, bir az azalması oldu hər iteration addım. 743 00:26:07,670 --> 00:26:08,740 Beləliklə, bu, doğru daha yaxşı hiss etmir? 744 00:26:08,740 --> 00:26:13,450 Sonuncu dəfə isə, təxminən n dəfə n oldu bu dəfə n mənfi 1, üstəgəl n minus var 745 00:26:13,450 --> 00:26:16,500 2, üstəgəl n mənfi 3, üstəgəl n mənfi 4, nöqtə, nöqtə, nöqtə. 746 00:26:16,500 --> 00:26:18,750 Amma siz lisey geri əgər dərsliklər, kiçik fırıldaqçı 747 00:26:18,750 --> 00:26:24,380 düsturlar var ki, arxa hesabatı, əgər siz ədəd bu seriyası əlavə 748 00:26:24,380 --> 00:26:31,280 addımlar ümumi sayı nə Burada almaq olacaq? 749 00:26:31,280 --> 00:26:36,580 >> Bu, o biri kimi, n mənfi 1, 2 bölünür dəfə n. 750 00:26:36,580 --> 00:26:39,040 Beləliklə, mən çəkmək olar, əgər mənə görək yalnız bir an üçün bu qədər. 751 00:26:39,040 --> 00:26:42,230 Və yenə, mən yuvarlaqlaşdırma cür bəzi Ben ədəd yalnız bizim həyat sadə saxlamaq üçün 752 00:26:42,230 --> 00:26:47,830 amma xatırlayıram kimi, əgər belə bir şey var Mən sonra, n mənfi 1 şeylər n minus 753 00:26:47,830 --> 00:26:53,570 2, sonra n mənfi 3, bu təxminən var 2-dən artıq bu kimi bir şey, və əgər mən 754 00:26:53,570 --> 00:26:55,510 Bunu çoxaltmaq ki həqiqətən n kv. 755 00:26:55,510 --> 00:26:58,940 Bu çox yaxşı hiss deyil. 2-dən artıq n minus n. 756 00:26:58,940 --> 00:27:00,350 >> Amma burada bir şey var. 757 00:27:00,350 --> 00:27:03,720 Informatika, problemləri zaman n zaman maraqlı almaq üçün başlayın 758 00:27:03,720 --> 00:27:04,700 həqiqətən böyük olur. 759 00:27:04,700 --> 00:27:08,110 Və n həqiqətən böyük olur zaman, hansı bu dəyərləri bütün hakim gedir 760 00:27:08,110 --> 00:27:09,750 başqaları? 761 00:27:09,750 --> 00:27:10,990 Bu, sağ kvadrat n növü var? 762 00:27:10,990 --> 00:27:13,340 Bəli, 2 ayırıcı olduqca yaxşıdır. 763 00:27:13,340 --> 00:27:16,740 Amma milyardlarla bəhs edirsinizsə, məlumatların ədəd və ya trilyonlarca 764 00:27:16,740 --> 00:27:18,700 məlumatların ədəd, OK, belə ki, iki dəfə kimi sürətli istəyirik. 765 00:27:18,700 --> 00:27:22,440 Lakin, həqiqətən, böyük sayı əgər umurunda Bu amil olur nə varsa, 766 00:27:22,440 --> 00:27:23,040 daha böyük və daha böyük. 767 00:27:23,040 --> 00:27:25,990 Və şübhəsiz ki, bu, daha çox edir Bu adam daha fərq. 768 00:27:25,990 --> 00:27:29,120 Uşaqlar sağ belə baxmayaraq, ikinci alqoritm, biz zəng edəcəyik 769 00:27:29,120 --> 00:27:32,970 seçim sort, real dünyada, bir bit sürətli potensial, mən deyiləm, çünki 770 00:27:32,970 --> 00:27:35,360 alaraq daha az və az hər dəfə addımlar. 771 00:27:35,360 --> 00:27:37,340 >> Bu, həqiqətən əsaslı sürətli deyil. 772 00:27:37,340 --> 00:27:41,430 Çünki həqiqətən bu həyata oynamaq əgər sonunda n böyük dəyərlər, 773 00:27:41,430 --> 00:27:44,750 gün böyük kifayət n üçün, hələ də var olduqca yavaş hiss edəcəyik. 774 00:27:44,750 --> 00:27:46,770 Yaxşı, mənə bir qoy ki, son keçir. 775 00:27:46,770 --> 00:27:48,920 Mən zəng nə var seçim növ. 776 00:27:48,920 --> 00:27:51,040 Uşaqlar özünüzü yenidən qura bilərsiniz son bir dəfə? 777 00:27:51,040 --> 00:27:53,550 Və bu son halda, gedirəm nəyisə 778 00:27:53,550 --> 00:27:54,970 durub sırala çağırıb. 779 00:27:54,970 --> 00:27:57,470 Durub sort olan konseptual, bir az fərqli. 780 00:27:57,470 --> 00:28:00,980 >> Geri və irəli gedən və daha çox ən kiçik element seçilməsi, Ben 781 00:28:00,980 --> 00:28:05,030 yalnız bu hər biri ilə məşğul olacaqlar Mən onları qovuşana və Insert kimi uşaqlar 782 00:28:05,030 --> 00:28:06,850 onların düzgün yer daxil. 783 00:28:06,850 --> 00:28:10,160 Beləliklə, mən yalnız, Grace ilə başlamaq üçün gidiyorum və mən o dörd nömrəni ki, görürük. 784 00:28:10,160 --> 00:28:11,720 Sayı dörd harada aid edir? 785 00:28:11,720 --> 00:28:14,940 Mən bir şey çeşidlənməsi açılmış yoxdur belə Grace orada qalmaq olur. 786 00:28:14,940 --> 00:28:18,355 Siz ola bilər, əgər İndi, iddia gidiyorum Bu, doğru bir addım atmaq 787 00:28:18,355 --> 00:28:21,650 Mənim sorted siyahısı, bu mənim deyil, çeşidlənməmiş qalan siyahısı. 788 00:28:21,650 --> 00:28:23,260 Belə ki, indi mən gələn davam üçün gidiyorum və adı nə yenidən? 789 00:28:23,260 --> 00:28:23,700 >> BRANSON: Branson. 790 00:28:23,700 --> 00:28:24,150 >> DAVID J. Malan: Branson. 791 00:28:24,150 --> 00:28:25,375 Belə ki, Branson sayı iki. 792 00:28:25,375 --> 00:28:27,490 Beləliklə, mən sizi gidiyorum bir an üçün. 793 00:28:27,490 --> 00:28:30,940 İndi, siz məxsusdur Bu sıra? 794 00:28:30,940 --> 00:28:32,360 Belə ki, lütf sağ. 795 00:28:32,360 --> 00:28:35,670 Belə ki, yenə edilməsi cür istəyirik Grace burada bir çox iş yoxdur. 796 00:28:35,670 --> 00:28:37,290 Biz sizə harada qoymaq edirsiniz? 797 00:28:37,290 --> 00:28:40,120 Belə ki, biz sizə uçmaq olacaq sol və orada Branson daxil edin. 798 00:28:40,120 --> 00:28:41,680 Amma indi iddia edir ki, Uşaqlar edilir. 799 00:28:41,680 --> 00:28:43,240 Ancaq xəbərdarlıq, mən əlavə yer istifadə deyiləm. 800 00:28:43,240 --> 00:28:45,130 Bu hələ 2 elementləri var burada, buraya 5. 801 00:28:45,130 --> 00:28:47,910 Ümumi array ölçüsü 7, belə ki, mən bütün hüququ, aldadıcı deyil? 802 00:28:47,910 --> 00:28:51,950 >> Belə ki, indi biz, burada Gabe ilə var altı nömrəni, harada aid edirsiniz? 803 00:28:51,950 --> 00:28:52,650 Siz daha şanslı var. 804 00:28:52,650 --> 00:28:53,820 Belə ki, orada qalmaq almaq. 805 00:28:53,820 --> 00:28:57,210 Yalnız doğru bir kiçik addım atmaq yalnız sıralaması etdiyiniz aydın etmək. 806 00:28:57,210 --> 00:29:00,520 İndi biz yenə sayı Neil var bir, siz hara gedirik? 807 00:29:00,520 --> 00:29:03,540 Olduğunu görürük başlayacaq lazımdır və indi baxmayaraq ilk bu alqoritm, 808 00:29:03,540 --> 00:29:05,950 nəzər olduqca ağıllı hiss baxmaq baş haqqında budur. 809 00:29:05,950 --> 00:29:07,370 Əgər irəli addım bilər. 810 00:29:07,370 --> 00:29:09,260 >> Biz Neil qoymaq istəyirsiniz? 811 00:29:09,260 --> 00:29:11,830 Belə ki, açıq-aydın burada, belə ki, necə biz Neil alıram? 812 00:29:11,830 --> 00:29:12,970 Bu addım-addım edək. 813 00:29:12,970 --> 00:29:15,620 Siz getmək lazımdır harada Gabe? 814 00:29:15,620 --> 00:29:19,590 Yep, belə ki, böyük bir addım və ya iki yarım addımlar etmək 815 00:29:19,590 --> 00:29:20,820 orada bir addım. 816 00:29:20,820 --> 00:29:21,750 Siz getmək harada Grace? 817 00:29:21,750 --> 00:29:22,510 Yaxşı. 818 00:29:22,510 --> 00:29:23,500 Bir addım belə. 819 00:29:23,500 --> 00:29:24,960 Və nəhayət, Branson? 820 00:29:24,960 --> 00:29:25,460 Başqa bir addımdır. 821 00:29:25,460 --> 00:29:27,190 Və indi biz yer Neil qoya bilər. 822 00:29:27,190 --> 00:29:28,440 >> Belə ki, indi bu məntiqlə davam edir. 823 00:29:28,440 --> 00:29:32,420 Biz Neil dəyişkən deyil baxmayaraq üzərində və üzərində və onu qoymaq üçün 824 00:29:32,420 --> 00:29:36,420 O, ən pis halda, gedir ki, Biz qarşılaşa bilər növbəti sayı ola bilər 825 00:29:36,420 --> 00:29:42,220 sayı ola, demək, bir sıra var idi sıfır, sonra biz bütün keçmək olacaq 826 00:29:42,220 --> 00:29:42,730 Bu uşaqlar. 827 00:29:42,730 --> 00:29:44,950 Bir sıra mənfi var ki Güman bir, sonra biz keçmək lazımdır 828 00:29:44,950 --> 00:29:46,080 bu uşaqlar bütün. 829 00:29:46,080 --> 00:29:48,500 Beləliklə, biz həqiqətən Flipping yalnız cür istəyirik biz istəyirik ki ətrafında problem, 830 00:29:48,500 --> 00:29:52,620 olan hesabına köçürdükdən Seçim prosesi belə durub 831 00:29:52,620 --> 00:29:56,930 Uşaqlar yalnız idi ki, bu cür prosesi, təxminən n mənfi bir şey hərəkət etmək üçün 832 00:29:56,930 --> 00:29:57,940 addımlar sayı. 833 00:29:57,940 --> 00:30:01,200 Və addımlar ki sayı yalnız gedir Mən daha nömrələri seçmək kimi artırmaq, 834 00:30:01,200 --> 00:30:04,730 Mən sizə uşaqlar shoving saxlamaq lazımdır, əgər geri və geri və geri. 835 00:30:04,730 --> 00:30:08,320 >> Belə ki, kədərli şey indi bu bütün alqoritmləri kvadrat n. 836 00:30:08,320 --> 00:30:10,570 Gəlin irəli getmək və şükür bunların uşaqlar, və bu bir az görüntüləmək 837 00:30:10,570 --> 00:30:11,090 fərqli. 838 00:30:11,090 --> 00:30:12,312 Çox yaxşı. 839 00:30:12,312 --> 00:30:14,120 >> [Alqış] 840 00:30:14,120 --> 00:30:15,030 >> Bütün hüquqlar. 841 00:30:15,030 --> 00:30:16,280 Burada gedin. 842 00:30:16,280 --> 00:30:18,390 843 00:30:18,390 --> 00:30:18,470 Üçün təşəkkür edirik - 844 00:30:18,470 --> 00:30:19,190 >> BRANSON: [işitilemez] nömrələri saxlamaq. 845 00:30:19,190 --> 00:30:21,990 >> DAVID J. Malan: Xeyr, siz habelə nömrələri saxlamaq. 846 00:30:21,990 --> 00:30:23,440 Bütün hüquqlar. 847 00:30:23,440 --> 00:30:24,100 Qəşəng edilir. 848 00:30:24,100 --> 00:30:25,300 Bütün hüquqlar. 849 00:30:25,300 --> 00:30:30,510 Beləliklə, biz artıq yekunlaşdırmaq mümkün olmadıqda Bakalým daha sürətlə və daha çox vizual, 850 00:30:30,510 --> 00:30:33,410 dəqiq nə oldu Burada aşağıdakı kimi. 851 00:30:33,410 --> 00:30:36,510 852 00:30:36,510 --> 00:30:38,770 Mən irəli getmək gidiyorum və Firefox qədər çəkin. 853 00:30:38,770 --> 00:30:41,310 Biz bu nümayişin keçid olacaq Kursun saytında. 854 00:30:41,310 --> 00:30:43,870 Java iş almaq üçün bir az rahatsız edici deyil bəzi brauzerlərdə bu gün. 855 00:30:43,870 --> 00:30:46,760 Evdə bu ilə oynamaq yoxdur Belə ki, Firefox istifadə etmək lazımdır bilər həyata 856 00:30:46,760 --> 00:30:47,990 iş almaq üçün. 857 00:30:47,990 --> 00:30:50,440 Və nə mən bu ilə gedirəm nümayiş aşağıdakı kimidir. 858 00:30:50,440 --> 00:30:54,875 >> Altında, mən bütün dəstə var bir başlanğıc və o cümlədən menyu variantları, 859 00:30:54,875 --> 00:30:55,840 düyməsinə dayandırmaq. 860 00:30:55,840 --> 00:30:59,450 Həmçinin, bir kənara kimi, müşahidə bu proqramlara səhv, siz vasitəsi 861 00:30:59,450 --> 00:31:03,720 əslində başlanğıc və ya dayandırmaq bilməz sizə əmr və ya Alt Tut 'düyməsinə halda 862 00:31:03,720 --> 00:31:06,560 plus və zoom ilə, hansı işin daha çox düymələri göstərir. 863 00:31:06,560 --> 00:31:09,090 Oynamaq Belə Bilginize Bu evdə. 864 00:31:09,090 --> 00:31:12,870 İndi yalnız bir Start basın gidiyorum an, bir gecikme ifadə sonra, 865 00:31:12,870 --> 00:31:16,810 , burada 200 ms kimi yalnız belə ki, biz nə görürük. 866 00:31:16,810 --> 00:31:20,180 >> Beləliklə, mən bu vizual olduğunu iddia ilk alqoritm 867 00:31:20,180 --> 00:31:23,730 Bu uşaqlar bubble sort, vasitəsi etdi biz insanların cüt-müdrik dəyişdirildikdə. 868 00:31:23,730 --> 00:31:27,490 Bu görselleştirme üçün əsas fikir ki, bar boyu 869 00:31:27,490 --> 00:31:30,510 sayı ölçüsünü təmsil edir. 870 00:31:30,510 --> 00:31:32,210 Ki taller bar Belə ki, böyük nömrəsi. 871 00:31:32,210 --> 00:31:33,680 Qısa bar, sayı kiçik. 872 00:31:33,680 --> 00:31:38,630 Fark əgər, biz vasitəsilə olacaq Bu alqoritm ilk iteration, 873 00:31:38,630 --> 00:31:42,620 ki, böyük və kiçik ədəd dəyişdirmə kiçik sayı ilk və gəlir 874 00:31:42,620 --> 00:31:44,280 böyük sayı doğru gedir. 875 00:31:44,280 --> 00:31:48,770 >> Və tezliklə biz serialın sonuna almaq kimi yeddi-dən çox ədəd, biz istəyirik 876 00:31:48,770 --> 00:31:49,900 əvvəlinə geri gedir. 877 00:31:49,900 --> 00:31:51,140 Bu təxmin edirik. 878 00:31:51,140 --> 00:31:54,860 Uzaq sol, kiçik oğlan gedir yan dəyişdirmək, və bu 879 00:31:54,860 --> 00:31:56,010 prosesi təkrar. 880 00:31:56,010 --> 00:31:59,450 İndi bu vizual tez olur qazma, mənə davam və dayandırmaq bildirin 881 00:31:59,450 --> 00:32:04,170 bu, çox gecikmə bir şey dəyişmək daha sürətli, yalnız indi üçün bir fikir almaq üçün 882 00:32:04,170 --> 00:32:05,060 Bu alqoritmi. 883 00:32:05,060 --> 00:32:07,840 >> Mən bunu sürətləndi etdik Belə olsa da, bu alınması, mənim prosessor təkmilləşdirilməsi kimi 884 00:32:07,840 --> 00:32:08,580 yeni kompüter. 885 00:32:08,580 --> 00:32:12,980 Mən əsaslı dəyişməyib mənim alqoritm, ancaq həqiqətən daha çox edə bilərsiniz 886 00:32:12,980 --> 00:32:16,800 aydın insanlarla daha çox ki, böyük ədəd, üst qədər burda olunur 887 00:32:16,800 --> 00:32:20,900 və kiçik nömrələri burda olunur aşağı alt. 888 00:32:20,900 --> 00:32:22,390 İndi bu şey burada sıralanır. 889 00:32:22,390 --> 00:32:25,260 Və bir kənara kimi, meydanlarda var orada yalnız bir mühasibat 890 00:32:25,260 --> 00:32:28,010 , nə çox müqayisə saymaq kömək və ya neçə svopları var 891 00:32:28,010 --> 00:32:28,950 həqiqətən böyük işlər görülmüşdür. 892 00:32:28,950 --> 00:32:30,750 >> Yaxşı, biri edək digərləri gördük. 893 00:32:30,750 --> 00:32:37,116 Məni bura bubble sırala basın edək və Mənə seçin bildirin və bu, bütün web page 894 00:32:37,116 --> 00:32:38,936 bir az arabası var. 895 00:32:38,936 --> 00:32:41,155 Nin risk qəbul etsin və yenidən axır. 896 00:32:41,155 --> 00:32:44,560 897 00:32:44,560 --> 00:32:45,030 Orada biz gedin. 898 00:32:45,030 --> 00:32:47,180 Belə ki, seçim sort nə edək. 899 00:32:47,180 --> 00:32:49,140 Bilmirəm niyə menyu orada görünür. 900 00:32:49,140 --> 00:32:54,070 Ki, düzeltmek üçün bir-zoom edək bug, 50 dəyişdirə. 901 00:32:54,070 --> 00:32:56,020 Ah, həqiqətən nə edək çox daha sürətli edir. 902 00:32:56,020 --> 00:32:59,160 Beş ms və ya, və Başlat seçin. 903 00:32:59,160 --> 00:33:00,470 >> Belə ki, bu seçim sortudur. 904 00:33:00,470 --> 00:33:03,070 Belə ki, yenə nə haqqında düşünmək burada insanlar qədər idi. 905 00:33:03,070 --> 00:33:08,490 Biz serialın ilə getdi və seçilmiş daha kiçik element, 906 00:33:08,490 --> 00:33:09,250 və yenidən və yenidən. 907 00:33:09,250 --> 00:33:11,110 İndi mən hələ olduqca pis olduğunu iddia edirlər. 908 00:33:11,110 --> 00:33:15,010 Bu hələ kvadrat N edilib, vermək və ya almaq lakin bu bir az real dünyada idi, 909 00:33:15,010 --> 00:33:18,280 daha sürətli, Mən, həqiqətən, alaraq, çünki hər dəfə addımlar biraz az. 910 00:33:18,280 --> 00:33:19,800 Lakin biz yalnız nə söhbət edirik? 911 00:33:19,800 --> 00:33:21,830 Burada bəlkə 40 və ya belə barlar? 912 00:33:21,830 --> 00:33:23,200 Biz 40 milyon söhbət deyilik. 913 00:33:23,200 --> 00:33:27,430 Belə ki, tamamilə mənə aydın deyil ki, həqiqətən əhəmiyyətli bir gəlir idi. 914 00:33:27,430 --> 00:33:32,530 >> Mənə indi geri və dəyişdirmək edək seçin olan üçüncü alqoritmi, 915 00:33:32,530 --> 00:33:33,180 durub növ. 916 00:33:33,180 --> 00:33:36,380 İndi həqiqətən arabası var, çünki menyu həqiqətən orada olmamalıdır. 917 00:33:36,380 --> 00:33:40,840 Belə ki, indi biz burada geri hərəkət edəcəyik və bu alqoritm başlayın. 918 00:33:40,840 --> 00:33:43,270 Bağırtı, başlamaq və dayandırmaq. 919 00:33:43,270 --> 00:33:47,160 Belə ki, bu bir növ bir çox model var bu, qovuşdurmağımız yenə istəyirik 920 00:33:47,160 --> 00:33:50,240 insanların daxil, və ya Bu halda barlar daxil 921 00:33:50,240 --> 00:33:52,620 onların müvafiq yer. 922 00:33:52,620 --> 00:33:55,430 Və artıq əvvəl həyata Mən ətrafında çevrildi. 923 00:33:55,430 --> 00:33:58,940 Amma bu, çox, nəzəri, hələ kvadrat n. 924 00:33:58,940 --> 00:34:01,430 >> Beləliklə, biz ümumiləşdirmək mümkün olmadıqda Bakalým Bu aşağıdakı kimi. 925 00:34:01,430 --> 00:34:04,750 Mən irəli getmək və yalnız verəcəyəm söhbət ortaq bir yol bizə sort 926 00:34:04,750 --> 00:34:08,489 Bu şeyləri, mənə təqdim etsinlər burada notation yalnız bir bit. 927 00:34:08,489 --> 00:34:12,480 Siz böyük bir şey adlı görmək üzeresiniz O, sözün çünki böyük 928 00:34:12,480 --> 00:34:16,320 O. Bu bir kompüter bir yoldur alim və ya hətta istifadə edir riyaziyyatçı 929 00:34:16,320 --> 00:34:19,230 çalışan zaman təsvir etmək bəzi alqoritmi. 930 00:34:19,230 --> 00:34:21,400 Faktiki Kaç addımlar edir? 931 00:34:21,400 --> 00:34:25,080 >> İndi mən özümü xəcalətli gidiyorum burada yalnız bir anda mənim yazı. 932 00:34:25,080 --> 00:34:29,020 Amma mənə davam və deyirlər ki, qoy Bu burada böyük O olacaq. 933 00:34:29,020 --> 00:34:33,610 Və mənə bir başqa tətbiq edək simvolu kapital Omega. 934 00:34:33,610 --> 00:34:37,080 Omega, qarşı olacaq mahiyyətcə, böyük O Halbuki böyük O. üzrə 935 00:34:37,080 --> 00:34:40,790 vasitələri, ən pis halda, nə qədər vaxt bəzi alqoritmi ilə, bilər 936 00:34:40,790 --> 00:34:43,480 n baxımından, omega gedir nə qədər vaxt güc olmaq 937 00:34:43,480 --> 00:34:45,409 ən yaxşı halda edir. 938 00:34:45,409 --> 00:34:48,090 Və biz biz demək nə görürsünüz yalnız bir anda, ən yaxşı halda. 939 00:34:48,090 --> 00:34:49,940 >> Belə bir şey sadə başlamaq edək. 940 00:34:49,940 --> 00:34:54,719 Mənə bir xətti axtarışı ilə başlamaq edək. 941 00:34:54,719 --> 00:34:55,679 Belə ki, çeşidlənməsi deyil. 942 00:34:55,679 --> 00:34:58,000 Biz bu xətti axtarış arayacaðým. 943 00:34:58,000 --> 00:35:01,140 İndi bir az etmək Bu masa. 944 00:35:01,140 --> 00:35:06,600 İndi, xətti axtarış halda, ən pis halda, nə qədər addımlar 945 00:35:06,600 --> 00:35:11,770 bir tapmaq üçün mənə etmək niyyətindədir ixtiyari seçim sayı? 946 00:35:11,770 --> 00:35:14,540 Və N Toplam qapı var və ya n ümumi sayı. 947 00:35:14,540 --> 00:35:15,940 Ən pis halda. 948 00:35:15,940 --> 00:35:18,800 Neçə addımlar mən üçün gedirəm bir sıra sayı 50 tapmaq üçün almaq 949 00:35:18,800 --> 00:35:20,830 n Qapı? 950 00:35:20,830 --> 00:35:21,410 Və niyə? 951 00:35:21,410 --> 00:35:23,680 Bütün ola bilər, çünki sonunda üzərində üzərində yol. 952 00:35:23,680 --> 00:35:27,120 Jennifer rast O qədər çox kimi, sayı 50-belə, bütün yol üzərində idi 953 00:35:27,120 --> 00:35:30,760 ən pis halda xətti axtarış n böyük O, biz demək lazımdır olunur. 954 00:35:30,760 --> 00:35:33,430 >> Nə yaxşı halda haqqında həqiqətən xoşbəxt almaq əgər? 955 00:35:33,430 --> 00:35:36,200 Bu, sadəcə, bir addım olacaq addımlar və ya sabit bir sayı. 956 00:35:36,200 --> 00:35:37,830 Beləliklə, biz 1 kimi təsvir edəcəyik. 957 00:35:37,830 --> 00:35:39,010 Belə ki, bu olduqca yaxşıdır. 958 00:35:39,010 --> 00:35:41,210 İndi biz bir şey nə idi əgər binar axtarış istəyirsiniz? 959 00:35:41,210 --> 00:35:43,860 960 00:35:43,860 --> 00:35:47,846 Ən pis belə ikili axtarış , iş etdi nə qədər vaxt? 961 00:35:47,846 --> 00:35:49,250 >> [SƏSLƏRİ INTERPOSING] 962 00:35:49,250 --> 00:35:51,310 >> DAVID J. Malan: Belə ki, həqiqətən, mən bir neçə yerdə eşitdim. 963 00:35:51,310 --> 00:35:56,390 Belə ki, həqiqətən, n daxil olmaq və vermək və ya almaq oldu biz yarısında siyahısı bölmək çünki 964 00:35:56,390 --> 00:36:00,730 yenidən və yenidən və yenidən, biz edirik Nəticədə, tapmaq üçün, dəyəri, 965 00:36:00,730 --> 00:36:04,750 orada, ancaq bir kapsayan vardır. 966 00:36:04,750 --> 00:36:08,590 Biz ki, ehtimal nədir binar axtarış verilən almaq? 967 00:36:08,590 --> 00:36:09,700 Bu sıralanır var. 968 00:36:09,700 --> 00:36:12,770 Bu sorted deyil, siz şey ayıra bilərsiniz yeniden yarım, və 969 00:36:12,770 --> 00:36:15,490 tərk edə bilərsiniz və siz doğru getmək bilər, Siz sol və sağ getmək bilərsiniz, ancaq istəyirik 970 00:36:15,490 --> 00:36:18,070 element, əgər tapmaq niyyətində deyil siyahısı sorted deyil, çünki 971 00:36:18,070 --> 00:36:18,790 siz onu əldən bilər. 972 00:36:18,790 --> 00:36:22,120 Sizin Heuristic Çünki sol gedən üçün ya doğru əgər qüsurlu olacaq 973 00:36:22,120 --> 00:36:23,420 həqiqətən sorted deyil. 974 00:36:23,420 --> 00:36:26,110 Belə bir gizli dəyəri növ var bu kimi bir şey istifadə. 975 00:36:26,110 --> 00:36:29,250 >> İndi bizim çeşidlənməsi daxil bildirin alqoritmlər axtarış deyil - 976 00:36:29,250 --> 00:36:31,140 oh, həqiqətən bu boş gedək. 977 00:36:31,140 --> 00:36:33,190 Ən yaxşı halda İkili axtarış? 978 00:36:33,190 --> 00:36:36,290 Yalnız olmaq olur, əgər O, həmçinin 1-in çox serialın ortasında, və ya 979 00:36:36,290 --> 00:36:37,810 telefon kitab orta. 980 00:36:37,810 --> 00:36:39,710 İndi bubble sırala nə edək. 981 00:36:39,710 --> 00:36:42,570 Belə ki, daha, indi biz daxil edirik növ deyil, arar. 982 00:36:42,570 --> 00:36:47,220 >> Ən pis halda, nə çox addımlar idi biz iddia bubble sırala etmək olacaq? 983 00:36:47,220 --> 00:36:48,410 n kare. 984 00:36:48,410 --> 00:36:49,200 Beləliklə, mən ki, cəlb gedirəm. 985 00:36:49,200 --> 00:36:51,710 Ooh, mənim yazı daha pis görünür ki, böyük proqnozlaşdırılır zamanı. 986 00:36:51,710 --> 00:36:52,510 Bütün hüquqlar. 987 00:36:52,510 --> 00:36:53,570 Belə ki, kvadrat n oldu. 988 00:36:53,570 --> 00:36:59,460 Və bubble sırala ən yaxşı halda, neçə addımlar onu gedir? 989 00:36:59,460 --> 00:37:00,980 1, duydum. 990 00:37:00,980 --> 00:37:01,760 >> HOPARLÖR 1: n. 991 00:37:01,760 --> 00:37:03,286 >> DAVID J. Malan: n, duydum. 992 00:37:03,286 --> 00:37:04,200 >> HOPARLÖR 1: 2. 993 00:37:04,200 --> 00:37:05,010 >> DAVID J. Malan: 2, duydum. 994 00:37:05,010 --> 00:37:06,670 3 eşidirlərmi? 995 00:37:06,670 --> 00:37:07,080 Bütün hüquqlar. 996 00:37:07,080 --> 00:37:11,390 Beləliklə, mən n, 2, 1 eşitdim, amma seçin edək o ayrı ən azı ilk 997 00:37:11,390 --> 00:37:12,330 təkliflər, 1. 998 00:37:12,330 --> 00:37:15,370 Bu, çünki pis instinkt deyil cür burada bir model aşağıdakı. 999 00:37:15,370 --> 00:37:19,670 Amma bu, yalnız necə 1 addım sürsə dünya Mən iddia edə biləcək siyahısı 1000 00:37:19,670 --> 00:37:22,900 Mən yalnız icazə alıram, çünki, çeşidlənir 1 addım, neçə elementləri etmək 1001 00:37:22,900 --> 00:37:25,230 Mən, həqiqətən, kontrol bilər? 1002 00:37:25,230 --> 00:37:28,270 Bəli, yalnız 1, hansı n var deməkdir mənfi 1 elementləri ola həyata bilər 1003 00:37:28,270 --> 00:37:31,310 üçün, və yalnız sonra iman gedirəm 1 element baxaraq ki, 1004 00:37:31,310 --> 00:37:31,850 şey çeşidlənir. 1005 00:37:31,850 --> 00:37:33,930 Burada doğru deyil 1 belə. 1006 00:37:33,930 --> 00:37:35,710 Belə ki minimal, neçə Mən baxmaq var? 1007 00:37:35,710 --> 00:37:36,680 >> [SƏSLƏRİ INTERPOSING] 1008 00:37:36,680 --> 00:37:40,160 >> Həqiqətən n mənfi 1, və ya,: DAVID J. Malan n, hər baxmaq lazımdır, çünki 1009 00:37:40,160 --> 00:37:42,190 əmin olun element bu qaydada deyil. 1010 00:37:42,190 --> 00:37:44,750 Ancaq yenə də, biz dalğa bizim sort olacaq kiçik nömrələri əlləri və 1011 00:37:44,750 --> 00:37:47,100 n böyük olur kimi, onlar istəyirik, güman hər halda maraqsız. 1012 00:37:47,100 --> 00:37:48,380 Belə ki, bubble sırala var. 1013 00:37:48,380 --> 00:37:49,830 İndi, bu son iki nə edək. 1014 00:37:49,830 --> 00:37:53,520 Sonra seçim sort və biz edəcəyik durub sort yoxdur. 1015 00:37:53,520 --> 00:37:57,160 Və sonra biz əsəcək çox şey şüurunda 1016 00:37:57,160 --> 00:37:58,926 bütün bunlar daha yaxşı. 1017 00:37:58,926 --> 00:38:00,410 Bütün hüquqlar. 1018 00:38:00,410 --> 00:38:04,700 >> Çalışan ən pis halda nədir seçim növ vaxt? 1019 00:38:04,700 --> 00:38:05,680 >> HOPARLÖR 4: n kvadrat. 1020 00:38:05,680 --> 00:38:06,710 >> DAVID J. Malan: n kvadrat, mən eşitmə alıram. 1021 00:38:06,710 --> 00:38:09,790 Amma niyə n daxilən, kvadrat? 1022 00:38:09,790 --> 00:38:11,170 >> HOPARLÖR 4: biz yalnız Çünki. 1023 00:38:11,170 --> 00:38:12,260 >> DAVID J. Malan: biz yalnız Çünki. 1024 00:38:12,260 --> 00:38:12,550 OK. 1025 00:38:12,550 --> 00:38:13,380 Cavab Yaxşı. 1026 00:38:13,380 --> 00:38:16,660 Amma daxilən, niyə seçim deyil sort n kvadrat? 1027 00:38:16,660 --> 00:38:18,980 Biz nə oldu təkrar? 1028 00:38:18,980 --> 00:38:22,570 Biz vasitəsilə tarama saxlamaq idi Siz kiçik, siz var 1029 00:38:22,570 --> 00:38:24,020 kiçik, siz kiçik var. 1030 00:38:24,020 --> 00:38:27,480 Və verilmiş, biz n edə idi addımlar, sonra n sonra mənfi 1, n minus 2. 1031 00:38:27,480 --> 00:38:30,700 Amma cür bu bütün əlavə əgər, və ya əlavə etdiyiniz iman onu 1032 00:38:30,700 --> 00:38:34,810 əvvəlcədən onları, biz n qaba almaq bəzi kiçik ədəd minus kvadrat. 1033 00:38:34,810 --> 00:38:36,730 Mən bu n kvadrat zəng etmək üçün gedirəm. 1034 00:38:36,730 --> 00:38:39,530 Amma ən yaxşı seçim növ ilə halda, necə bir çox addımlar 1035 00:38:39,530 --> 00:38:40,632 Mənə etmək niyyətindədir? 1036 00:38:40,632 --> 00:38:41,840 >> HOPARLÖR 5: [işitilemez] 1037 00:38:41,840 --> 00:38:44,350 >> DAVID J. Malan: Bu təəssüf ki, var hələ n kare, sağ? 1038 00:38:44,350 --> 00:38:49,590 Mən kiçik seçilməsi alıram Çünki əgər element, və biz, burada yeddi nəfər idi 1039 00:38:49,590 --> 00:38:53,280 Mən yalnız bilirəm, bir dəfə mən çox almaq sonunda, ki, mən kiçik gördük 1040 00:38:53,280 --> 00:38:55,670 sayı, yerdə o və ya o ola bilər. 1041 00:38:55,670 --> 00:38:58,820 Amma necə Mən növbəti tapa bilərəm kiçik nömrə? 1042 00:38:58,820 --> 00:39:00,160 Başqa bir keçid var. 1043 00:39:00,160 --> 00:39:04,810 Belə ki, ən yaxşı halda, nə edir Seçim Sıralama girdi? 1044 00:39:04,810 --> 00:39:07,830 Bu artıq sort siyahısı, bir nömrəli var iki nömrəli, sayı üç, dörd nömrəni. 1045 00:39:07,830 --> 00:39:08,600 Amma bir kompüter edirəm. 1046 00:39:08,600 --> 00:39:10,190 Mən yalnız bir baxmaq olar bir anda şey. 1047 00:39:10,190 --> 00:39:12,465 Bir addım I sort bilməz geri bir insan və demək kimi, 1048 00:39:12,465 --> 00:39:14,030 ooh, bu doğru görünür. 1049 00:39:14,030 --> 00:39:17,580 >> Mən yalnız düzgün qərar ola bilər olan seçerek seçimi sırala 1050 00:39:17,580 --> 00:39:18,370 kiçik nömrəsi. 1051 00:39:18,370 --> 00:39:21,390 Amma bir nömrəli ilk tapmaq olsa da, Mən başqa bir şey bilmirəm, əgər 1052 00:39:21,390 --> 00:39:24,460 Mən olmayan digər nömrələri, bütün Mən Mən bir sıra təhvil olduğunuz bilirik ki, 1053 00:39:24,460 --> 00:39:27,930 olan arxasında qapı və ya bir sıra nömrələri, mən bir bilmək üçün yeganə yol 1054 00:39:27,930 --> 00:39:28,680 kiçik idi? 1055 00:39:28,680 --> 00:39:32,440 Mən burada bütün yol almaq və həyata varsa, lənətləmək, bir həqiqətən kiçik idi. 1056 00:39:32,440 --> 00:39:34,870 >> Amma necə sonra müəyyən yoxdur iki növbəti kiçik? 1057 00:39:34,870 --> 00:39:38,350 Eyni təsirsizlik edərək təkrar. 1058 00:39:38,350 --> 00:39:42,210 Belə ki, nəhayət, durub növ ilə, necə pis halda, 1059 00:39:42,210 --> 00:39:44,990 biz bunu həyata demək idi? 1060 00:39:44,990 --> 00:39:49,100 Bu da kvadrat n. 1061 00:39:49,100 --> 00:39:53,020 Və haqqında ən yaxşı halda ilə? 1062 00:39:53,020 --> 00:39:56,282 Biz cliffhanger kimi tərk edəcəyik. 1063 00:39:56,282 --> 00:40:00,090 Biz ki, boş növbəti dəfə doldurmaq lazımdır lakin ilk mənə təklif edək ki, biz 1064 00:40:00,090 --> 00:40:02,620 əsaslı daha yaxşı edə Bütün bunlar, bütün sağ? 1065 00:40:02,620 --> 00:40:05,220 >> Belə ki, özünüz üçün hesab edirəm ki, nə durub sort olacaq. 1066 00:40:05,220 --> 00:40:06,910 Yaxşı, ki, çox dramatik deyil Mən yalnız bir Ben çünki 1067 00:40:06,910 --> 00:40:08,970 ki, dəyişiklik gördüm. 1068 00:40:08,970 --> 00:40:09,620 Wow. 1069 00:40:09,620 --> 00:40:10,420 OK. 1070 00:40:10,420 --> 00:40:12,615 Belə ki, burada bir qədər var müxtəlif nümayiş. 1071 00:40:12,615 --> 00:40:16,580 Mən burada Yakınlaştırmak varsa, ki görürsünüz sol, biz də, bubble növ var 1072 00:40:16,580 --> 00:40:20,740 Biz seçilməsi növ var orta, və sağında, biz bir şey var, biz 1073 00:40:20,740 --> 00:40:23,380 hələ baxdı yoxdur Sıralama daxil çağırıb. 1074 00:40:23,380 --> 00:40:26,080 Amma biz olduğunuz nə hesab Bu gün indiyə qədər burada edir. 1075 00:40:26,080 --> 00:40:29,200 Jennifer ilk mərhələdə gündəmə gələn zaman, biz nömrələrin sıra yolu ilə getdi 1076 00:40:29,200 --> 00:40:33,750 yenidən və yenidən, xətti axtarış ilə, və biz böyük O, xətti çalışan zaman var 1077 00:40:33,750 --> 00:40:35,100 n, belə danışmaq. 1078 00:40:35,100 --> 00:40:41,000 >> Indi ilk həftəsində hesab zaman sinif, biz uçurum və fəth zaman, 1079 00:40:41,000 --> 00:40:43,740 və biz telefon kitab, qoparmaq idi və Gökhan, biz kollektiv 1080 00:40:43,740 --> 00:40:47,500 üçün olan kullanılarak geliştirilebiliyor əsas fikir, tərəfindən təkrar özünüzü təkrar 1081 00:40:47,500 --> 00:40:50,930 Elə-belə, atmaq, atmaq , atmaq problemin yarısı 1082 00:40:50,930 --> 00:40:55,320 Ümumiyyətlə, yarım bir problem ayırıcı, və sonra kiçik parça müalicə 1083 00:40:55,320 --> 00:40:59,630 konseptual ekvivalent kimi problem başqa, biz birtəhər etdi 1084 00:40:59,630 --> 00:41:00,910 əsaslı yaxşı. 1085 00:41:00,910 --> 00:41:04,720 Amma bubble sırala ilə, seçim sort, durub növ ilə, biz var ola bilər 1086 00:41:04,720 --> 00:41:06,560 Jennifer ki belə faydalıdır. 1087 00:41:06,560 --> 00:41:10,220 Biz olduqca çox yalnız geri getdi və irəli bütövlükdə dəfə dəstə və biz 1088 00:41:10,220 --> 00:41:12,650 tweaked şeyi bir az bit, dəyişdirmə Bu üçün, bəlkə 1089 00:41:12,650 --> 00:41:13,730 daxil və ya seçib. 1090 00:41:13,730 --> 00:41:16,950 Lakin günün sonunda, bir çox idi yöndəmsiz gəzinti geri və irəli. 1091 00:41:16,950 --> 00:41:21,160 Biz, həqiqətən, leverage bir şey vermədi Jennifer kimi smart bölünməsi kimi etdi 1092 00:41:21,160 --> 00:41:22,040 və fəth. 1093 00:41:22,040 --> 00:41:25,620 >> Belə növ birləşməsi, əksinə, hansı Gələn həftə qədər görmək olmaz, o gedir 1094 00:41:25,620 --> 00:41:29,540 leverage bölməklə əsas ideya giriş, sonra halving, sonra 1095 00:41:29,540 --> 00:41:30,580 halving, sonra halving. 1096 00:41:30,580 --> 00:41:34,590 Və loop hər iteration üzrə sol yarım çeşidlənməsi və sağ 1097 00:41:34,590 --> 00:41:38,200 yarım, sol yarısı sol yarısı, sonra sonra sol və sağ yarım, 1098 00:41:38,200 --> 00:41:40,990 sol sağ yarısı yarısı və sağ yarım hüququ yarısı. 1099 00:41:40,990 --> 00:41:42,840 Və təkrar təkrar. 1100 00:41:42,840 --> 00:41:46,170 >> Belə ki, vizual görürük, lakin bu olacaq Gələn həftə bizi gözləyir budur. 1101 00:41:46,170 --> 00:41:49,760 Ümumiyyətlə, biz bir az düşünmək hər hansı belə problem az çətindir. 1102 00:41:49,760 --> 00:41:52,435 1103 00:41:52,435 --> 00:41:57,970 Biz sol kvadrat n, n var ortada kvadrat və n 1104 00:41:57,970 --> 00:41:59,400 sağ n daxil ol. 1105 00:41:59,400 --> 00:42:00,590 Belə ki, real cliffhanger var. 1106 00:42:00,590 --> 00:42:02,040 Biz bazar ertəsi görəcəksiniz. 1107 00:42:02,040 --> 00:42:05,163 >> [Alqış]