1 00:00:00,000 --> 00:00:00,990 2 00:00:00,990 --> 00:00:02,970 >> [MÜZİK OYUN] 3 00:00:02,970 --> 00:00:10,400 4 00:00:10,400 --> 00:00:12,550 >> DAVID J. MALAN: Bu CS50 olduğunu. 5 00:00:12,550 --> 00:00:14,612 Ve bu haftanın üç başlangıcıdır. 6 00:00:14,612 --> 00:00:16,820 Bu yüzden heyecanlı bir sürü var işler bugün kapsayacak. 7 00:00:16,820 --> 00:00:20,160 Fırsat bir sürü için sahneye gönüllü. 8 00:00:20,160 --> 00:00:22,780 Ve sonuçta, bugün değil kodu hakkında tüm. 9 00:00:22,780 --> 00:00:24,820 Ama bu fikirleri hakkında ve bu algoritmalar hakkında, 10 00:00:24,820 --> 00:00:28,420 ve aslında bazı geri getiren Haftanın sıfır öğrenilen dersler, 11 00:00:28,420 --> 00:00:31,910 burada hatırlama, biz bu ucubeyi tanıttı. 12 00:00:31,910 --> 00:00:33,880 Ve borçlanma ilham bundan başlatmak için 13 00:00:33,880 --> 00:00:36,879 her zamankinden daha karmaşık çözmek için algoritmik problemleri. 14 00:00:36,879 --> 00:00:38,420 Ama önce, duyurular bir çift. 15 00:00:38,420 --> 00:00:42,020 Yani bir, katılmak isterseniz Öğle yemeğinde CS50 personeli ve sınıf arkadaşları 16 00:00:42,020 --> 00:00:44,670 Bu Cuma hem burada ve Cambridge, New Haven, 17 00:00:44,670 --> 00:00:48,060 Tabii en adresini ziyaret edebilirsiniz Bir URL bulunabilir sitesi. 18 00:00:48,060 --> 00:00:50,390 Bu Çarşamba olacak Anlatım Sanders burada olmayacak. 19 00:00:50,390 --> 00:00:53,610 O yüzden sadece online olacak CS50 web sitesinde melodi, 20 00:00:53,610 --> 00:00:55,850 Burada Cambridge olsun veya New Haven de. 21 00:00:55,850 --> 00:00:58,110 >> Ve o zaman sorun iki set senin elinde zaten. 22 00:00:58,110 --> 00:01:03,067 Henüz daldı yoksa, bana izin sert ifadeli öneri sunmak 23 00:01:03,067 --> 00:01:05,150 Özellikle şimdi, olduğu gibi, bu Sorun, avans setleri 24 00:01:05,150 --> 00:01:08,669 Eğer gerçekten, şimdi değilse başlamak istiyorsun hafta sonu veya önce üzerinde biraz serpmek 25 00:01:08,669 --> 00:01:10,710 ilk dışarı çıktığınızda Cuma, sen olacak çünkü 26 00:01:10,710 --> 00:01:14,380 onlar mutlaka değiliz bulmak uzun veya daha zorlu başına elde 27 00:01:14,380 --> 00:01:14,950 se. 28 00:01:14,950 --> 00:01:17,575 Ben de, o bulacaksınız düşünüyorum Genel, onlar kabaca almak eğilimindedir 29 00:01:17,575 --> 00:01:18,892 zaman aynı miktarda etrafında. 30 00:01:18,892 --> 00:01:20,850 Ama kesinlikle bağlıdır öğrenci ve üzerinde 31 00:01:20,850 --> 00:01:22,880 anlayışla bağlıdır hangi ile yaklaşım. 32 00:01:22,880 --> 00:01:24,910 Ama her zaman, sen gidiyorsun Bazı duvara karşı çalıştırmak için, 33 00:01:24,910 --> 00:01:26,350 ve vurmak için gidiyoruz Bazı böcek, ve sen sadece 34 00:01:26,350 --> 00:01:27,950 muktedir olacak değil bir noktada bitti olsun. 35 00:01:27,950 --> 00:01:31,380 Ve bu muktedir derece değerli uzaklaşın ertesi gün geri gelmek için, 36 00:01:31,380 --> 00:01:35,286 Mesai saatleri gidin CS50 post tartışın veya benzeri aslında engellenmemiş olsun. 37 00:01:35,286 --> 00:01:36,160 Yani akılda tutmak. 38 00:01:36,160 --> 00:01:40,830 Mümkün olduğunca erken başlayan Yapabileceğiniz en iyi şey. 39 00:01:40,830 --> 00:01:44,160 Başladığımız yere Yani burada haftada sıfır üzerinde sınıf. 40 00:01:44,160 --> 00:01:47,441 Ve biz bir gönüllü alabilirim Burada bana mikrofon bulmanıza yardımcı olmak için? 41 00:01:47,441 --> 00:01:47,940 TAMAM. 42 00:01:47,940 --> 00:01:48,900 Zaten Ayakta. 43 00:01:48,900 --> 00:01:50,080 Yukarı gel. 44 00:01:50,080 --> 00:01:53,707 O işe gidiyor nasıl sanırım. 45 00:01:53,707 --> 00:01:54,415 Adın ne? 46 00:01:54,415 --> 00:01:55,570 ALAN ESTRADA: Alan Estrada. 47 00:01:55,570 --> 00:01:56,778 DAVID J. MALAN: Alan Estrada. 48 00:01:56,778 --> 00:01:57,910 Yukarı gel. 49 00:01:57,910 --> 00:01:58,619 Tanıştığımıza memnun oldum. 50 00:01:58,619 --> 00:01:59,910 ALAN ESTRADA: Nice to meet you. 51 00:01:59,910 --> 00:02:02,772 DAVID J. MALAN: Ve burada olduğunu Bize hafta sıfır, elbette sahip. 52 00:02:02,772 --> 00:02:03,028 ALAN ESTRADA: Ben. 53 00:02:03,028 --> 00:02:03,160 Ben ... idim. 54 00:02:03,160 --> 00:02:05,868 >> DAVID J. MALAN: Yani gidebiliriz önde ve Mike Smith bulmak bizim için, 55 00:02:05,868 --> 00:02:08,639 olabildiğince hızlı olarak? 56 00:02:08,639 --> 00:02:10,639 Mümkün olduğunca hızlı. 57 00:02:10,639 --> 00:02:13,756 Kelimenin tam anlamıyla sorunu yırtılma yarısında size ihtiyacınız olan. 58 00:02:13,756 --> 00:02:15,130 >> ALAN ESTRADA: Um. 59 00:02:15,130 --> 00:02:17,380 DAVID J. MALAN: Kelimenin tam anlamıyla yarısında sorunu yırtılma. 60 00:02:17,380 --> 00:02:20,210 61 00:02:20,210 --> 00:02:22,083 >> ALAN ESTRADA: Oh. 62 00:02:22,083 --> 00:02:22,583 Mm. 63 00:02:22,583 --> 00:02:23,300 Çok güzel. 64 00:02:23,300 --> 00:02:23,700 >> DAVID J. MALAN: Tamam. 65 00:02:23,700 --> 00:02:24,200 İyi. 66 00:02:24,200 --> 00:02:24,701 Teşekkür ederim. 67 00:02:24,701 --> 00:02:25,700 ALAN ESTRADA: Çok iyi. 68 00:02:25,700 --> 00:02:26,210 TAMAM. 69 00:02:26,210 --> 00:02:27,610 >> DAVID J. MALAN: Ve şimdi, Bunu whittled ettik 70 00:02:27,610 --> 00:02:29,320 Sorunun yarısı boyutuna. 71 00:02:29,320 --> 00:02:31,267 Şimdi, biz dörtte aşağı konum. 72 00:02:31,267 --> 00:02:33,475 Eğer dikkat ediyorsunuz biz tutuyor hangi tarafta? 73 00:02:33,475 --> 00:02:34,405 >> [Gülüyor] 74 00:02:34,405 --> 00:02:35,970 >> ALAN ESTRADA: Evet, bence-- 75 00:02:35,970 --> 00:02:37,594 >> DAVID J. MALAN: Ne bölümünde biz mi? 76 00:02:37,594 --> 00:02:39,150 ALAN ESTRADA: susturucular, yani. 77 00:02:39,150 --> 00:02:39,941 >> DAVID J. MALAN: Tamam. 78 00:02:39,941 --> 00:02:42,810 Ama Mike Smith gidiyor susturucuları sonra olmak. 79 00:02:42,810 --> 00:02:44,130 Yani-- 80 00:02:44,130 --> 00:02:48,180 >> [Gülüyor] 81 00:02:48,180 --> 00:02:48,742 >> Pekala. 82 00:02:48,742 --> 00:02:50,200 ALAN ESTRADA: Nereye bakıyorsun? 83 00:02:50,200 --> 00:02:52,049 DAVID J. MALAN: Mike Smith. 84 00:02:52,049 --> 00:02:53,090 ALAN ESTRADA: Mike Smith. 85 00:02:53,090 --> 00:02:54,760 DAVID J. MALAN: Şimdi, cerrahi konum. 86 00:02:54,760 --> 00:02:57,840 Şimdi doktorlar. 87 00:02:57,840 --> 00:02:58,340 Şimdi-- 88 00:02:58,340 --> 00:02:59,856 >> ALAN ESTRADA: en gerçek ile gidelim Let's-. 89 00:02:59,856 --> 00:03:00,370 Gerçek. 90 00:03:00,370 --> 00:03:00,970 >> DAVID J. MALAN: Gerçek. 91 00:03:00,970 --> 00:03:01,470 TAMAM. 92 00:03:01,470 --> 00:03:03,700 Eğer Real, gerekiyorsa. 93 00:03:03,700 --> 00:03:05,250 Şimdi, Mike Smith hangi tarafta? 94 00:03:05,250 --> 00:03:06,250 >> ALAN ESTRADA: Bu şekilde. 95 00:03:06,250 --> 00:03:07,333 >> DAVID J. MALAN: yol? 96 00:03:07,333 --> 00:03:08,240 ALAN ESTRADA: Bekleyin. 97 00:03:08,240 --> 00:03:08,790 M o-- değil mi? 98 00:03:08,790 --> 00:03:09,110 Biz Şarkı söylemeyi kes başladı 99 00:03:09,110 --> 00:03:10,090 >> DAVID J. MALAN: Evet. 100 00:03:10,090 --> 00:03:10,650 Onlar kalacaksın. 101 00:03:10,650 --> 00:03:11,430 Haklısın. 102 00:03:11,430 --> 00:03:11,710 >> ALAN ESTRADA: Evet. 103 00:03:11,710 --> 00:03:13,126 >> DAVID J. MALAN: Yani Ahmet'in burada. 104 00:03:13,126 --> 00:03:13,990 ALAN ESTRADA: ne olacak? 105 00:03:13,990 --> 00:03:14,665 >> [Gülüyor] 106 00:03:14,665 --> 00:03:17,365 107 00:03:17,365 --> 00:03:18,330 >> Kötü örnek, çocuklar. 108 00:03:18,330 --> 00:03:18,830 Özür dilerim. 109 00:03:18,830 --> 00:03:21,610 DAVID J. MALAN: Bu öğretecek Eğer sandalyeden sıçrama. 110 00:03:21,610 --> 00:03:22,318 >> ALAN ESTRADA: Oh. 111 00:03:22,318 --> 00:03:22,890 Ah. 112 00:03:22,890 --> 00:03:23,390 Anladım. 113 00:03:23,390 --> 00:03:24,670 Anladım. 114 00:03:24,670 --> 00:03:25,170 Ah. 115 00:03:25,170 --> 00:03:25,669 Ah. 116 00:03:25,669 --> 00:03:26,812 Bu Tamam bu--, seni aldım. 117 00:03:26,812 --> 00:03:27,520 Burada Smith? 118 00:03:27,520 --> 00:03:28,894 >> DAVID J. MALAN: Smith, teşekkür ederim. 119 00:03:28,894 --> 00:03:30,535 Yani Smith ararken devam edeceğiz? 120 00:03:30,535 --> 00:03:30,790 >> ALAN ESTRADA: Oh, evet. 121 00:03:30,790 --> 00:03:31,340 Hayır hayır Hayır. 122 00:03:31,340 --> 00:03:31,600 Oh hayır. 123 00:03:31,600 --> 00:03:31,940 Bu benim. 124 00:03:31,940 --> 00:03:32,580 >> DAVID J. MALAN: Oh, Smith var. 125 00:03:32,580 --> 00:03:33,415 TAMAM. 126 00:03:33,415 --> 00:03:34,040 >> ALAN ESTRADA: Evet, Burada Smith var. 127 00:03:34,040 --> 00:03:34,700 Üzgünüm beyler. 128 00:03:34,700 --> 00:03:35,860 Ben Michael-- düşündüm biz Michael aradılar. 129 00:03:35,860 --> 00:03:36,550 Özür dilerim. 130 00:03:36,550 --> 00:03:37,550 >> DAVID J. MALAN: Tamam. 131 00:03:37,550 --> 00:03:39,950 Pekala, şimdi sen paccini and Sons içine. 132 00:03:39,950 --> 00:03:41,242 >> ALAN ESTRADA: paccini ve oğulları. 133 00:03:41,242 --> 00:03:43,158 DAVID J. MALAN: Sadece sen ve ben bu konuda vardır. 134 00:03:43,158 --> 00:03:44,050 TAMAM. 135 00:03:44,050 --> 00:03:45,130 Bize Mike Smith. 136 00:03:45,130 --> 00:03:45,830 Smith. 137 00:03:45,830 --> 00:03:46,310 >> ALAN ESTRADA: Smith. 138 00:03:46,310 --> 00:03:46,750 >> DAVID J. MALAN: Smith. 139 00:03:46,750 --> 00:03:47,728 Biz Çöp R konum. 140 00:03:47,728 --> 00:03:48,644 ALAN ESTRADA: Berbat. 141 00:03:48,644 --> 00:03:50,096 Ah. 142 00:03:50,096 --> 00:03:52,480 Bu biraz zaman alacak. 143 00:03:52,480 --> 00:03:54,340 >> [Gülüyor] 144 00:03:54,340 --> 00:03:55,804 145 00:03:55,804 --> 00:03:56,720 DAVID J. MALAN: Ayakkabı. 146 00:03:56,720 --> 00:03:58,080 Biz ayakkabı konum. 147 00:03:58,080 --> 00:04:00,210 >> ALAN ESTRADA: Şimdi zaman-- ediyoruz 148 00:04:00,210 --> 00:04:01,105 >> DAVID J. MALAN: Nice. 149 00:04:01,105 --> 00:04:01,980 ALAN ESTRADA: hususların 150 00:04:01,980 --> 00:04:03,620 [Gülüyor] 151 00:04:03,620 --> 00:04:05,440 Ah, bu harika. 152 00:04:05,440 --> 00:04:06,910 [Gülüyor] 153 00:04:06,910 --> 00:04:08,380 154 00:04:08,380 --> 00:04:09,390 >> DAVID J. MALAN: Tamam. 155 00:04:09,390 --> 00:04:11,365 >> ALAN ESTRADA: Oh, bu iyi. 156 00:04:11,365 --> 00:04:14,425 Ben gidiyorum sanmıyorum Bundan sonra PSAT arkadaşları sahiptir. 157 00:04:14,425 --> 00:04:15,300 DAVID J. MALAN: İyi. 158 00:04:15,300 --> 00:04:16,078 Sporting. 159 00:04:16,078 --> 00:04:17,036 ALAN ESTRADA: Sporting. 160 00:04:17,036 --> 00:04:18,668 Aa, L, M, N, O, P 161 00:04:18,668 --> 00:04:19,459 DAVID J. MALAN: Tamam. 162 00:04:19,459 --> 00:04:21,600 Yani yarısında bu gözyaşı verelim. 163 00:04:21,600 --> 00:04:22,270 Tamam. 164 00:04:22,270 --> 00:04:25,606 Bu, zaten kötü biter Mike çünkü Smith sarı sayfalarda olmayacaktır. 165 00:04:25,606 --> 00:04:26,430 >> ALAN ESTRADA: Aw. 166 00:04:26,430 --> 00:04:27,140 >> DAVID J. MALAN: Hayır, sorun değil. 167 00:04:27,140 --> 00:04:28,930 Ama böyle farz edelim O bu sayfada var. 168 00:04:28,930 --> 00:04:33,260 Yani şimdi, aşağı sorunu whittled ettik bir sayfaya ve Mike Smith bulundu. 169 00:04:33,260 --> 00:04:35,180 >> [Tezahürat] 170 00:04:35,180 --> 00:04:35,757 171 00:04:35,757 --> 00:04:36,340 Tamam teşekkür ederim. 172 00:04:36,340 --> 00:04:40,700 173 00:04:40,700 --> 00:04:41,200 TAMAM. 174 00:04:41,200 --> 00:04:43,646 Bu olağanüstü oldu. 175 00:04:43,646 --> 00:04:45,954 Ama yine de daha hızlıydı doğrusal arama daha, 176 00:04:45,954 --> 00:04:47,870 burada biz başlar Kitabın başında, 177 00:04:47,870 --> 00:04:51,210 soldan sağa ve biz yolumuza hareket Sonunda Mike Smith arıyor. 178 00:04:51,210 --> 00:04:53,540 Ve böylece, eğer telefon rehberi belki 1000 sayfaları vardı 179 00:04:53,540 --> 00:04:56,300 belki almış olurdu Bize 10 ya da öylesine sayfa gözyaşları. 180 00:04:56,300 --> 00:04:59,380 >> Ama kaldıraçlı olabilir Bir varsayım dokundu 181 00:04:59,380 --> 00:05:03,602 Bütün bunlar sırasında, hangi söylemektir peşin telefon rehberi neydi o? 182 00:05:03,602 --> 00:05:04,310 HEDEF KİTLE: Sıralama. 183 00:05:04,310 --> 00:05:05,000 DAVID J. MALAN: Bu sıralanmış oluyor. 184 00:05:05,000 --> 00:05:05,160 Sağ? 185 00:05:05,160 --> 00:05:07,909 O yüzden alfabetik olarak sıralanmış Bu isimleri ve numaraları tüm 186 00:05:07,909 --> 00:05:11,230 A adlı ila sıralanır Z'nin, alfabetik arasında. 187 00:05:11,230 --> 00:05:13,100 Ama bugün, şimdi sormak soru, iyi, 188 00:05:13,100 --> 00:05:16,170 nasıl Verizon ya da telefon yaptım şirket bu duruma olsun? 189 00:05:16,170 --> 00:05:19,560 >> Bu bir şey çünkü kaldıraç Bu varsayım ve bu nedenle, 190 00:05:19,560 --> 00:05:22,570 Bir bir sorunu çözmek algoritması daha verimli. 191 00:05:22,570 --> 00:05:24,900 Ama biz asla gerçekten haftada sıfır sordu, iyi, 192 00:05:24,900 --> 00:05:27,790 Maliyet yaptım ne kadar Verizon veya bir başkası 193 00:05:27,790 --> 00:05:29,620 sıralı sırayla bu telefon rehberini almak için? 194 00:05:29,620 --> 00:05:29,780 >> Sağ? 195 00:05:29,780 --> 00:05:31,529 Bu ise önemli değil Mike Smith bakıyor 196 00:05:31,529 --> 00:05:35,190 Seni bir sürerse, süper hızlı yıl başlangıçta sayfaları sıralamak için. 197 00:05:35,190 --> 00:05:35,690 Sağ? 198 00:05:35,690 --> 00:05:38,620 Siz de sadece elemek olabilir randomize telefon defteri üzerinde, 199 00:05:38,620 --> 00:05:40,690 süper olacak eğer sıralamak için pahalı. 200 00:05:40,690 --> 00:05:42,350 Yani eğer biz başka gönüllü olabilir. 201 00:05:42,350 --> 00:05:46,350 En bir alacak olarak buraya bakalım Biz nasıl up-- hadi Bir-- nasıl 202 00:05:46,350 --> 00:05:48,100 bu sıralama hakkında gidebilir. 203 00:05:48,100 --> 00:05:51,990 >> Ve eğer Ürdün aslında olabilir Sahnede bizi buraya katılın. 204 00:05:51,990 --> 00:05:55,100 Sadece bir an için gel. 205 00:05:55,100 --> 00:05:56,359 Adın ne? 206 00:05:56,359 --> 00:05:57,150 CAROLINE: Caroline. 207 00:05:57,150 --> 00:05:58,691 DAVID J. MALAN: Caroline, yukarı gel. 208 00:05:58,691 --> 00:06:02,070 Ve katıldı olacak Burada benimle ve Ürdün tarafından. 209 00:06:02,070 --> 00:06:03,800 Caroline, teşekkür ederim. 210 00:06:03,800 --> 00:06:04,300 Pekala. 211 00:06:04,300 --> 00:06:08,330 Yani biz burada için ne Caroline 26 mavi kitaplar olduğunu 212 00:06:08,330 --> 00:06:10,747 FAS yönetmek için kullandığı Bazı final sınavları. 213 00:06:10,747 --> 00:06:13,330 Bunlar, bulmak zor alıyorsanız ama biz önceden yaptık 214 00:06:13,330 --> 00:06:15,800 biz birilerinin ismini koyduk olduğunu Bunların her birinin ön yüzünde, 215 00:06:15,800 --> 00:06:18,133 ama biz basit sakladım daha sonra tam isimlerini koyarak. 216 00:06:18,133 --> 00:06:22,720 Bu yüzden adı ile kişiyi vereceğini L, D, J, B, tüm yol Adan Zye, 217 00:06:22,720 --> 00:06:24,090 ama onlar rasgele sırada sensin. 218 00:06:24,090 --> 00:06:26,890 Ve sen-cekti eğer öyleyse, sizin yanınızdaki konuşuyor senin gibi sorunu ile yol 219 00:06:26,890 --> 00:06:31,620 o, sen devam edebilir yoktur ve A'dan Z'ye, bizim için bu sıralama 220 00:06:31,620 --> 00:06:34,070 >> HEDEF KİTLE: Tamam, bu yüzden L orta gibidir. 221 00:06:34,070 --> 00:06:35,050 C başlıyor. 222 00:06:35,050 --> 00:06:42,410 B. L. B öncesinde J, Q. 223 00:06:42,410 --> 00:06:45,140 >> DAVID J. MALAN: Tut bir saniye düşündü. 224 00:06:45,140 --> 00:06:48,910 Çünkü aksi takdirde, bu sadece Senin, benim, Ürdün ve ilginç. 225 00:06:48,910 --> 00:06:49,724 Oraya gidiyoruz. 226 00:06:49,724 --> 00:06:50,640 HEDEF KİTLE: [duyulamaz]. 227 00:06:50,640 --> 00:06:57,299 R. 228 00:06:57,299 --> 00:06:58,090 DAVID J. MALAN: Tamam. 229 00:06:58,090 --> 00:06:59,310 Napıyon? 230 00:06:59,310 --> 00:07:01,730 >> CAROLINE: M O. sonra gelir 231 00:07:01,730 --> 00:07:02,564 >> DAVID J. MALAN: Tamam. 232 00:07:02,564 --> 00:07:03,064 >> CAROLINE: O. 233 00:07:03,064 --> 00:07:04,120 DAVID J. MALAN: Ey, iyi. 234 00:07:04,120 --> 00:07:04,970 >> CAROLINE E. 235 00:07:04,970 --> 00:07:06,730 >> DAVID J. MALAN: E, F Evet. 236 00:07:06,730 --> 00:07:07,620 >> CAROLINE: T, U, V. 237 00:07:07,620 --> 00:07:10,689 >> DAVID J. MALAN: V, T, U, V o yüzden Eğer devam making-- konum gibi görünüyor. 238 00:07:10,689 --> 00:07:12,730 Eğer yapıyoruz gibi görünüyor Büyük bir kazık buraya, 239 00:07:12,730 --> 00:07:13,910 ve orada büyük bir yığın tür. 240 00:07:13,910 --> 00:07:16,230 Yani alfabenin ilk yarısı, alfabesinin ikinci yarısı. 241 00:07:16,230 --> 00:07:16,460 TAMAM. 242 00:07:16,460 --> 00:07:16,960 İyi. 243 00:07:16,960 --> 00:07:19,680 Tür ikisinde sorunu bölme. 244 00:07:19,680 --> 00:07:21,771 M, N, X. evet. 245 00:07:21,771 --> 00:07:22,270 CAROLINE: K. 246 00:07:22,270 --> 00:07:22,980 DAVID J. MALAN: Tamam. 247 00:07:22,980 --> 00:07:25,070 K. Yani bir tür seçerek ediyoruz birbiri ardına onları bir, 248 00:07:25,070 --> 00:07:27,620 Sol veya sağ ya koyarak, ya da Z adlı katta oluyor. 249 00:07:27,620 --> 00:07:28,012 TAMAM. 250 00:07:28,012 --> 00:07:29,190 >> CAROLINE: Z kat oluyor. 251 00:07:29,190 --> 00:07:29,360 >> DAVID J. MALAN: Tamam. 252 00:07:29,360 --> 00:07:30,920 Y katta oluyor. 253 00:07:30,920 --> 00:07:31,735 Şimdi X'i koyabilirsiniz 254 00:07:31,735 --> 00:07:32,409 >> CAROLINE: G. 255 00:07:32,409 --> 00:07:33,700 DAVID J. MALAN: G sol gidiyor. 256 00:07:33,700 --> 00:07:36,017 S doğru gidiyor. 257 00:07:36,017 --> 00:07:37,642 Pekala, bir sola tüm yol gidiyor. 258 00:07:37,642 --> 00:07:38,790 >> CAROLINE: A, B, C, D 259 00:07:38,790 --> 00:07:39,873 >> DAVID J. MALAN: Şimdi, iyi. 260 00:07:39,873 --> 00:07:43,260 Biz bir var, B, C W aşağı orada olacak. 261 00:07:43,260 --> 00:07:45,566 Pekala, T. 262 00:07:45,566 --> 00:07:46,611 >> CAROLINE: H, I, J 263 00:07:46,611 --> 00:07:47,860 DAVID J. MALAN: H, I, J iyi. 264 00:07:47,860 --> 00:07:49,160 CAROLINE: merkezinde, ben zaman-- ediyorum 265 00:07:49,160 --> 00:07:50,000 DAVID J. MALAN: Tamam. 266 00:07:50,000 --> 00:07:52,375 Yani şimdi, biz tür gidiyoruz Bu çeşitli yığınları birleştirmek. 267 00:07:52,375 --> 00:08:00,730 Yani A ile C arasındaki, o zaman ben D görüyorum ve E ve F, G ve H ve I güzel. 268 00:08:00,730 --> 00:08:05,540 J, K Ve sonra, bu kazık baş aşağı, ama bu sorun değil. 269 00:08:05,540 --> 00:08:06,040 Elbette. 270 00:08:06,040 --> 00:08:07,240 Biz bazı köşeleri kesebilir. 271 00:08:07,240 --> 00:08:07,950 TAMAM. 272 00:08:07,950 --> 00:08:10,530 Sonra W, X, Y, Z mi 273 00:08:10,530 --> 00:08:11,250 >> CAROLINE: Evet. 274 00:08:11,250 --> 00:08:11,880 >> DAVID J. MALAN: Mükemmel. 275 00:08:11,880 --> 00:08:14,122 Yani büyük bir teşekkür Bu sıralama için Caroline. 276 00:08:14,122 --> 00:08:15,030 >> [Tezahürat] 277 00:08:15,030 --> 00:08:17,287 >> Teşekkür ederim. 278 00:08:17,287 --> 00:08:18,120 Çok teşekkür ederim. 279 00:08:18,120 --> 00:08:22,910 Yani şimdi bir an için düşünelim nasıl Caroline yapıyor hakkında gitti, 280 00:08:22,910 --> 00:08:26,040 ve tam olarak ne biz nasıl ki-- başardık biz 281 00:08:26,040 --> 00:08:28,409 Bunu çözmek için başardık Sorun ne zaman biz sadece 282 00:08:28,409 --> 00:08:29,950 rasgele girdilerin bir sürü verilen. 283 00:08:29,950 --> 00:08:31,610 >> Peki, orada benziyor Orada bir sistemin biraz? 284 00:08:31,610 --> 00:08:32,110 Sağ. 285 00:08:32,110 --> 00:08:34,495 Önceki harf Yani alfabesinde, o 286 00:08:34,495 --> 00:08:37,120 oldu sola koyarak ve alfabede daha sonra harfler, 287 00:08:37,120 --> 00:08:38,270 O sağ içine koyarak. 288 00:08:38,270 --> 00:08:40,500 Ve en kısa sürede o buldum Bazı yakın mektuplar, olanları 289 00:08:40,500 --> 00:08:43,124 Bu, birbirine hemen yanında gitmek O sırada o koymak istiyorsunuz. 290 00:08:43,124 --> 00:08:46,750 Ve böylece biz tür bu küçük vardı meydana gelen sıralı girdilerin yığınları. 291 00:08:46,750 --> 00:08:50,540 >> Ve böylece oldukça ne demek Çoğumuz insanlar yapardı. 292 00:08:50,540 --> 00:08:53,530 Biz tür bunun aracılığıyla elemek istiyorum ve biz tür bir mekanizma olurdu. 293 00:08:53,530 --> 00:08:56,930 Ama yazmak zor olabilir aşağı bir formül haddi zatında. 294 00:08:56,930 --> 00:08:59,010 Bundan daha organik biraz daha hissettim. 295 00:08:59,010 --> 00:09:02,560 Yani görelim eğer bağlı şimdi can Daha az girişler sorun. 296 00:09:02,560 --> 00:09:05,170 >> Yerine 26, haydi daha az şeyler yapmak 297 00:09:05,170 --> 00:09:09,890 hemen arkasında, yedi, ile söylemek Bu kapılar, tabiri caizse. 298 00:09:09,890 --> 00:09:11,300 Sadece yedi sayı var mı? 299 00:09:11,300 --> 00:09:15,240 Ve şimdi hedef olarak ise El bir değeri bulmak için, 300 00:09:15,240 --> 00:09:17,850 Bakalım ne kadar etkin izin Biz bunu hakkında gidebilirsiniz. 301 00:09:17,850 --> 00:09:22,460 Ve şimdi eğer görelim Bazı sayılar uygulamak başlar, 302 00:09:22,460 --> 00:09:26,310 ya da bazı formüller hangi tanımlamak için Bizim telefon rehberinden etkinliği 303 00:09:26,310 --> 00:09:31,060 algoritma, bizim sınav kitap algoritması ve daha genel olarak, bilgi bulma. 304 00:09:31,060 --> 00:09:34,770 >> Bu Yani, beni ileriye gidelim ve dokunmatik ekranda buraya, 305 00:09:34,770 --> 00:09:41,100 sahip bir web tarayıcısı koymak Tam bu yedi kapı. 306 00:09:41,100 --> 00:09:46,670 Ve biz bir başka alabilir Buraya gelmek için gönüllü, 307 00:09:46,670 --> 00:09:48,480 Buraya bu aynı kapıları koyduk. 308 00:09:48,480 --> 00:09:49,170 Hızlı gönüllü. 309 00:09:49,170 --> 00:09:51,130 >> Bu Şehre demolar gidiyor daha hızlı ve daha hızlı şimdi. 310 00:09:51,130 --> 00:09:51,600 Aşağı gel. 311 00:09:51,600 --> 00:09:52,308 Adın ne? 312 00:09:52,308 --> 00:09:53,040 TREVOR: Trevor. 313 00:09:53,040 --> 00:09:53,998 >> DAVID J. MALAN: Trevor? 314 00:09:53,998 --> 00:09:55,770 Pekala, Trevor, aşağı gel. 315 00:09:55,770 --> 00:09:59,212 Yani Trevor burada gönüllü oldu benzer bir sorun, ama var bir tane 316 00:09:59,212 --> 00:10:02,170 kapsamında dar ve bu gidiyor izin Şimdi resmileştirmek için denemek için 317 00:10:02,170 --> 00:10:03,970 Bu numaraları sıralama işlemi. 318 00:10:03,970 --> 00:10:05,500 >> Yani Trevor, tanıştığımıza memnun oldum. 319 00:10:05,500 --> 00:10:08,720 Yani burada bir dizi çok olduğu yedi kapı listesini konuşuyoruz. 320 00:10:08,720 --> 00:10:10,327 Devam edin ve bize sayı 50 bulabilirsiniz. 321 00:10:10,327 --> 00:10:12,410 Ve sonra aslında sonra, Bunu nasıl bulduğunu bize bildirin. 322 00:10:12,410 --> 00:10:19,124 323 00:10:19,124 --> 00:10:20,040 Tamam göre-- etmelidir. 324 00:10:20,040 --> 00:10:21,945 Evet, burada bir mı? 325 00:10:21,945 --> 00:10:24,680 Ah ah. 326 00:10:24,680 --> 00:10:25,560 TAMAM. 327 00:10:25,560 --> 00:10:26,680 Bunu bir tıkladım. 328 00:10:26,680 --> 00:10:28,690 İyi. 329 00:10:28,690 --> 00:10:29,780 >> Ve iyi. 330 00:10:29,780 --> 00:10:30,970 Şimdi o bir tıkladım. 331 00:10:30,970 --> 00:10:34,060 Ve sana mikrofonu vereyim, böylece sadece bir an içinde var. 332 00:10:34,060 --> 00:10:37,000 Devam edin ve tıklayın Eğer düşündüğünüz next door. 333 00:10:37,000 --> 00:10:39,812 Evet iyi. 334 00:10:39,812 --> 00:10:41,020 TREVOR: Ben bir kapı unclick miyim? 335 00:10:41,020 --> 00:10:42,620 DAVID J. MALAN: Hayır, unclick olamaz. 336 00:10:42,620 --> 00:10:43,119 TREVOR: Tamam. 337 00:10:43,119 --> 00:10:43,974 Bu. 338 00:10:43,974 --> 00:10:45,640 DAVID J. MALAN: Nereye gitmek istiyorsun? 339 00:10:45,640 --> 00:10:46,410 Hangisi? 340 00:10:46,410 --> 00:10:47,230 >> TREVOR: Bu bir. 341 00:10:47,230 --> 00:10:48,042 >> DAVID J. MALAN: Hayır 342 00:10:48,042 --> 00:10:48,450 >> TREVOR: Tamam. 343 00:10:48,450 --> 00:10:48,735 Bu. 344 00:10:48,735 --> 00:10:49,020 >> DAVID J. MALAN: Evet. 345 00:10:49,020 --> 00:10:49,700 Bu iyi oldu. 346 00:10:49,700 --> 00:10:50,380 Pekala. 347 00:10:50,380 --> 00:10:53,900 Yani algoritması neydi ya Bu, Trevor yapmak için prosedür nedir? 348 00:10:53,900 --> 00:10:56,149 >> TREVOR: Ben sadece gitti Kapılar kadar bir 50 bulduk. 349 00:10:56,149 --> 00:10:56,940 DAVID J. MALAN: Tamam. 350 00:10:56,940 --> 00:10:58,150 Mükemmel algoritma. 351 00:10:58,150 --> 00:10:59,540 Yani sorun yok. 352 00:10:59,540 --> 00:11:03,120 Aslında, eğer ben açığa Çünkü ne Bu diğer iki kapılar ardında ne 353 00:11:03,120 --> 00:11:06,954 biz burada bulabilirsiniz biz sadece rastgele girişi var. 354 00:11:06,954 --> 00:11:08,870 Yani bu kadar aslında sen-ebil almak kadar iyi. 355 00:11:08,870 --> 00:11:12,509 Ve aslında, daha iyi anladım etraflıca bütün dizi arıyor, 356 00:11:12,509 --> 00:11:15,300 Gerçekten olurdu çünkü şanssız Numarayı isabet olsaydı 357 00:11:15,300 --> 00:11:16,604 Son kapıda 50. 358 00:11:16,604 --> 00:11:18,520 Ama ne onun yerine biz eğer Sana bir varsayım verdi. 359 00:11:18,520 --> 00:11:20,630 Sıralama tüm I varsayalım etrafında bu kapılar, 360 00:11:20,630 --> 00:11:23,500 böylece var sayılar bu kez kriteri 361 00:11:23,500 --> 00:11:29,730 ama bu sefer aslında a, bu kez different-- 362 00:11:29,730 --> 00:11:32,640 aslında sizin için sıralanır oluyor. 363 00:11:32,640 --> 00:11:35,380 Eldeki Ve şimdi gol sayı 50 vurmaktır. 364 00:11:35,380 --> 00:11:36,090 >> TREVOR: Tamam. 365 00:11:36,090 --> 00:11:37,670 >> DAVID J. MALAN: neler var olacak sizin algoritması? 366 00:11:37,670 --> 00:11:39,628 >> TREVOR: bu kadar Eh, eğer sıralanmış, o Ya gidiyor 367 00:11:39,628 --> 00:11:42,710 En büyük eğer en büyüğü şey olmak, azalan, o ilk olacak 368 00:11:42,710 --> 00:11:44,751 ya da tam tersi ise, bu sonuncusu olacaktır. 369 00:11:44,751 --> 00:11:48,897 Yani sadece bu kapıyı dokunun ve edeceğiz sonra sadece son kapıyı dokunun. 370 00:11:48,897 --> 00:11:49,980 DAVID J. MALAN: Mükemmel. 371 00:11:49,980 --> 00:11:50,270 Pekala. 372 00:11:50,270 --> 00:11:51,150 Bu yüzden sayı 50 bulundu. 373 00:11:51,150 --> 00:11:52,970 Yani en kısa sürede bildiği gibi Onlar dizildi, biz 374 00:11:52,970 --> 00:11:55,040 Bu varsayımı kaldıraç başardık. 375 00:11:55,040 --> 00:11:57,040 Bu yüzden böyle çok fazla konum Telefon rehberi örneği. 376 00:11:57,040 --> 00:11:59,540 En kısa sürede size, hatta birlikte olduğu gibi Bu gibi küçük bir sorun, 377 00:11:59,540 --> 00:12:02,380 senin girişler önceden sıralanmış, biz Aslında tartışmalı değeri bulmak 378 00:12:02,380 --> 00:12:03,130 daha verimli. 379 00:12:03,130 --> 00:12:05,800 >> Ve seni o olsaydı söylemedi , küçük büyük, küçük ya da büyük kriteri 380 00:12:05,800 --> 00:12:08,080 ve bu yüzden çok makul bir ucunda ya da başlatmak için 381 00:12:08,080 --> 00:12:09,750 Aslında hedef değeri bulmak için. 382 00:12:09,750 --> 00:12:11,400 Yani hem Trevor teşekkür ederiz. 383 00:12:11,400 --> 00:12:13,260 Ve ben güzel yapılır propose-- edeceğiz. 384 00:12:13,260 --> 00:12:16,960 Biz, aslında, küçük bir klip var , CS50 bizim favori anları arasında yer alıyor 385 00:12:16,960 --> 00:12:19,700 böylece bazen bu demolar Oldukça plana göre gitmez. 386 00:12:19,700 --> 00:12:22,050 Ve gerçekten de şu anda, ben Yanlış bir arayüz çekti 387 00:12:22,050 --> 00:12:23,508 hangi ile dokunmatik ekranı kullanmak için. 388 00:12:23,508 --> 00:12:24,660 Yani bu benim hatam oldu. 389 00:12:24,660 --> 00:12:26,600 >> Yani bunun için yapacak olarak gelecek yılki klibi 390 00:12:26,600 --> 00:12:28,570 Ben kendi ekranında tıklayarak oldu neden. 391 00:12:28,570 --> 00:12:31,390 Ama hızlı bir göz atalım Geçen yıl ne de 392 00:12:31,390 --> 00:12:34,770 çok gündeme geldi Jay, ile Burada Trevor gibi, gönüllü 393 00:12:34,770 --> 00:12:39,380 ve bu kısa klipte, görürsünüz Bu aynı demo oldukça vermedi nasıl 394 00:12:39,380 --> 00:12:41,074 öğrenilen aynı dersleri ortaya koymaktadır. 395 00:12:41,074 --> 00:12:41,740 [VİDEO OYNATMA] 396 00:12:41,740 --> 00:12:45,360 Ben yapmak istediğiniz -Tek artık Benim için bulmak ve bizim için, 397 00:12:45,360 --> 00:12:51,674 Gerçekten, sayı 50 adım adım. 398 00:12:51,674 --> 00:12:52,450 >> Sayılarının 50? 399 00:12:52,450 --> 00:12:53,190 >> -The Sayı 50. 400 00:12:53,190 --> 00:12:55,356 Ve sen ne ortaya çıkarabilir Bu kapıların ardında her 401 00:12:55,356 --> 00:12:58,540 sadece bir parmak ile dokunarak. 402 00:12:58,540 --> 00:13:00,910 Kahretsin. 403 00:13:00,910 --> 00:13:02,870 >> [Gülüyor] 404 00:13:02,870 --> 00:13:03,806 >> [SON OYNATMA] 405 00:13:03,806 --> 00:13:05,430 DAVID J. MALAN: Bu yüzden çok iyi gitti. 406 00:13:05,430 --> 00:13:06,796 Bu sıralanmamış kapı vardı. 407 00:13:06,796 --> 00:13:08,670 Ve Jay, tabii ki, Çok hızlı bir şekilde buldum. 408 00:13:08,670 --> 00:13:12,910 Trevor çok daha iyi bir iş yaptı Öğretilebilir an açısından, 409 00:13:12,910 --> 00:13:15,850 bu nedenle bu yıl, konuşmak için uzun sürüyor bulmak için. 410 00:13:15,850 --> 00:13:17,950 Tabii ki, o zaman biz verdi Jay ikinci şans, 411 00:13:17,950 --> 00:13:20,320 bu sayede biz kapıları kriteri Biz Trevor için yaptığı gibi, 412 00:13:20,320 --> 00:13:22,300 ve Trevor süper iyi bu sefer yaptı. 413 00:13:22,300 --> 00:13:26,124 Ama Jay yarısı kadar çabuk yaptım. 414 00:13:26,124 --> 00:13:26,790 [VİDEO OYNATMA] 415 00:13:26,790 --> 00:13:29,650 -The Amaç da artık etmektir bize numara 50 bulabilirsiniz 416 00:13:29,650 --> 00:13:33,030 ama algoritmik bunu, ve Bu konuda gidiyoruz nasıl bize bildirin. 417 00:13:33,030 --> 00:13:33,660 >> -TAMAM. 418 00:13:33,660 --> 00:13:35,604 >> Eğer bulursanız -Ve, filmi tutmak. 419 00:13:35,604 --> 00:13:37,228 Eğer bulamazsanız, onu geri ver. 420 00:13:37,228 --> 00:13:38,044 >> Adamım. 421 00:13:38,044 --> 00:13:38,860 >> Oh! 422 00:13:38,860 --> 00:13:40,800 >> - [Inaudible] Tamam. 423 00:13:40,800 --> 00:13:46,236 Yani uçlarını kontrol edeceğim Oh orada- olmadığını belirlemek için, ilk. 424 00:13:46,236 --> 00:13:48,646 >> [Alkış] 425 00:13:48,646 --> 00:13:53,948 426 00:13:53,948 --> 00:13:55,729 >> [SON OYNATMA] 427 00:13:55,729 --> 00:13:56,520 DAVID J. MALAN: Tamam. 428 00:13:56,520 --> 00:13:59,760 Yani açıkça kapıları sıralama daha verimli yol açar. 429 00:13:59,760 --> 00:14:01,680 Ve böylece, iki kat daha hızlı Orada ne demek olduğunu. 430 00:14:01,680 --> 00:14:03,270 Ve böylece Jay şanslı iki kere aldım. 431 00:14:03,270 --> 00:14:06,685 Ve o da son olarak şanslı var yıl, bazı Blu-ray diskler sipariş 432 00:14:06,685 --> 00:14:07,560 aslında dışarı vermek. 433 00:14:07,560 --> 00:14:09,768 Bu yıl üzgünüm, biz Trevor aynı yoktu. 434 00:14:09,768 --> 00:14:11,540 Ama daha iyisi bir kaç yıl önce oldu. 435 00:14:11,540 --> 00:14:14,820 Ve bazılarınız biliyor olabilir, bu O CS50 oldu adam, Sean, 436 00:14:14,820 --> 00:14:17,780 Kesin olan meydan Aynı sorun, SD de olsa, 437 00:14:17,780 --> 00:14:19,360 Yakında, geri gün göreceğimiz gibi. 438 00:14:19,360 --> 00:14:22,622 Ve sadece vermedi bulacaksınız O, Jay biraz daha uzun sürebilir 439 00:14:22,622 --> 00:14:25,580 Trevor biraz daha uzun, öyleydi aslında bu harika bir fırsat 440 00:14:25,580 --> 00:14:29,820 neredeyse herkes meşgul kalabalık la Fiyat teşvik Sağ 441 00:14:29,820 --> 00:14:31,889 Onu biz arayan numarayı bulmak için. 442 00:14:31,889 --> 00:14:32,930 Haydi. bir göz atın. 443 00:14:32,930 --> 00:14:33,320 >> [VİDEO OYNATMA] 444 00:14:33,320 --> 00:14:33,820 >> -TAMAM. 445 00:14:33,820 --> 00:14:36,680 Yani burada görev Sean, şudur. 446 00:14:36,680 --> 00:14:40,860 Ben bunların arkasında gizli Kapılar sayı yedi. 447 00:14:40,860 --> 00:14:45,120 Fakat bu kapıların bazıları sıkışmış hem de diğer negatif sayılar vardır. 448 00:14:45,120 --> 00:14:47,500 Ve hedef düşünmektir sayıların bu üst satırın 449 00:14:47,500 --> 00:14:50,390 sadece bir dizi, ya da sadece kağıt parçaları dizisi 450 00:14:50,390 --> 00:14:51,510 Arkalarında numaraları ile. 451 00:14:51,510 --> 00:14:55,540 Ve amacınız sadece üst kullanılarak, bir Dizi burada, bana numarayı yedi bulabilirsiniz. 452 00:14:55,540 --> 00:14:58,570 Ve biz o eleştirmek için gidiyoruz Bunu yaparken nasıl. 453 00:14:58,570 --> 00:14:59,070 -Pekala. 454 00:14:59,070 --> 00:15:00,850 Bize numarayı yedi, lütfen bul. 455 00:15:00,850 --> 00:15:10,500 456 00:15:10,500 --> 00:15:11,000 Hayır. 457 00:15:11,000 --> 00:15:15,050 458 00:15:15,050 --> 00:15:18,550 Beş, 19, 13. 459 00:15:18,550 --> 00:15:22,240 460 00:15:22,240 --> 00:15:24,770 >> [Gülüyor] 461 00:15:24,770 --> 00:15:25,910 >> Bu hileli bir soru değil. 462 00:15:25,910 --> 00:15:29,410 463 00:15:29,410 --> 00:15:29,910 Bir. 464 00:15:29,910 --> 00:15:33,218 465 00:15:33,218 --> 00:15:34,695 >> [Gülüyor] 466 00:15:34,695 --> 00:15:37,861 Bu noktada, puanınızı çok değil İyi, siz de devam olabilir. 467 00:15:37,861 --> 00:15:40,610 468 00:15:40,610 --> 00:15:41,110 Üç. 469 00:15:41,110 --> 00:15:43,890 470 00:15:43,890 --> 00:15:45,378 >> [Gülüyor] 471 00:15:45,378 --> 00:15:46,370 472 00:15:46,370 --> 00:15:47,774 >> Devam et. 473 00:15:47,774 --> 00:15:50,690 Açıkçası, ben yardım edemem ama merak ediyorum ne bile yani-- düşünüyorsanız 474 00:15:50,690 --> 00:15:51,959 >> [Gülüyor] 475 00:15:51,959 --> 00:15:53,229 476 00:15:53,229 --> 00:15:55,020 Sadece üst satır, böylece Üç sol var. 477 00:15:55,020 --> 00:15:56,200 Bu yüzden bana yedi bulabilirsiniz. 478 00:15:56,200 --> 00:15:59,700 479 00:15:59,700 --> 00:16:02,167 >> [Gülüyor] 480 00:16:02,167 --> 00:16:14,870 481 00:16:14,870 --> 00:16:15,370 17. 482 00:16:15,370 --> 00:16:25,675 483 00:16:25,675 --> 00:16:26,946 Yedi. 484 00:16:26,946 --> 00:16:28,780 >> [Alkış] 485 00:16:28,780 --> 00:16:29,426 >> Pekala. 486 00:16:29,426 --> 00:16:30,360 >> [SON OYNATMA] 487 00:16:30,360 --> 00:16:31,840 >> DAVID J. MALAN: Yani biz-ebil Bu gün uzun izleyebilirsiniz. 488 00:16:31,840 --> 00:16:34,090 Ve tabii ki, bazı Bu yılki demolar belki 489 00:16:34,090 --> 00:16:36,330 Şimdi önümüzdeki içinde sona erecek yılın Video de. 490 00:16:36,330 --> 00:16:39,040 Bu yüzden şimdi aslında atalım algoritmalar odaklanmak 491 00:16:39,040 --> 00:16:42,140 biz değil eğer burada, ve görmek Şimdi resmileştirmek başlar 492 00:16:42,140 --> 00:16:46,650 bizim veri alma hakkında nasıl gidebiliriz Bu duruma o sıralanmış var ki 493 00:16:46,650 --> 00:16:50,054 yani sonuçta, biz aslında can daha verimli bir şekilde arayın. 494 00:16:50,054 --> 00:16:52,470 Ve biz gidiyoruz bile oldukça küçük veri setleri kullanmak, 495 00:16:52,470 --> 00:16:54,511 Sekiz sayı gibi biz Gemide burada var, 496 00:16:54,511 --> 00:16:58,230 sonuçta bu aynı fikirleri uygulayabilirsiniz 1000 girişlere, bir milyon girişleri, 497 00:16:58,230 --> 00:17:02,100 4 milyar giriş, algoritmalar, çünkü temelde aynı olacak. 498 00:17:02,100 --> 00:17:05,359 >> Ve böylece bu bizim son bir Gönüllüler bugün için fırsat, 499 00:17:05,359 --> 00:17:09,790 ama belki de en tutulan biri, hangi biz sekiz gönüllülere ihtiyacımız var 500 00:17:09,790 --> 00:17:12,960 gelip bize yürümeyi sıralama işlemi, kısa sürede olacak 501 00:17:12,960 --> 00:17:15,212 Bu müziği olmak burada duruyor. 502 00:17:15,212 --> 00:17:16,170 Beni buraya başlayalım. 503 00:17:16,170 --> 00:17:19,692 >> Yani turquoise-- yeşil bir değil mi? 504 00:17:19,692 --> 00:17:21,130 Eğer ediyorsunuz demektir? 505 00:17:21,130 --> 00:17:21,630 İki. 506 00:17:21,630 --> 00:17:23,069 Aşağı gel. 507 00:17:23,069 --> 00:17:23,569 TAMAM. 508 00:17:23,569 --> 00:17:24,420 Üç. 509 00:17:24,420 --> 00:17:25,400 Dört. 510 00:17:25,400 --> 00:17:27,247 Beş Tamam bana-- edelim. 511 00:17:27,247 --> 00:17:28,830 Sen arkadaş tarafından aday ediliyoruz. 512 00:17:28,830 --> 00:17:31,340 Altı, yedi, sekiz. 513 00:17:31,340 --> 00:17:32,130 Yukarı gel. 514 00:17:32,130 --> 00:17:32,630 Pekala. 515 00:17:32,630 --> 00:17:33,190 Çok teşekkür ederim. 516 00:17:33,190 --> 00:17:33,689 Yukarı gel. 517 00:17:33,689 --> 00:17:34,790 Yukarı gel. 518 00:17:34,790 --> 00:17:35,330 >> Pekala. 519 00:17:35,330 --> 00:17:38,890 Yani biz burada-- ve bu ne var daha garip olanlar arasında yer alıyor, 520 00:17:38,890 --> 00:17:42,390 Bu beri sana o mizah gerektirir zaman sadece biraz benim için. 521 00:17:42,390 --> 00:17:43,442 Sen bir numara olacaktır. 522 00:17:43,442 --> 00:17:44,150 Adın ne? 523 00:17:44,150 --> 00:17:44,610 >> ANNAN: Annan. 524 00:17:44,610 --> 00:17:45,526 >> DAVID J. MALAN: Annan. 525 00:17:45,526 --> 00:17:46,092 David. 526 00:17:46,092 --> 00:17:46,800 Adın ne? 527 00:17:46,800 --> 00:17:47,140 >> JOSEPH: Joseph. 528 00:17:47,140 --> 00:17:49,190 >> DAVID J. MALAN: Joseph, Eğer iki numaralı bulunmaktadır. 529 00:17:49,190 --> 00:17:52,260 >> SERENA: Serena, üç numara. 530 00:17:52,260 --> 00:17:53,722 Stefan sayı dört. 531 00:17:53,722 --> 00:17:54,430 Cynthia: Cynthia. 532 00:17:54,430 --> 00:17:57,548 DAVID J. MALAN: Cynthia, beş numara. 533 00:17:57,548 --> 00:17:58,452 [Duyulamaz] 534 00:17:58,452 --> 00:17:59,618 DAVID J. MALAN: [duyulamaz]. 535 00:17:59,618 --> 00:18:00,391 David sayı altı. 536 00:18:00,391 --> 00:18:00,890 MAT: Matt. 537 00:18:00,890 --> 00:18:02,160 DAVID J. MALAN: Matt sayı yedi. 538 00:18:02,160 --> 00:18:02,850 Ve? 539 00:18:02,850 --> 00:18:03,210 >> WAVERLY: Waverly. 540 00:18:03,210 --> 00:18:04,470 >> DAVID J. MALAN: Waverly, sekiz numara. 541 00:18:04,470 --> 00:18:04,970 Pekala. 542 00:18:04,970 --> 00:18:06,510 Eğer hoppala Yapabileceğim. 543 00:18:06,510 --> 00:18:08,820 Hepinizin ise, olduğu gibi senin Orada ilk sorun, 544 00:18:08,820 --> 00:18:10,820 Sekiz Müzik standları vardır Burada seyirci karşı karşıya. 545 00:18:10,820 --> 00:18:14,200 Eğer üzerinde numara koymak olsaydı Bu müzik şekilde duran 546 00:18:14,200 --> 00:18:16,560 onlar hizaya olduğunu gemide aynı numaralar. 547 00:18:16,560 --> 00:18:19,560 Yani kendinizi tarafından böyle görünmesi Bu müziği numaralarınızı koyarak 548 00:18:19,560 --> 00:18:21,960 Burada duruyor. 549 00:18:21,960 --> 00:18:25,980 Mükemmel kadar. 550 00:18:25,980 --> 00:18:26,600 >> Mükemmel. 551 00:18:26,600 --> 00:18:26,890 TAMAM. 552 00:18:26,890 --> 00:18:29,556 Yani şimdi biz sormak için gidiyoruz Bir kaç farklı şekilde soru. 553 00:18:29,556 --> 00:18:31,610 Nasıl sıralama hakkında gidebilirsiniz Burada bu millet kadar? 554 00:18:31,610 --> 00:18:34,500 Biz birkaç yaklaşım vardı çünkü Daha önce, biz bu sayede vardı 555 00:18:34,500 --> 00:18:36,360 tür iki farklı kova yapma. 556 00:18:36,360 --> 00:18:38,842 Ve sonra biz genellikle vardı Birlikte bir şeyler ekleme. 557 00:18:38,842 --> 00:18:41,050 En kısa sürede biz iki sayı gördüğümüz gibi bu arada ait 558 00:18:41,050 --> 00:18:41,975 Biz bunları bir araya koymak. 559 00:18:41,975 --> 00:18:43,350 Birbirine ait iki mektup. 560 00:18:43,350 --> 00:18:45,058 >> Ama eğer görelim biz Bu resmileştirmek edemez, 561 00:18:45,058 --> 00:18:48,044 sonuçta sahip olacak şekilde olacak bazı sözde kod, 562 00:18:48,044 --> 00:18:49,710 hangi ile bu sorunları çözebilir. 563 00:18:49,710 --> 00:18:51,870 Yani şimdi, ben bakıyorum Burada bu rakamlara. 564 00:18:51,870 --> 00:18:55,030 Ve ben hatalar bir sürü görürsünüz. 565 00:18:55,030 --> 00:18:57,750 Sonuçta, ben bir tane istiyorum sol ve sağ tarafta sekiz. 566 00:18:57,750 --> 00:19:00,650 >> Ve bu yüzden bakıyorum Bu iki, dört ve iki. 567 00:19:00,650 --> 00:19:02,930 Ve sorun Açıkçası, ne? 568 00:19:02,930 --> 00:19:04,261 Evet. 569 00:19:04,261 --> 00:19:04,760 So 570 00:19:04,760 --> 00:19:07,160 İki besbelli önce gelir Dört, yani ne biliyor musun? 571 00:19:07,160 --> 00:19:10,210 Beni ilk açgözlü bir yaklaşım ele alalım, çok benzer bir sorun eğer sen 572 00:19:10,210 --> 00:19:13,790 Eğer gelen çağırmak durumunda Şehre set Sorun Set One Standard Edition, 573 00:19:13,790 --> 00:19:16,820 Nerede Ben sadece yerel sorunu çözmek bana hemen önünde burada 574 00:19:16,820 --> 00:19:17,690 beni nereye götürecek ve bakın. 575 00:19:17,690 --> 00:19:17,870 >> TAMAM. 576 00:19:17,870 --> 00:19:20,161 Yani iki ve dört, gitmeme izin önde ve sadece size iki takas. 577 00:19:20,161 --> 00:19:22,400 Fiziksel hareket edebilirsiniz Kendinizi ve kağıt, 578 00:19:22,400 --> 00:19:25,040 Ben aldık görünüyor Daha iyi bir durumda listelenmektedir. 579 00:19:25,040 --> 00:19:26,330 >> Şimdi, onlar iyi. 580 00:19:26,330 --> 00:19:28,480 Ben, hareket için gidiyorum dört ve altı iyi görünüyor. 581 00:19:28,480 --> 00:19:29,110 Problem değil. 582 00:19:29,110 --> 00:19:30,440 Altı ve sekiz Tamam. 583 00:19:30,440 --> 00:19:31,860 Sekiz ve bir başka sorun. 584 00:19:31,860 --> 00:19:34,750 Sekiz ve biri hakkında doğru ne için mi? 585 00:19:34,750 --> 00:19:36,990 Bir, sekiz önce gelir ve böylece biz ne yapmalıyız? 586 00:19:36,990 --> 00:19:38,090 Şimdi bu ikisini takas edelim. 587 00:19:38,090 --> 00:19:39,316 Bir ve sekiz. 588 00:19:39,316 --> 00:19:40,690 Ve şimdi, ben devam edeceğim. 589 00:19:40,690 --> 00:19:42,030 Ben ileriye bakmaya devam edeceğim. 590 00:19:42,030 --> 00:19:42,840 Ve en ne olacağını görelim. 591 00:19:42,840 --> 00:19:44,680 Sekiz üç, ve Tabii ki, sıra dışı. 592 00:19:44,680 --> 00:19:45,815 En takas edelim. 593 00:19:45,815 --> 00:19:46,940 Elbette sekiz ve yedi. 594 00:19:46,940 --> 00:19:47,481 Bozuk. 595 00:19:47,481 --> 00:19:48,280 En takas edelim. 596 00:19:48,280 --> 00:19:49,940 Sekiz'in ve beş tabii ki, hadi takas. 597 00:19:49,940 --> 00:19:50,560 Pekala. 598 00:19:50,560 --> 00:19:51,880 Liste sıralanır. 599 00:19:51,880 --> 00:19:53,060 evet? 600 00:19:53,060 --> 00:19:54,280 >> Tamam, tabii ki değil. 601 00:19:54,280 --> 00:19:55,860 Ama bu doğru, biraz daha iyidir? 602 00:19:55,860 --> 00:19:57,270 Ne haber Ne Çünkü. 603 00:19:57,270 --> 00:20:01,749 Her zaman biz bir takas, gerçekleştirilen küçük bir sayı tür bu şekilde percolated, 604 00:20:01,749 --> 00:20:03,790 ve daha büyük bir sayı Bu şekilde süzülmüş, ya da biz olacak 605 00:20:03,790 --> 00:20:06,880 için kabarmış söyleyerek başlamak sola veya sağa kabarmış. 606 00:20:06,880 --> 00:20:10,080 >> Şimdi, bunun nedeni, yeterli değil en iyi bir sayı olabilir 607 00:20:10,080 --> 00:20:11,990 tek nokta taşındık ileri, ya da en kötüsü, 608 00:20:11,990 --> 00:20:13,880 Bir numara olabilir ayrıca bir nokta taşındı. 609 00:20:13,880 --> 00:20:16,369 Peki ne, bu tür biliyorum şimdiye kadar oldukça iyi çalıştı. 610 00:20:16,369 --> 00:20:17,410 Bana sadece tekrar deneyelim. 611 00:20:17,410 --> 00:20:18,880 İki ve dört onlar iyiyiz. 612 00:20:18,880 --> 00:20:20,180 Dört ve altı, onlar iyiyiz. 613 00:20:20,180 --> 00:20:21,790 Altı ve bir, sıra dışı. 614 00:20:21,790 --> 00:20:23,007 Yani seni iki takas edelim. 615 00:20:23,007 --> 00:20:25,840 Ve şimdi, sorun en dikkat iyi yine biraz almaya başlıyor. 616 00:20:25,840 --> 00:20:27,006 Altı ve üç sıra dışı. 617 00:20:27,006 --> 00:20:28,100 Seni iki takas edelim. 618 00:20:28,100 --> 00:20:29,730 Altı yedi, sen iyisin. 619 00:20:29,730 --> 00:20:32,230 Yedi beş, tabii ki, sıra dışı. 620 00:20:32,230 --> 00:20:33,920 Sırayla yedi ve sekiz. 621 00:20:33,920 --> 00:20:36,470 Ve şimdi, ben gerekebilir Daha fazla bu birkaç kez yapın. 622 00:20:36,470 --> 00:20:39,830 Ve aslında, kendisi için düşünmeye belki kaç kez maksimum 623 00:20:39,830 --> 00:20:41,330 Ben ileri geri yürümek zorunda kalabilirsiniz? 624 00:20:41,330 --> 00:20:42,390 >> Biz geri geleceğiz. 625 00:20:42,390 --> 00:20:43,700 Yani iki ve dört hala Tamam. 626 00:20:43,700 --> 00:20:44,940 Dört ve bir, hayır. 627 00:20:44,940 --> 00:20:45,747 Yani, en swap edelim. 628 00:20:45,747 --> 00:20:47,830 Ve yine, görsel fark tek köpüren tür 629 00:20:47,830 --> 00:20:49,163 Olması gereken solunda. 630 00:20:49,163 --> 00:20:50,010 Dört ve üç takas. 631 00:20:50,010 --> 00:20:51,330 Dört ve altı. 632 00:20:51,330 --> 00:20:53,100 Altı ve beş takas. 633 00:20:53,100 --> 00:20:53,959 Altı yedi. 634 00:20:53,959 --> 00:20:55,000 Yedi sekiz iyidir. 635 00:20:55,000 --> 00:20:55,500 >> İyi. 636 00:20:55,500 --> 00:20:58,460 Biz daha iyi alıyoruz. 637 00:20:58,460 --> 00:20:59,130 Yani görelim. 638 00:20:59,130 --> 00:21:00,940 Şimdi, biz iki ve bir tane var. 639 00:21:00,940 --> 00:21:02,520 Tabii ki, takas. 640 00:21:02,520 --> 00:21:07,520 İki ve üç, üç ve dört, dört ve Beş, altı ve yedi, yedi ve sekiz. 641 00:21:07,520 --> 00:21:08,020 İyi. 642 00:21:08,020 --> 00:21:08,730 Ve biliyor musun? 643 00:21:08,730 --> 00:21:11,190 Ben orada bir değişiklik yapılmadı Çünkü Bana bir sağlamlık denetimi yapalım. 644 00:21:11,190 --> 00:21:13,023 Beni tüm yol gidelim başa geri. 645 00:21:13,023 --> 00:21:13,680 TAMAM. 646 00:21:13,680 --> 00:21:14,750 Bir, yup iki--, gördün mü? 647 00:21:14,750 --> 00:21:15,870 Bir şeyler yanlış oldu. 648 00:21:15,870 --> 00:21:18,420 Üç, dört, beş, altı, yedi, sekiz. 649 00:21:18,420 --> 00:21:21,920 Ve bu son geçişte vardır benim şimdi ile rahat 650 00:21:21,920 --> 00:21:23,830 o sıralanır iddia eden? 651 00:21:23,830 --> 00:21:24,330 TAMAM. 652 00:21:24,330 --> 00:21:25,880 Görme, kesinlikle doğrudur. 653 00:21:25,880 --> 00:21:28,410 Ama işlevsel, ne Ayrıca sadece oldu 654 00:21:28,410 --> 00:21:31,870 size izin verdiği son geçişte Bu liste aslında olduğunu teyit etmek 655 00:21:31,870 --> 00:21:32,660 kriteri? 656 00:21:32,660 --> 00:21:34,477 >> Ne yapmak ya bu son geçiş yapmadım? 657 00:21:34,477 --> 00:21:35,810 HEDEF KİTLE: hiçbir değişiklik yoktu. 658 00:21:35,810 --> 00:21:36,120 DAVID J. MALAN: Üzgünüm? 659 00:21:36,120 --> 00:21:37,070 HEDEF KİTLE: değişiklik yok. 660 00:21:37,070 --> 00:21:38,653 DAVID J. MALAN: herhangi bir değişiklik olmamıştır. 661 00:21:38,653 --> 00:21:41,947 Bu yüzden benim aptal olacağını Yine aynı algoritmayı yapmak 662 00:21:41,947 --> 00:21:43,780 Ben herhangi yapmadım eğer İlk defa değiştirir. 663 00:21:43,780 --> 00:21:45,160 Ve devlet değişmedi. 664 00:21:45,160 --> 00:21:47,576 Şüphesiz, ben yapmak için gitmiyorum her ikinci kez değiştirir. 665 00:21:47,576 --> 00:21:49,820 Ve böylece, artık güvenli demek, liste sıralanır. 666 00:21:49,820 --> 00:21:52,069 >> Ve gerçekten de, bu şimdi bir şey biz genellikle olacak 667 00:21:52,069 --> 00:21:56,900 çağrı kabarcık sıralama, bu sayede ikili, Eğer tekrar hataları düzeltmek için 668 00:21:56,900 --> 00:22:00,210 ve tekrar ve tekrar ve size ileri ve geri gidiyor tutmak, 669 00:22:00,210 --> 00:22:03,370 ve ileri geri, senin kadar Böyle swapları, yapmak hangi noktada 670 00:22:03,370 --> 00:22:07,089 Eğer ben, evet, emin olabilirsiniz hatalar tüm sabitleme tamamladı. 671 00:22:07,089 --> 00:22:08,630 En sıfırlamak ve başka bir yaklaşım deneyelim. 672 00:22:08,630 --> 00:22:11,590 Siz geri gidebiliriz Eğer sırası, bir an önce vardı 673 00:22:11,590 --> 00:22:13,780 hangi bu gibi görünüyordu. 674 00:22:13,780 --> 00:22:17,640 Şimdi bir yaklaşım a atalım Daha fazla sınav kitap gibi küçük, 675 00:22:17,640 --> 00:22:21,122 bu sayede sürekli vardı Alfabenin harfini seçtikten 676 00:22:21,122 --> 00:22:22,830 biz tür istedim Bir sonraki başa. 677 00:22:22,830 --> 00:22:26,420 Belki yüksek bir mektup oldu, A, veya düşük mektup Z. gibi 678 00:22:26,420 --> 00:22:28,170 >> Yani herkes geri bu sırada bulunuyor. 679 00:22:28,170 --> 00:22:29,800 Ve şimdi bunu yapmama izin ver. 680 00:22:29,800 --> 00:22:34,880 Diyelim ki ben biliyorum görelim Burada sekiz sayı. 681 00:22:34,880 --> 00:22:37,410 Ben devam edeceğim ve Sadece kasten seçin 682 00:22:37,410 --> 00:22:38,520 küçük elemanları. 683 00:22:38,520 --> 00:22:38,760 Sağ? 684 00:22:38,760 --> 00:22:39,801 Bu da sezgisel görünüyor. 685 00:22:39,801 --> 00:22:42,560 Neden küçük bulmuyorum ait olduğu yere elemanın, koyun 686 00:22:42,560 --> 00:22:45,280 sonraki en küçük elemanı olsun, koymak o aittir ve sadece tekrar nerede. 687 00:22:45,280 --> 00:22:46,820 >> Sezgisel Çünkü Bu çok çalışması gerekir. 688 00:22:46,820 --> 00:22:48,441 Yani dört, bu oldukça küçük bir sayı bu. 689 00:22:48,441 --> 00:22:49,940 Ben bu nerede hatırlamak için gidiyorum. 690 00:22:49,940 --> 00:22:50,523 Bir dakika bekle. 691 00:22:50,523 --> 00:22:51,577 İki küçük. 692 00:22:51,577 --> 00:22:53,910 Şimdi beni nerede anımsayalım iki ve yaklaşık dört unutun. 693 00:22:53,910 --> 00:22:55,050 Biz daha sonra ilgilenirim. 694 00:22:55,050 --> 00:22:56,460 Altı, ben ilgilenmiyorum. 695 00:22:56,460 --> 00:22:57,810 Sekiz, ben ilgilenmiyorum. 696 00:22:57,810 --> 00:22:59,780 Biri benim yeni küçük sayıdır. 697 00:22:59,780 --> 00:23:01,470 Yani biri nerede olduğunu hatırlamak için gidiyorum. 698 00:23:01,470 --> 00:23:02,534 Üç, ilgilenmiyorum. 699 00:23:02,534 --> 00:23:03,450 Yedi, ilgilenmiyorum. 700 00:23:03,450 --> 00:23:04,530 Beş, ilgilenmiyorum. 701 00:23:04,530 --> 00:23:07,390 >> Düşmeden Yani sahne bu yıl, 702 00:23:07,390 --> 00:23:09,890 Ben numarayı alayım Şehre ve senin adın neydi? 703 00:23:09,890 --> 00:23:10,150 >> ANNAN: Annan. 704 00:23:10,150 --> 00:23:11,220 >> DAVID J. MALAN: Annan. 705 00:23:11,220 --> 00:23:13,540 Ve bana katılmak eğer Listenin başında, 706 00:23:13,540 --> 00:23:14,870 nereye ait olduğunu seni koyalım. 707 00:23:14,870 --> 00:23:16,080 Unfortunately-- adın ne? 708 00:23:16,080 --> 00:23:16,650 >> STEFAN: Stefan. 709 00:23:16,650 --> 00:23:18,191 >> DAVID J. MALAN: Stefan şekilde olduğunu. 710 00:23:18,191 --> 00:23:23,490 Stefan, bu çözer önce Yani Sorun, ne yapmalıyız? 711 00:23:23,490 --> 00:23:25,412 Biz Stefan ile ne yapacağız? 712 00:23:25,412 --> 00:23:27,269 >> HEDEF KİTLE: [duyulamaz]. 713 00:23:27,269 --> 00:23:28,060 DAVID J. MALAN: Tamam. 714 00:23:28,060 --> 00:23:28,850 Yani biz bunu yapabilir. 715 00:23:28,850 --> 00:23:31,730 Biz tür Stefan ve sürebilir onun Dört ve sadece bir değişkene koymak 716 00:23:31,730 --> 00:23:33,530 ve için ona tutun zaman bir miktar, 717 00:23:33,530 --> 00:23:35,220 böylece bir numara için oda yapma. 718 00:23:35,220 --> 00:23:36,280 Ve bu da kötü değil. 719 00:23:36,280 --> 00:23:39,270 Ben neden bunu, hatırlatıyoruz Biz sadece burada Stefan koydu? 720 00:23:39,270 --> 00:23:41,610 Neden bu bir ihlal edebilir fikirlerin başladık 721 00:23:41,610 --> 00:23:44,830 Geçen hafta, son kez bahsediyoruz? 722 00:23:44,830 --> 00:23:45,330 Evet? 723 00:23:45,330 --> 00:23:45,740 >> HEDEF KİTLE: [duyulamaz]. 724 00:23:45,740 --> 00:23:46,860 >> DAVID J. MALAN: onun için hiçbir indeks var. 725 00:23:46,860 --> 00:23:49,735 Bir şekilde, gerçekten, bu düşünürsek Dizi, bu olumsuz gibi olduğunu, 726 00:23:49,735 --> 00:23:52,900 yani bellek aslında var Burada bu gerçekten bir dizi ise, 727 00:23:52,900 --> 00:23:55,090 gibi biz derste geçen hafta ilan etti. 728 00:23:55,090 --> 00:23:56,250 Yani biz bunu yapmamalıyız. 729 00:23:56,250 --> 00:23:57,340 Biz bir değişkende saklamak olabilir. 730 00:23:57,340 --> 00:23:57,820 >> Yoksa biliyor musun? 731 00:23:57,820 --> 00:23:59,153 Ben başkası öneririz duydum. 732 00:23:59,153 --> 00:24:01,020 Biz Stefan ile başka ne yapabilirdi? 733 00:24:01,020 --> 00:24:03,770 Neden biz sadece onu tahliye yok ve bir numara nerede üzerine koydular. 734 00:24:03,770 --> 00:24:05,170 Oraya gitmek istiyorum Yani eğer. 735 00:24:05,170 --> 00:24:07,300 Ve gerçekten de, bu bir Oldukça iyi bir çözüm. 736 00:24:07,300 --> 00:24:10,480 Şimdi, bir yandan, biraz ettik en kötü sorunu yaptı. 737 00:24:10,480 --> 00:24:13,650 Dört uzağa şimdi olması gereken yerden. 738 00:24:13,650 --> 00:24:14,900 Bu yarıda doğru olmalıdır. 739 00:24:14,900 --> 00:24:16,100 >> Ama ne biliyor musun? 740 00:24:16,100 --> 00:24:17,630 Bu kötü şans olabilirdi. 741 00:24:17,630 --> 00:24:18,822 Belki sayı sekiz buradaydı. 742 00:24:18,822 --> 00:24:20,530 Ve böylece, belki biz-cekti Şanslı aldık, 743 00:24:20,530 --> 00:24:22,460 ve sonuna kadar sekiz yakın itti. 744 00:24:22,460 --> 00:24:24,710 Günün sonunda Yani, bu tür tüm ortalamalar dışarı. 745 00:24:24,710 --> 00:24:26,085 Biz yaklaşık dört bakım gerekmez. 746 00:24:26,085 --> 00:24:29,400 Şu an umurumda hepsi En küçük eleman seçme. 747 00:24:29,400 --> 00:24:32,030 >> Ve şimdi, ben ne gidiyorum bir numara unutun yapmak 748 00:24:32,030 --> 00:24:35,160 kalıcı, biliyorum çünkü Arkamda listesi şimdi sıralanır. 749 00:24:35,160 --> 00:24:36,720 Yani benim liste önceden boyut sekiz yaşındaydı. 750 00:24:36,720 --> 00:24:37,720 Şimdi, bu büyüklük yedi bulunuyor. 751 00:24:37,720 --> 00:24:40,340 Yani benim sorunum oluyor doğrusal olsa daha küçük. 752 00:24:40,340 --> 00:24:43,022 Yani şimdi, ben seçmek için gidiyorum Geçerli en küçük elemanı, iki. 753 00:24:43,022 --> 00:24:46,520 Altı, sekiz, dört, üç, yedi, beş. 754 00:24:46,520 --> 00:24:47,770 O küçük elemanı oldu. 755 00:24:47,770 --> 00:24:49,416 Peki Bense yapmaya gidiyorum Adın neydi? 756 00:24:49,416 --> 00:24:49,760 >> JOSEPH: Joseph. 757 00:24:49,760 --> 00:24:50,085 >> DAVID J. MALAN: Joseph? 758 00:24:50,085 --> 00:24:52,000 Biz bir yerde Yusuf'u terk edeceksin. 759 00:24:52,000 --> 00:24:54,842 Şimdi, ben iddia gidiyorum Bu adamlar iyi mudur ki 760 00:24:54,842 --> 00:24:56,550 Biliyorum ki bu iki Zaten sıralanır. 761 00:24:56,550 --> 00:24:58,424 Şimdi odaklanmak edelim Listenin geri kalanı. 762 00:24:58,424 --> 00:25:00,080 Altı akım küçüğüdür. 763 00:25:00,080 --> 00:25:01,190 Sekiz büyük. 764 00:25:01,190 --> 00:25:02,970 Dört artık geçerli küçüğüdür. 765 00:25:02,970 --> 00:25:04,762 Üç şimdi geçerli küçüğüdür. 766 00:25:04,762 --> 00:25:07,720 Ve şimdi, ben, üç seçmek için gidiyorum kim adınız tekrar ne bu--? 767 00:25:07,720 --> 00:25:08,190 SERENA: Serena. 768 00:25:08,190 --> 00:25:10,620 DAVID J. MALAN: Serena, sen-ebil eğer Numaranızı ve takas Şarkı söylemeyi kes kapmak 769 00:25:10,620 --> 00:25:11,550 Kalsang: kalsang. 770 00:25:11,550 --> 00:25:12,940 DAVID J. MALAN: kalsang. 771 00:25:12,940 --> 00:25:15,220 Geri gel, ve biz konum Bu ikisini takas olacak. 772 00:25:15,220 --> 00:25:17,360 Ve şimdi, otomatik pilotta bu etsinler. 773 00:25:17,360 --> 00:25:21,589 Ben gidip adamlara bırakmak için gidiyorum Bir sonraki en küçük öğeleri seçin. 774 00:25:21,589 --> 00:25:22,380 Dun, dun, dun, dun. 775 00:25:22,380 --> 00:25:24,560 Dört numara, ne yapmalıyım? 776 00:25:24,560 --> 00:25:26,261 Mükemmel. 777 00:25:26,261 --> 00:25:27,760 Şimdi, ben başka bir geçiş yapmak için gidiyorum. 778 00:25:27,760 --> 00:25:28,590 Dun, dun, dun, dun. 779 00:25:28,590 --> 00:25:31,465 Beş sonraki küçük olduğunu görüyoruz. 780 00:25:31,465 --> 00:25:32,840 Şimdi, ben başka bir geçiş almak gidiyorum. 781 00:25:32,840 --> 00:25:33,631 Dun, dun, dun, dun. 782 00:25:33,631 --> 00:25:34,880 Altı küçüğüdür. 783 00:25:34,880 --> 00:25:35,520 İyi. 784 00:25:35,520 --> 00:25:36,585 Yedi küçüğüdür. 785 00:25:36,585 --> 00:25:37,085 Değişiklik yok. 786 00:25:37,085 --> 00:25:38,630 Sekiz küçüğüdür. 787 00:25:38,630 --> 00:25:39,170 Bitti. 788 00:25:39,170 --> 00:25:43,900 >> Peki biz sadece iteratif tarafından yaptık birbiri ardına eleman seçme 789 00:25:43,900 --> 00:25:47,230 Biz konum şey uygulamak olduğunu Seçim tür olarak resmileştirmek için gidiyor. 790 00:25:47,230 --> 00:25:49,120 Ve hatta belki de var: açıklamak için daha basit, 791 00:25:49,120 --> 00:25:51,310 kelimenin tam anlamıyla hepinizi ki Sadece tutmak yapmak istiyorum 792 00:25:51,310 --> 00:25:54,700 liste üzerinden ileri ve geri gidiyor seçilmesi, küçük bir sonraki elemanı, 793 00:25:54,700 --> 00:25:55,720 bitirdiniz kadar. 794 00:25:55,720 --> 00:25:58,650 >> Bu yüzden belki de daha basit bulunuyor sezgisel, geçen daha. 795 00:25:58,650 --> 00:26:00,020 En son deneyelim. 796 00:26:00,020 --> 00:26:03,060 Siz kendinizi sıfırlamak olsaydı Aşağıdaki pozisyonlara 797 00:26:03,060 --> 00:26:08,600 son bir kez görelim eğer biz değil Şimdi bir başka yaklaşım resmileştirmek. 798 00:26:08,600 --> 00:26:12,857 Aslında, olur birisi Orada önermek istiyorum 799 00:26:12,857 --> 00:26:14,440 Biz bunu hakkında nasıl başka gidebilir? 800 00:26:14,440 --> 00:26:17,439 Buzzwords veya sıralama dışarı atarak olmadan Zaten bilinen cevapların, 801 00:26:17,439 --> 00:26:19,689 sadece sezgisel, ne yapabilirdi? 802 00:26:19,689 --> 00:26:21,635 >> HEDEF KİTLE: [duyulamaz]. 803 00:26:21,635 --> 00:26:22,510 DAVID J. MALAN: Evet. 804 00:26:22,510 --> 00:26:24,620 Yani orada bazı büyük sezgi var. 805 00:26:24,620 --> 00:26:28,020 İyi şeyler bugüne kadar ne gibi görünüyor Biz bölmek bilgisayar bilimi 806 00:26:28,020 --> 00:26:30,832 ve bölme sorununu ele o yarı yarıya ve yarım. 807 00:26:30,832 --> 00:26:32,540 Ve böylece gerçekten biz Bunu yapmak için başlayabilir. 808 00:26:32,540 --> 00:26:35,754 Ve aslında, bu, olması biz edeceğiz gidiyor Henüz, bizim en iyi çözümlerden birini görüyorum. 809 00:26:35,754 --> 00:26:37,420 Ama uzun zaman önce geri buna gelelim. 810 00:26:37,420 --> 00:26:40,500 Aslında, biz yapacağız Bir süre sonra bu hafta söyledi. 811 00:26:40,500 --> 00:26:42,180 Bunu çözmek için başka ne yapabilir? 812 00:26:42,180 --> 00:26:44,647 Yani burada herkes içinde rastgele düzen. 813 00:26:44,647 --> 00:26:45,230 Biliyor musun? 814 00:26:45,230 --> 00:26:48,320 Aksine ileri ve geri gitmek yerine, ileri ve geri, ileri ve geri 815 00:26:48,320 --> 00:26:50,624 Her zaman, bu gibi hissediyor Ben yürüyen bir sürü yapıyorum. 816 00:26:50,624 --> 00:26:52,790 Neden sadece başlamak değil Listenin başında, 817 00:26:52,790 --> 00:26:54,960 ve sadece ait dört koydu? 818 00:26:54,960 --> 00:26:59,680 Bu yüzden bana şu an için varsayalım o Benim liste sadece bu ilk unsurdur. 819 00:26:59,680 --> 00:27:04,937 Dört zamanında şu anda sıralanır, eğer umurumda tüm herşey burda mı? 820 00:27:04,937 --> 00:27:06,520 Bu tür trivially doğrudur, değil mi? 821 00:27:06,520 --> 00:27:10,000 Tek sayı içeren listede, ve benzeri bu sayı, dört Açıkçası sıralanır. 822 00:27:10,000 --> 00:27:13,070 >> Bu yüzden bana şart izin bu liste sıralanır. 823 00:27:13,070 --> 00:27:15,090 Ama şimdi bu listenin geri kalanını var. 824 00:27:15,090 --> 00:27:17,240 Yani şimdi, ben iki karşılaşıyoruz. 825 00:27:17,240 --> 00:27:21,690 Nerede Açıkçası iki yapar Dört göre aittir? 826 00:27:21,690 --> 00:27:22,580 Dört önce. 827 00:27:22,580 --> 00:27:23,862 Yani burada ne yapabilirim? 828 00:27:23,862 --> 00:27:24,820 Yeniden, isminiz nedir? 829 00:27:24,820 --> 00:27:25,090 >> JOSEPH: Joseph. 830 00:27:25,090 --> 00:27:26,030 >> DAVID J. MALAN: Joseph, Eğer geri adım eğer 831 00:27:26,030 --> 00:27:27,790 senin numarası ile sadece bir an için. 832 00:27:27,790 --> 00:27:31,130 Ve Stefan burada şimdi ne yapmalıyım? 833 00:27:31,130 --> 00:27:33,720 Şuraya Stefan vardiya edelim. 834 00:27:33,720 --> 00:27:35,520 Ve şimdi, Yusuf buraya gelsin. 835 00:27:35,520 --> 00:27:39,660 Ve şimdi, bana iddia izin Burada her şey sıralanır. 836 00:27:39,660 --> 00:27:42,474 Yani, benzer bir sonuç, ama temelde farklı bir yaklaşım. 837 00:27:42,474 --> 00:27:44,140 Ben bile aşağı orada ne bakmadım. 838 00:27:44,140 --> 00:27:46,310 Ben sadece elemanlar alarak devam onlar bana teslim konum olarak, 839 00:27:46,310 --> 00:27:47,240 ve onlarla anlaşma. 840 00:27:47,240 --> 00:27:48,330 >> Yani şimdi, ben altı numarayı görüyorum. 841 00:27:48,330 --> 00:27:51,110 Nerede altıncı aittir? 842 00:27:51,110 --> 00:27:53,250 Biz iki, dört, altı var. 843 00:27:53,250 --> 00:27:54,800 Tam o şimdi nerede. 844 00:27:54,800 --> 00:27:57,750 Yani şimdi en yalnız bırakalım ve Listenin bu kısmı iddia 845 00:27:57,750 --> 00:27:58,772 Şimdi sıralanır. 846 00:27:58,772 --> 00:28:01,230 Ve böylece, bu temelde hissediyor Bu farklı ben sadece 847 00:28:01,230 --> 00:28:05,230 Burada listede üzerinden hareket doğrusal ve asla geri katlama ediyorum. 848 00:28:05,230 --> 00:28:05,730 Evet. 849 00:28:05,730 --> 00:28:06,230 Pekala. 850 00:28:06,230 --> 00:28:08,190 Yani sekiz, nereye ait? 851 00:28:08,190 --> 00:28:08,730 Tam burada. 852 00:28:08,730 --> 00:28:09,310 Mükemmel. 853 00:28:09,310 --> 00:28:10,210 Yani şimdi, bir. 854 00:28:10,210 --> 00:28:10,900 Ah ah. 855 00:28:10,900 --> 00:28:13,010 Bu gibi hissediyor bu pahalı olacak. 856 00:28:13,010 --> 00:28:15,690 Şimdi, daha önceki algoritimde olduğu, Ben sadece insanları takas. 857 00:28:15,690 --> 00:28:18,648 Yani ben onu tüm yol koymak olabilir başlangıcı, ama sonra Joseph taşındı. 858 00:28:18,648 --> 00:28:21,450 Ama şimdi, Joseph taşırsanız Ne yanlış olacak? 859 00:28:21,450 --> 00:28:24,250 >> Şimdi, ben tür Birkaç gün önce undone-- ettik ileri ve daha sonra bir adım atmış 860 00:28:24,250 --> 00:28:26,300 bir adım geri, çünkü şimdi Yusuf bozuk olacaktır. 861 00:28:26,300 --> 00:28:26,830 Yani bu yapalım. 862 00:28:26,830 --> 00:28:29,150 Eğer bir numara sürebilir ve sadece bir an için geri adım. 863 00:28:29,150 --> 00:28:30,490 Nasıl put-- ne Adını bir daha? 864 00:28:30,490 --> 00:28:31,130 >> ANNAN: Annan. 865 00:28:31,130 --> 00:28:32,610 >> DAVID J. MALAN: yerine Annan? 866 00:28:32,610 --> 00:28:36,091 Ne saygı ile gerçekleşmesi gerekiyor İki, dört, altı ve sekiz? 867 00:28:36,091 --> 00:28:37,570 Hepsi kaydırmaya gerek. 868 00:28:37,570 --> 00:28:42,590 Sekiz Yani eğer vardiya istiyorum Önce, sonra altı, daha sonra dört, daha sonra iki. 869 00:28:42,590 --> 00:28:45,380 Ve sonra Annan, eğer ediyorum İyi, buraya gelmek istiyor. 870 00:28:45,380 --> 00:28:47,760 Ama burada, biz sadece ettik tür bir bedel ödedi 871 00:28:47,760 --> 00:28:49,510 algoritması farklı bir noktada. 872 00:28:49,510 --> 00:28:52,550 Seçimi ile son kez Oysa sıralama ve hatta kabarcık sıralama, 873 00:28:52,550 --> 00:28:54,700 Ben geri yürüyorum ve ileri, geri ve ileri, 874 00:28:54,700 --> 00:28:58,360 kesinlikle hangi yukarı ekliyor Zaman bilge ve tam anlamıyla kademeli. 875 00:28:58,360 --> 00:29:00,660 >> Yerleştirme sıralama, ilk başta bu gibi bakışta görünüyor 876 00:29:00,660 --> 00:29:05,150 süper akıllı, ki ben sadece Yavaş, artan ilerleme, 877 00:29:05,150 --> 00:29:07,120 ama ben ileri geri bu gitmiyorum. 878 00:29:07,120 --> 00:29:09,410 Ama birisi gerçekten ise Sipariş, haber dışında 879 00:29:09,410 --> 00:29:10,840 Ben sadece yapmak zorunda çalışmalarının tüm. 880 00:29:10,840 --> 00:29:14,750 Ben listenin yarısını taşımak zorunda Sadece bir numara yer açmak için. 881 00:29:14,750 --> 00:29:16,790 Yani aynı miktarda bulunuyor çalışma bugüne kadar bu 882 00:29:16,790 --> 00:29:18,690 işin sadece farklı bir tür, hissediyor. 883 00:29:18,690 --> 00:29:19,370 >> Devam edelim. 884 00:29:19,370 --> 00:29:22,657 Yani şimdi herkesin biliyoruz bir ve sekiz arasında sıralanır. 885 00:29:22,657 --> 00:29:23,740 Burada, sayı üç var. 886 00:29:23,740 --> 00:29:25,864 Eğer almak isterseniz Üç numaralı, geriye bir tane adım. 887 00:29:25,864 --> 00:29:28,260 Peki siz yapmak gerekiyor? 888 00:29:28,260 --> 00:29:28,760 Evet. 889 00:29:28,760 --> 00:29:33,070 Böylece başka bir, iki, üç adım var. 890 00:29:33,070 --> 00:29:36,010 Sadece maliyet zaman üç ünite Bana üç şimdi sığabilecek şekilde. 891 00:29:36,010 --> 00:29:37,460 Son olarak, yedi. 892 00:29:37,460 --> 00:29:39,730 >> En go ahead ve atalım Bir adım geri alıyorum. 893 00:29:39,730 --> 00:29:42,780 Bu sadece bize mal olacak Bir zamanlar birimi, ama bu sorun değil. 894 00:29:42,780 --> 00:29:44,170 Ve şimdi, beş üyenin gidiyor Biraz daha pahalı olabilir. 895 00:29:44,170 --> 00:29:45,340 Eğer geri adım istiyorsanız. 896 00:29:45,340 --> 00:29:48,380 Biz, sekiz taşımak gerekir yedi ve altı. 897 00:29:48,380 --> 00:29:50,749 Ve sonra herkes artık sıralanır. 898 00:29:50,749 --> 00:29:52,290 Yani burada bizim gönüllülere büyük bir el. 899 00:29:52,290 --> 00:29:53,554 Çok teşekkür ederim. 900 00:29:53,554 --> 00:29:56,220 >> [Alkış] 901 00:29:56,220 --> 00:29:56,860 >> Hepinize teşekkür ederim. 902 00:29:56,860 --> 00:29:57,520 Hepinize teşekkür ederim. 903 00:29:57,520 --> 00:30:02,940 Yani şimdi sadece nasıl görelim bunların hepsi pahalıya mal oldu. 904 00:30:02,940 --> 00:30:06,210 En belki düşünelim Bu en basit kabarcık sıralama. 905 00:30:06,210 --> 00:30:09,950 Ve ben, çünkü basit söylemek Sadece tarafından iştahla bunu çözebilir 906 00:30:09,950 --> 00:30:11,660 Burada ikili sorunu çözmek. 907 00:30:11,660 --> 00:30:13,720 İkili sorunu çözmek Burada, tekrar ve tekrar 908 00:30:13,720 --> 00:30:17,680 ve yine, çok sayıda tekrar senin gibi kat aslında gerekir. 909 00:30:17,680 --> 00:30:21,050 >> Bu yüzden çıkıyor Bir kabarcık sıralama ile, iyi, 910 00:30:21,050 --> 00:30:25,820 kaç adım Ben almak gerekiyor Bu algoritma ilk geçiş? 911 00:30:25,820 --> 00:30:30,850 Ben, en tane see-- izin take-- olabilir iki, üç, dört, beş, altı, yedi. 912 00:30:30,850 --> 00:30:32,190 Ve burada sekiz elemanları var. 913 00:30:32,190 --> 00:30:35,280 Yani n eksi 1 adımların gibi Listenin başından almak 914 00:30:35,280 --> 00:30:36,380 Listenin sonuna. 915 00:30:36,380 --> 00:30:41,350 >> Ama seçim sıralama ile, ben hatırlamak Tekrar öğelerinin seçilmesinden 916 00:30:41,350 --> 00:30:44,590 ve yine o, en küçük bulunuyor Ben, bir yerde koyuyorum 917 00:30:44,590 --> 00:30:46,616 ama sonra değilim Yine arkamda seyir. 918 00:30:46,616 --> 00:30:49,490 Bu yüzden biraz daha net olduğunu düşünüyorum sonra ilk defa, ben belki 919 00:30:49,490 --> 00:30:52,680 Tüm n eksi 1 adımları almak zorunda En küçük eleman bulmak için. 920 00:30:52,680 --> 00:30:55,920 Sonra yere koyun ve ben Daha önce burada kim tahliye. 921 00:30:55,920 --> 00:30:57,500 >> Ama sonra gerek yok Bu elemanın bakarak tutmak, 922 00:30:57,500 --> 00:30:59,040 Biliyorum çünkü bu Zaten küçük. 923 00:30:59,040 --> 00:31:01,581 Yani şimdi, ben sadece yedi bakabilirsiniz elementler, ardından altı elemanları, 924 00:31:01,581 --> 00:31:03,290 daha sonra beş element, dört unsur. 925 00:31:03,290 --> 00:31:06,900 Ve böylece matematiksel n ise elemanları veya sayıların sayısı 926 00:31:06,900 --> 00:31:11,990 biz başladı, hayal edebileceğiniz Bu n eksi 1 ile aynı olduğu, 927 00:31:11,990 --> 00:31:14,250 artı n eksi 2 adım artı n eksi 3 adım 928 00:31:14,250 --> 00:31:16,780 artı n eksi 4 adım, tüm yol aşağı sadece bir adım. 929 00:31:16,780 --> 00:31:18,160 Ve benim son kişi olduğumu. 930 00:31:18,160 --> 00:31:20,650 >> Ve bir sürü olduğunu hatırlayacak olursak kitaplarını ya da matematik kitaplarını istatistik 931 00:31:20,650 --> 00:31:24,730 üzerinde bu formüllere sahiptir Geri ciltli veya onların önünde, 932 00:31:24,730 --> 00:31:27,690 Bu serinin çıkıyor daha basit ifade edilebilir 933 00:31:27,690 --> 00:31:28,857 n kere n olarak eksi 2 üzerinde 1. 934 00:31:28,857 --> 00:31:31,273 Bu değil Ve eğer gayet Aklını ön planda. 935 00:31:31,273 --> 00:31:32,420 Ama bu gerçekten doğrudur. 936 00:31:32,420 --> 00:31:34,449 İşte o yazı sadece basit bir yolu var. 937 00:31:34,449 --> 00:31:36,240 Ve sonra düşünüyorsanız geri dereceli okula, 938 00:31:36,240 --> 00:31:38,698 Sadece çarparak başladığınızda İşlerin, elbette bu, 939 00:31:38,698 --> 00:31:41,820 Sadece n karesi eksi n 2'ye bölünür. 940 00:31:41,820 --> 00:31:44,772 Yaptığım tüm genişletmek olduğunu Orada ifadeler. 941 00:31:44,772 --> 00:31:46,730 Ve o yüzden bu yeniden izin biraz daha farklı. 942 00:31:46,730 --> 00:31:49,780 Bu n, 2 eksi n / 2 bölü var. 943 00:31:49,780 --> 00:31:53,270 >> Yani yine, ben sadece tür uygulayarak kulüpler Bazı aritmetik orada yönetir. 944 00:31:53,270 --> 00:31:57,140 Ama şimdi dikkat edin büyük terim Bu ifadede, tabiri caizse, 945 00:31:57,140 --> 00:31:58,540 n karesi olmasıdır. 946 00:31:58,540 --> 00:32:02,910 Yani evet, n kare var 2 eksi n / 2 ile ayrıldı. 947 00:32:02,910 --> 00:32:05,080 >> Ancak, genel olarak, n ise, Büyük bir değer olacak, 948 00:32:05,080 --> 00:32:08,740 O n karesi iddia gidiyorum baskın faktör olacak. 949 00:32:08,740 --> 00:32:10,490 Sadece olacak Daha büyük bir katkıda 950 00:32:10,490 --> 00:32:12,877 n / 2 den adım sayısı kadar. 951 00:32:12,877 --> 00:32:13,960 Yani bu ne demek istiyorsunuz? 952 00:32:13,960 --> 00:32:16,795 Hatta, en basit bir örnek deneyelim matematik biraz büyük olur gerçi. 953 00:32:16,795 --> 00:32:20,210 >> Bu yüzden, 1 milyon kişi vardı varsayalım evre, ya da 1 milyon şeylere 954 00:32:20,210 --> 00:32:21,320 Biz sıralamak istiyorum. 955 00:32:21,320 --> 00:32:23,730 En bir milyon fiş edelim tam olarak bu formüle 956 00:32:23,730 --> 00:32:27,230 bu toplam alır kaç adım görmek için diyelim kullanılarak milyon unsurları sıralamak, 957 00:32:27,230 --> 00:32:28,560 Seçim sıralama. 958 00:32:28,560 --> 00:32:30,760 >> Bu yüzden daha önce olduğu gibi aynı formülü olurdu. 959 00:32:30,760 --> 00:32:34,120 Ben olsun ki ben, bir milyon fiş ediyorum Bir milyon 2 bölü 960 00:32:34,120 --> 00:32:35,990 eksi bir milyon 2'ye bölünür. 961 00:32:35,990 --> 00:32:40,180 Ben önceden bu matematik yaparsanız Burada biz 500 milyar var 962 00:32:40,180 --> 00:32:47,460 Eksi 500,000, burada , 499999500000 bize verir 963 00:32:47,460 --> 00:32:49,270 hangi oldukça lanetlemek büyük. 964 00:32:49,270 --> 00:32:54,370 >> Aslında, şimdi karşılaştırırsanız 499 milyar 999 milyon 965 00:32:54,370 --> 00:33:01,210 Bizim özgün değer karşı 500.000, 500 milyar, o kadar lanet yakındır. 966 00:33:01,210 --> 00:33:06,850 Sağ? n, 2 verir bölü us-- doğrusu, burada n, 2 bölü 967 00:33:06,850 --> 00:33:08,370 Bize 500 milyar verdi. 968 00:33:08,370 --> 00:33:13,510 Bu oldukça lanetlemek yakın 499,999,500,000 için 969 00:33:13,510 --> 00:33:17,970 kapalı 500.000 çıkarılarak demek olan ya da daha genel olarak, kapalı çıkarılarak 970 00:33:17,970 --> 00:33:20,010 n değil, gerçekten büyük bir anlaşma karesi. 971 00:33:20,010 --> 00:33:22,490 Bu hale n karesi sayılar gerçekten çok hızlı büyür. 972 00:33:22,490 --> 00:33:25,790 >> Şimdi, bu sadece önemli ölçüde biz olarak, bilgisayar bilim adamları olarak, 973 00:33:25,790 --> 00:33:29,350 genellikle çok umurumda gidiş değildir Bu formüllerin nüansları hakkında 974 00:33:29,350 --> 00:33:31,400 ve tam olarak ne Kesin cevaplar. 975 00:33:31,400 --> 00:33:33,390 Biz sadece, sen biliyor musun bakım? 976 00:33:33,390 --> 00:33:37,810 Günün sonunda, bu formül karesi n sırasına olduğunu. 977 00:33:37,810 --> 00:33:39,350 >> Evet, biz orada 2'ye bölünüp ediyoruz. 978 00:33:39,350 --> 00:33:41,360 Evet, biz kapalı n eksi 2 çıkarılarak ediyoruz. 979 00:33:41,360 --> 00:33:46,860 Ama günün sonunda, dönem Bu gerçekten bizi incitiyor ve bizi maliyeti 980 00:33:46,860 --> 00:33:48,995 adımları çok o kare bir terimdir. 981 00:33:48,995 --> 00:33:51,370 Ve böylece ne bir bilgisayar bilimcisi Genellikle yapacak 982 00:33:51,370 --> 00:33:54,160 bunların hepsi görmezden olduğunu Daha küçük mertebeden terimler, 983 00:33:54,160 --> 00:33:56,900 ve sadece bir bakmak maliyet en katkıda bulunur. 984 00:33:56,900 --> 00:34:00,530 >> Ve bu, çünkü biz, güzel, Şimdi çok daha fazla genellik konuşmak 985 00:34:00,530 --> 00:34:02,470 algoritmalar hakkında ve bunları karşılaştırabilirsiniz. 986 00:34:02,470 --> 00:34:04,550 Ben olduğumu ve aslında Bu O kullanarak kasıtlı olduğunu. 987 00:34:04,550 --> 00:34:06,680 Ben sipariş üzerine derken , ben özellikle ben 988 00:34:06,680 --> 00:34:09,560 şey atıfta Büyük O. Ve büyük Ey denilen 989 00:34:09,560 --> 00:34:14,090 bir gösterim olduğu bir bilgisayar bilim adamı tanımlamak için kullandığı 990 00:34:14,090 --> 00:34:16,710 Bir üst şeye bağlı. 991 00:34:16,710 --> 00:34:21,150 >> Eğer bir algoritma olduğunu söylemek Yani eğer n karesi büyük O ise, 992 00:34:21,150 --> 00:34:23,380 Ben önerildiği gibi sadece an önce bu aracı 993 00:34:23,380 --> 00:34:27,710 onun çalışan açısından zaman ya da verimliliği, 994 00:34:27,710 --> 00:34:30,090 Arızalı alır n adımları karesi. 995 00:34:30,090 --> 00:34:31,420 Belki daha az, belki daha fazla. 996 00:34:31,420 --> 00:34:33,435 Ama n emri karesi üzerinde bulunuyor. 997 00:34:33,435 --> 00:34:34,560 Ve bu üst sınır var. 998 00:34:34,560 --> 00:34:36,530 Bu olacak değil Bundan daha acı. 999 00:34:36,530 --> 00:34:40,800 Bu n kuşbaşı olacak, ya da 2 değil n veya çok daha büyük bir şey. 1000 00:34:40,800 --> 00:34:43,800 Bu sınır bir üst olduğunu ne olursa olsun o maliyetidir. 1001 00:34:43,800 --> 00:34:46,150 Yani, haydi verilen Sadece birkaç örnek düşünün. 1002 00:34:46,150 --> 00:34:49,820 Ve bu sadece bir sonlu listesi çok yaygın çalışan süreleri 1003 00:34:49,820 --> 00:34:52,870 olması gerekiyordu algoritmalar için biz ettik bazı şeyleri tasvir 1004 00:34:52,870 --> 00:34:53,600 Zaten görüldü. 1005 00:34:53,600 --> 00:34:58,060 >> Örneğin, dava içinde So Seçim sıralama, ben burada ne yapıyorum iddia 1006 00:34:58,060 --> 00:35:02,250 bu seçim sırala koşu olduğunu Zaman n sırası kareli üzerindedir. 1007 00:35:02,250 --> 00:35:06,260 En kötü durumda, ben gidiyorum Burada rasgele sayılar bir sürü. 1008 00:35:06,260 --> 00:35:08,600 Ve biz matematiksel gördüğümüz gibi, Ben yürümeye devam eğer 1009 00:35:08,600 --> 00:35:11,310 Liste boyunca yoluyla Liste, en küçük bir sonraki seçme 1010 00:35:11,310 --> 00:35:14,410 Tekrar ve tekrar eleman, ben ise Aslında tüm adımları yazmak 1011 00:35:14,410 --> 00:35:18,750 Ben formulaically önerildiği gibi ben alıyorum önce, bu kare n emriyle var 1012 00:35:18,750 --> 00:35:20,370 Ben alıyorum adımlar. 1013 00:35:20,370 --> 00:35:24,520 >> Ve o balonu çıkıyor sıralama ve yerleştirme sıralama 1014 00:35:24,520 --> 00:35:27,370 En kötü durumda gibi yavaştır. 1015 00:35:27,370 --> 00:35:32,040 Örneğin, düşünün, ekleme sıralama, Biz ele en son algoritma, 1016 00:35:32,040 --> 00:35:35,500 hangi bize elemanın bakmak vardı ait olduğu yere ve sonra takın. 1017 00:35:35,500 --> 00:35:38,720 Ve sonra bir sonraki elemanın baktı, ait olduğu yere ve onu takılı. 1018 00:35:38,720 --> 00:35:40,990 >> Yani mümkün olan en iyi senaryoyu düşünün. 1019 00:35:40,990 --> 00:35:45,590 Ben gönüllüler sıraya vardı varsayalım kelimenin tam anlamıyla böyle, sekize kadar biri 1020 00:35:45,590 --> 00:35:47,440 Zaten sıralanır. 1021 00:35:47,440 --> 00:35:51,300 Ekleme sıralama kaç adım sekiz kişi sıralamak için sürecekse, 1022 00:35:51,300 --> 00:35:55,640 onlar sahnede gelirseniz Bu gibi bakıyor? 1023 00:35:55,640 --> 00:35:57,410 >> Sekiz kişi zaten sıralanır. 1024 00:35:57,410 --> 00:35:58,760 Ve ben ekleme sıralama kullanmak. 1025 00:35:58,760 --> 00:36:02,180 Algoritmalar Bu son. 1026 00:36:02,180 --> 00:36:03,640 Peki, gerçek hızlıca reenact edelim. 1027 00:36:03,640 --> 00:36:05,504 Ben buradan başlayın eğer Yani, bir bakın. 1028 00:36:05,504 --> 00:36:06,420 Nerede biri aittir? 1029 00:36:06,420 --> 00:36:07,730 Tam burada aittir. 1030 00:36:07,730 --> 00:36:08,330 Ben iki görüyorum. 1031 00:36:08,330 --> 00:36:09,660 Nerede iki aittir? 1032 00:36:09,660 --> 00:36:10,260 Tam burada. 1033 00:36:10,260 --> 00:36:10,900 Ben üç görüyorum. 1034 00:36:10,900 --> 00:36:11,920 Nerede üç aittir? 1035 00:36:11,920 --> 00:36:12,480 Tam burada. 1036 00:36:12,480 --> 00:36:13,100 >> Ben dört görüyorum. 1037 00:36:13,100 --> 00:36:13,600 Tam burada. 1038 00:36:13,600 --> 00:36:15,660 Beş, altı, yedi, sekiz. 1039 00:36:15,660 --> 00:36:17,320 Kendimi tekrarlamak için bir neden yok. 1040 00:36:17,320 --> 00:36:21,260 Ve böylece, kaç adım n'nin açısından mı? 1041 00:36:21,260 --> 00:36:23,870 Bu n sırasına bulunuyor adımlar, değil mi? n eksi 1. 1042 00:36:23,870 --> 00:36:27,567 Ama doğrusal sayı aldı adımlar ve şimdi ben bittim. 1043 00:36:27,567 --> 00:36:28,900 Yani olsa da, en iyi durumda değil. 1044 00:36:28,900 --> 00:36:29,983 Ne kötü durumda ne olacak? 1045 00:36:29,983 --> 00:36:32,730 Ne sekiz, oraya vardı yedi, oraya vardı 1046 00:36:32,730 --> 00:36:35,840 ve bir ve iki yüzden, buraya edildi Liste gerçekten tersine olduğunu? 1047 00:36:35,840 --> 00:36:38,300 >> Peki, gerçekten olur Bu sayı ne olur? 1048 00:36:38,300 --> 00:36:41,300 Ve biz örneklerden sadece bir çift yapacağız. 1049 00:36:41,300 --> 00:36:49,300 Ne sayı sekiz, gerçekten, eğer burada ve number-- hoppala. 1050 00:36:49,300 --> 00:36:52,660 1051 00:36:52,660 --> 00:36:56,430 Peki, eğer gerçekten, sayı Sekiz, buraya tüm yol 1052 00:36:56,430 --> 00:36:57,790 ve ben ekleme sıralama kullanıyorum? 1053 00:36:57,790 --> 00:36:58,290 >> TAMAM. 1054 00:36:58,290 --> 00:37:00,280 Ben yerinde var şu anda iddia. 1055 00:37:00,280 --> 00:37:03,152 Ama şimdi, yedi-- nereye yedi nereye gidiyor? 1056 00:37:03,152 --> 00:37:04,360 Tabii ki, burada gider. 1057 00:37:04,360 --> 00:37:06,760 Yani tek bir yerde sekiz taşımak zorunda. 1058 00:37:06,760 --> 00:37:08,554 Şimdi altı, nereye gidiyor? 1059 00:37:08,554 --> 00:37:09,220 Peki, tamam. 1060 00:37:09,220 --> 00:37:13,150 Şimdi, ben üzerinden sekiz taşımak zorunda Bir yerde, bir yerde yedi 1061 00:37:13,150 --> 00:37:14,440 ve sonra altı aşağı plop. 1062 00:37:14,440 --> 00:37:16,870 >> Böylece ilk kez, maliyet şeyleri düzeltmek için bana bir adım, 1063 00:37:16,870 --> 00:37:18,570 o şeyleri düzeltmek için bana iki adım mal oldu. 1064 00:37:18,570 --> 00:37:20,370 Kaç adım düzeltmek için almaya gidiyor 1065 00:37:20,370 --> 00:37:22,720 doğru yerde beş koymak şeyler? 1066 00:37:22,720 --> 00:37:23,340 Üç. 1067 00:37:23,340 --> 00:37:29,520 Şimdi ben zorunda çünkü bir iki, üç taşıyın. 1068 00:37:29,520 --> 00:37:32,430 Kaç adımlar alacak doğru yerde dört koymak için? 1069 00:37:32,430 --> 00:37:36,040 4 artı 5 artı 6, artı 7. 1070 00:37:36,040 --> 00:37:40,260 >> Ve bu yüzden matematiksel özdeş olduğunu Biz seçim sıralama için deyimiyle. 1071 00:37:40,260 --> 00:37:42,130 Bu dizi var sadece artıyor. 1072 00:37:42,130 --> 00:37:45,650 1 artı 2 artı 3 artı 4, ya da tersine, 7 artı 6 1073 00:37:45,650 --> 00:37:52,610 artı 5 artı 4 bugünün kadar ekler n sırasına göre amaçları karesi. 1074 00:37:52,610 --> 00:37:57,640 >> Yani ben de şart izin kabarcık sıralama n karesi de geçerlidir. 1075 00:37:57,640 --> 00:38:01,340 Çünkü kabarcık sıralama, her biri zaman, listede geçmesi 1076 00:38:01,340 --> 00:38:03,100 Ben kabaca kaç adım alıyorum? 1077 00:38:03,100 --> 00:38:06,260 Her zaman tam anlamıyla oradan oraya yürümek? 1078 00:38:06,260 --> 00:38:07,960 Kabaca n adımlar. 1079 00:38:07,960 --> 00:38:12,650 Ama kaç kere olabilir listeye geçmesi gerekir? 1080 00:38:12,650 --> 00:38:13,920 >> Eh, kabaca n zaman. 1081 00:38:13,920 --> 00:38:15,680 Belki n eksi 1, ama kabaca n kere. 1082 00:38:15,680 --> 00:38:16,430 Peki, neden? 1083 00:38:16,430 --> 00:38:19,560 Peki, kabarcık sıralama ile, eğer Biz kabarcık sıralama ile başlar 1084 00:38:19,560 --> 00:38:23,570 olası en kötü listesinde ile Yine tamamen durum 1085 00:38:23,570 --> 00:38:25,550 geriye, ne olacak ki? 1086 00:38:25,550 --> 00:38:28,830 Ben listede geçmesi ve sayı kimse orada tüm yol aittir. 1087 00:38:28,830 --> 00:38:33,280 >> Ama kabarcık sıralama ile, ne kadar bir tane yok Liste boyunca benim ilk geçişte hareket? 1088 00:38:33,280 --> 00:38:36,620 Kaç noktalar o olsun Doğru yere yakın? 1089 00:38:36,620 --> 00:38:37,240 Sadece bir. 1090 00:38:37,240 --> 00:38:40,281 Yani bu yoluyla eğer tür sebebi, Bu algoritma sayesinde her zaman, 1091 00:38:40,281 --> 00:38:41,880 David'in alarak kabaca n adımlar. 1092 00:38:41,880 --> 00:38:44,940 Ama kaç geçer Liste öyle aracılığıyla 1093 00:38:44,940 --> 00:38:49,060 kabarcık biri için almaya gidiyor ait olduğu sola? 1094 00:38:49,060 --> 00:38:51,840 >> O, böyle hareket var n alanlarda bu şekilde. 1095 00:38:51,840 --> 00:38:57,960 Dolayısıyla, sadece listenin sıralama yapmak için, Ben ileri geri n kez yürümek gerekiyor. 1096 00:38:57,960 --> 00:39:01,540 Ve her seferinde, ben n elemanlı bakıyor. 1097 00:39:01,540 --> 00:39:05,410 Yani üzerinde n şeyler n kez yapmak n emri karesi. 1098 00:39:05,410 --> 00:39:07,220 >> Şimdi, biz bazı göreceğiz şort o 1099 00:39:07,220 --> 00:39:10,440 CS50 sonraki sorun gömülü Bunlara, başka bir yaklaşım ayarlamak, 1100 00:39:10,440 --> 00:39:13,490 ama şimdi, Sadece düşünelim diğer bazı çalışma süreleri, 1101 00:39:13,490 --> 00:39:16,840 Özellikle sıralama olanlar alırsak zaman biraz batmaya. 1102 00:39:16,840 --> 00:39:21,790 Ne biz zaten gördüğümüz bir algoritma var Bu n adımlarının sipariş alır? 1103 00:39:21,790 --> 00:39:27,560 >> Doğrusal bir numara almalı neler biz bugüne kadar gördüğüm adımlarını? 1104 00:39:27,560 --> 00:39:29,350 Bu da ne? 1105 00:39:29,350 --> 00:39:30,480 Telefon rehberi arama. 1106 00:39:30,480 --> 00:39:31,390 İlk algoritma. 1107 00:39:31,390 --> 00:39:31,560 Sağ? 1108 00:39:31,560 --> 00:39:33,650 Biz doğrusal konum nerede Mike Smith arıyor? 1109 00:39:33,650 --> 00:39:34,150 Gerçekten. 1110 00:39:34,150 --> 00:39:37,180 Haftanın sıfır, ben başladığımda Bir seferde bir sayfa açtığımı, 1111 00:39:37,180 --> 00:39:40,095 ve hatta bu tür olduğunu söyledi doğrusal bir duygu algoritması, 1112 00:39:40,095 --> 00:39:42,720 ve biz o resim vardı Düz kırmızı çizgi ile yönetim kurulu 1113 00:39:42,720 --> 00:39:44,678 ve düz sarı çizgi, o gerçekten vardı 1114 00:39:44,678 --> 00:39:46,810 n büyük O olan algoritmaları. 1115 00:39:46,810 --> 00:39:50,680 >> Bir telefonda Mike Smith'i bulmak Çünkü En kötü durumda n sayfalarının kitabı, 1116 00:39:50,680 --> 00:39:52,422 Beni n adımlar olabilir. 1117 00:39:52,422 --> 00:39:53,630 Yoklama alma konusunda ne olacak? 1118 00:39:53,630 --> 00:39:55,790 Bir iki üç dört beş altı. 1119 00:39:55,790 --> 00:39:59,420 Bu çalışma süresi nedir yoklama almak için algoritma? 1120 00:39:59,420 --> 00:40:03,070 Çünkü teoride n Big O, ben odadaki herkesi işaret var. 1121 00:40:03,070 --> 00:40:05,861 >> Şimdi bir kenara olarak ne hakkında Haftanın sıfırdan diğer optimizasyon? 1122 00:40:05,861 --> 00:40:08,117 İki, dört, altı, sekiz, 10, 12. 1123 00:40:08,117 --> 00:40:10,200 Bir bilgisayar bilimcisi olur gerçekleştirmek bir dakika bekleyin, 1124 00:40:10,200 --> 00:40:12,320 Bu sırasına bulunuyor n, iki aşama ile ayrılır. 1125 00:40:12,320 --> 00:40:12,820 Sağ? 1126 00:40:12,820 --> 00:40:14,444 Ben bir anda iki kişiyi yapıyorum çünkü. 1127 00:40:14,444 --> 00:40:17,015 Ama biz görmezden gidiyoruz Bu alt mertebeden terimler, 1128 00:40:17,015 --> 00:40:19,140 ve biz sadece gidiyoruz 2 ile bölme atmak, 1129 00:40:19,140 --> 00:40:21,830 ve sadece söylemek n büyük Ey de bu algoritma için. 1130 00:40:21,830 --> 00:40:22,760 >> Peki ya bu? 1131 00:40:22,760 --> 00:40:26,170 Biz bunlardan bazıları atlamak, ama ne yapacaksınız n log olan bir algoritma oldu? 1132 00:40:26,170 --> 00:40:29,900 Bu kabaca n adımları log aldı? 1133 00:40:29,900 --> 00:40:30,870 Böl ve fethet. 1134 00:40:30,870 --> 00:40:31,369 Kesinlikle. 1135 00:40:31,369 --> 00:40:33,900 Telefon rehberi örnekteki gibi Haftanın sıfır ve bugün erken saatlerde, 1136 00:40:33,900 --> 00:40:36,191 Nerede biz sorunu bölünmüş Tekrar ve tekrar ve tekrar. 1137 00:40:36,191 --> 00:40:39,070 Biz hafta gemide çekti kavisli yeşil hat olarak sıfır, 1138 00:40:39,070 --> 00:40:41,460 ve biz o gün olduğunu söyledi logaritmik algoritması. 1139 00:40:41,460 --> 00:40:44,970 >> Ve gerçekten de, sayısı adımlar onu bölmek yerine ve fethetmek için gereken, 1140 00:40:44,970 --> 00:40:48,610 veya ikili arama olarak biz başlayacağız Telefon defterinde olduğu gibi, çağırarak, 1141 00:40:48,610 --> 00:40:50,680 günlük ve adımların sırasına olduğunu. 1142 00:40:50,680 --> 00:40:52,470 Ve bu garip biri bir parçasıdır. 1143 00:40:52,470 --> 00:40:54,910 >> Bir adım gerekenlere, veya daha özel olarak 1144 00:40:54,910 --> 00:40:56,240 adımlar sabit sayıda? 1145 00:40:56,240 --> 00:40:58,865 Belki öyle, belki üç var, iki değil, ancak bir bilgisayar bilimcisi sadece 1146 00:40:58,865 --> 00:41:01,423 1 büyük O olarak kolaylaştırır, bazı adımları sabit sayısı. 1147 00:41:01,423 --> 00:41:04,256 Bunu yapabileceğim bir şey neler var adımlar sabit sayıda alır? 1148 00:41:04,256 --> 00:41:08,030 1149 00:41:08,030 --> 00:41:10,930 >> Alkışlar çalışma süresi nedir? 1150 00:41:10,930 --> 00:41:11,920 Sabit zaman. 1151 00:41:11,920 --> 00:41:12,420 Sağ? 1152 00:41:12,420 --> 00:41:15,490 Gibi, çalışma süresi ne sadece birini alır bir şey yapıyor 1153 00:41:15,490 --> 00:41:18,570 operasyon gibi F Hello World yazdırın. 1154 00:41:18,570 --> 00:41:24,110 Yani, sabit zaman olduğu söylenebilir Baskı F az köşe durumda olmadıkça, 1155 00:41:24,110 --> 00:41:28,260 Ne çalışma süresi olabilir baskı F aslında olacak? 1156 00:41:28,260 --> 00:41:28,790 Ve neden? 1157 00:41:28,790 --> 00:41:30,550 Bu durumda n ölçüm nedir? 1158 00:41:30,550 --> 00:41:32,251 >> HEDEF KİTLE: [duyulamaz]. 1159 00:41:32,251 --> 00:41:33,250 DAVID J. MALAN: Kesinlikle. 1160 00:41:33,250 --> 00:41:34,900 Karakter sayısı Biz yazdırmak istiyorum. 1161 00:41:34,900 --> 00:41:36,191 Yani çok bağlam-duyarlı olduğunu. 1162 00:41:36,191 --> 00:41:39,910 Bugün, biz çok odaklanan oldum harfler ve burada gemide sayılar. 1163 00:41:39,910 --> 00:41:43,540 Ama aynı zamanda olabilir gerçek bir dize karakter. 1164 00:41:43,540 --> 00:41:46,420 Başka var dışarı yüzden döner önemsememe başlayacak tedbir, 1165 00:41:46,420 --> 00:41:48,530 ve tam tersi Büyük O, tabiri caizse. 1166 00:41:48,530 --> 00:41:50,120 >> Bu omega notasyonu var. 1167 00:41:50,120 --> 00:41:53,380 Büyük O, ne demek Oysa Üst koşu zamanında bağlı? 1168 00:41:53,380 --> 00:41:55,580 Maksimum, ne kadar zaman bir şey alabilir? 1169 00:41:55,580 --> 00:41:59,250 Omega-- üzgünüm bu geliyor tutar up-- bunun tam tersi olan, 1170 00:41:59,250 --> 00:42:02,960 Bir alt sınır üzerinde bulunuyor bu sayede Zaman şey miktarı alabilir. 1171 00:42:02,960 --> 00:42:10,480 >> So Örneğin, ne bir algoritma var her zaman n karesi adımlar atmaktadır? 1172 00:42:10,480 --> 00:42:15,600 Eh, algoritmaların biri gördüğümüz Bugün Aslında, hem de bu olabilir. 1173 00:42:15,600 --> 00:42:16,720 Seçim sıralama. 1174 00:42:16,720 --> 00:42:18,270 Seçim çeşit çok aptalca. 1175 00:42:18,270 --> 00:42:21,760 Hatta hatta algorithm-- üzgünüm eğer Dizi zaten sıralanır ise, 1176 00:42:21,760 --> 00:42:24,150 Seçim sıralama gidiyor Liste boyunca yürümeye devam 1177 00:42:24,150 --> 00:42:28,907 en küçük olduğundan emin olmak için eleman tekrar ve tekrar ve tekrar. 1178 00:42:28,907 --> 00:42:31,740 Ve sen insanlarda bile seyirci, bir dakika bekleyin biliyoruz, 1179 00:42:31,740 --> 00:42:33,948 Zaten geçti küçük elemanı, bilgisayar 1180 00:42:33,948 --> 00:42:37,300 görünüyor kadar bunu bilmiyor listede tüm yol boyunca. 1181 00:42:37,300 --> 00:42:40,240 Benzer şekilde, bir düşük olduğu bağlanmış de dikkate alınabilir 1182 00:42:40,240 --> 00:42:42,000 Lineer zaman olabilir. 1183 00:42:42,000 --> 00:42:48,260 >> O kadar sürer ne kadar zaman En iyi sıralama n elemanları 1184 00:42:48,260 --> 00:42:52,420 kabarcık sıralama gibi bir şey kullanarak dava? 1185 00:42:52,420 --> 00:42:54,280 Listeniz zaten sıralanır varsayalım. 1186 00:42:54,280 --> 00:42:56,696 Biz kabarcık sıralama alır söyledi n sırası adımları karesi. 1187 00:42:56,696 --> 00:42:59,640 Ama zaten ne sıralanmış eğer? 1188 00:42:59,640 --> 00:43:02,310 Ne sonra fark varsa dizi aracılığıyla tek geçişli 1189 00:43:02,310 --> 00:43:03,540 Bu hiçbir swapları yaptık? 1190 00:43:03,540 --> 00:43:05,970 Eğer geçer fazla yapmaya devam etmek gerekir mi? 1191 00:43:05,970 --> 00:43:06,470 >> Hayır. 1192 00:43:06,470 --> 00:43:10,340 Yani daha düşük bir kabarcık tür üzerinde bağlı doğrusal olduğu söylenebilir. 1193 00:43:10,340 --> 00:43:11,830 N Omega. 1194 00:43:11,830 --> 00:43:14,450 Ve biz bakabilirsiniz Bunların da diğerleri. 1195 00:43:14,450 --> 00:43:17,990 Yani kısaca bir göz atalım Burada sadece bir görselleştirme de 1196 00:43:17,990 --> 00:43:20,790 Bu kendilerini ayırt nasıl çalıştığını görmek için. 1197 00:43:20,790 --> 00:43:24,592 Ben bu işe buraya gitmek için gidiyorum C50 web sitesinde mevcuttur var sayfa, 1198 00:43:24,592 --> 00:43:27,550 ancak çalışma almak için bir acı olacak, denilen bir teknoloji kullandığından beri 1199 00:43:27,550 --> 00:43:30,560 Bir Java uygulamaları, bu gün büyük ölçüde desteklenmeyen, 1200 00:43:30,560 --> 00:43:32,730 En azından Chrome ve bazı başkaları tarafından. 1201 00:43:32,730 --> 00:43:37,070 >> Ve beni go ahead ve bu hız izin yukarı ve neler olup bittiğini açıklar. 1202 00:43:37,070 --> 00:43:40,840 Bu balonun bir gösteri sıralama, ilk algoritma biz baktı. 1203 00:43:40,840 --> 00:43:43,950 Ve o bir görselleştirme her bulunuyor Bu çubukların bir sayıyı temsil eder. 1204 00:43:43,950 --> 00:43:45,710 Büyük bir bar, numara büyük. 1205 00:43:45,710 --> 00:43:47,520 Daha küçük çubuk, numara küçük. 1206 00:43:47,520 --> 00:43:50,353 Ve hatta, görsel ne görebilirsiniz Bu da, süper hızlı gidiyor 1207 00:43:50,353 --> 00:43:53,699 kırmızı çubuk benim gibi olduğunu geri yürüme ve ileri sorunları tespit. 1208 00:43:53,699 --> 00:43:56,740 Sen büyük unsurlar olduğunu görebilirsiniz Gerçekten sağa köpüren vardır, 1209 00:43:56,740 --> 00:43:59,650 ve daha küçük elementler sol köpüren vardır. 1210 00:43:59,650 --> 00:44:01,870 Ve buraya, biz ise aslında daha yakından bakmak, 1211 00:44:01,870 --> 00:44:04,330 biz aslında güvenebilirsiniz karşılaştırmalar ve swap sayısı 1212 00:44:04,330 --> 00:44:05,350 Bu yapılıyordu. 1213 00:44:05,350 --> 00:44:07,360 >> Ama bunun yerine, en bakalım İkinci algoritma at 1214 00:44:07,360 --> 00:44:11,240 biz erken baktı bizim Gönüllüler, seçim sıralama. 1215 00:44:11,240 --> 00:44:13,500 Görme, sahip olduğu bir çok farklı etki. 1216 00:44:13,500 --> 00:44:16,820 Ama içinde, yine çok sezgisel Biz küçük bir sonraki seçerek tutmak 1217 00:44:16,820 --> 00:44:18,660 eleman, ve biz biraz şanslıydık. 1218 00:44:18,660 --> 00:44:20,110 Bu temelde daha hızlı hissetti. 1219 00:44:20,110 --> 00:44:22,840 Ama biz tekrar bu koştum ve yine girdi sürü ile 1220 00:44:22,840 --> 00:44:26,680 Biz gerçekten olduğunu görürdünüz Hala n büyük O'da karesi. 1221 00:44:26,680 --> 00:44:29,920 >> En son birini yapalım Burada, ekleme sıralama, 1222 00:44:29,920 --> 00:44:33,180 hangi üçüncü algoritma oldu Biz ve hatırlama baktı 1223 00:44:33,180 --> 00:44:36,700 bu bir ile ilgilenir olduğunu elemanları, onları karşılaşır olarak, 1224 00:44:36,700 --> 00:44:39,290 ama sonra belki vardiya şeyler üzerinde yer açmak için 1225 00:44:39,290 --> 00:44:41,660 ait oldukları unsurları ekleyerek. 1226 00:44:41,660 --> 00:44:45,330 >> Ve bu da vererek biter son sonuç. Şimdi bunların hepsi üç 1227 00:44:45,330 --> 00:44:46,490 oldukça hızlı hissettim. 1228 00:44:46,490 --> 00:44:48,740 Ve gerçekten de, ben onları koştu oldukça iyi bir klip. 1229 00:44:48,740 --> 00:44:52,510 Ama temelde, hepsi değil oldukça korkunç, dürüst olmak gerekirse. 1230 00:44:52,510 --> 00:44:56,960 Bu algoritmalar, şimdiye kadar n büyük O bu çalışma karesi 1231 00:44:56,960 --> 00:44:59,270 biraz almak Zaman sonunda çalıştırın. 1232 00:44:59,270 --> 00:45:01,920 >> Ve gerçekten de, biz görebilirsiniz ve son olarak bu his 1233 00:45:01,920 --> 00:45:04,090 Bu üçüncü ve son demo yukarı çekerseniz. 1234 00:45:04,090 --> 00:45:05,840 Bu başka bir şeydir O görselleştirme gidiyor 1235 00:45:05,840 --> 00:45:08,500 Soldaki kabarcık sıralama göstermek için, Ortada seçim, sıralama 1236 00:45:08,500 --> 00:45:13,410 ve bir şey, biri bizim El, daha önce önerilen yükseltir 1237 00:45:13,410 --> 00:45:15,020 Sağdaki sıralama birleştirme. 1238 00:45:15,020 --> 00:45:16,937 Bir böl ve fethet Sağdaki stratejisi. 1239 00:45:16,937 --> 00:45:19,520 Ve bu konum, aslında, bu Çarşamba günü bakacağız. 1240 00:45:19,520 --> 00:45:21,990 Ama paralel olarak çalıştırmak için bu zaman izin verin. 1241 00:45:21,990 --> 00:45:26,765 Bu kabaca aynı sayıda var elemanları, hepsi aynı anda çalışan. 1242 00:45:26,765 --> 00:45:30,940 1243 00:45:30,940 --> 00:45:34,440 Seçim vs Kabarcık sıralama Birleştirme çeşit çeşit vs. 1244 00:45:34,440 --> 00:45:36,760 >> Şimdi, hepsi koşuyoruz Aynı anda teoride. 1245 00:45:36,760 --> 00:45:39,830 CPU çalıştığından Aynı hız, ama sen 1246 00:45:39,830 --> 00:45:44,014 Bunun ne kadar sıkıcı hissediyorum çok çabuk olmaya devam, 1247 00:45:44,014 --> 00:45:45,930 ve ne kadar hızlı ne zaman biz hafta biraz enjekte 1248 00:45:45,930 --> 00:45:49,330 Zero algoritmaları can biz şeyleri hızlandırmak. 1249 00:45:49,330 --> 00:45:51,760 >> Ve şimdi karşılaştırmak izin Son bir biçimde bu. 1250 00:45:51,760 --> 00:45:55,710 Ben devam edeceğim CS50 web sitesine, için 1251 00:45:55,710 --> 00:45:59,020 Biz bugün bu son bağlantı var nerede internette birisi 1252 00:45:59,020 --> 00:46:03,960 nazik bir video araya koymak neyin farklı sıralama yakalar 1253 00:46:03,960 --> 00:46:07,510 algoritmaları gibi konuştun. 1254 00:46:07,510 --> 00:46:09,577 Bu ekleme türüdür. 1255 00:46:09,577 --> 00:46:12,072 >> [Bipliyor] 1256 00:46:12,072 --> 00:46:13,070 1257 00:46:13,070 --> 00:46:16,850 >> Bu sayede bir frekans uyguluyorsanız bar bar yüksekliğine dayalı. 1258 00:46:16,850 --> 00:46:19,826 Bu kabarcık tür. 1259 00:46:19,826 --> 00:46:21,822 >> [Eğrilmiş Bipliyor] 1260 00:46:21,822 --> 00:46:33,299 1261 00:46:33,299 --> 00:46:45,774 >> Önümüzdeki o-- yanındaki geliyor yukarı gelecek o-- seçim sıralama, 1262 00:46:45,774 --> 00:46:48,820 Nerede yine biz seçme ediyoruz Bir sonraki en küçük elemanı, 1263 00:46:48,820 --> 00:46:51,820 ve biz o büyüyen görebilirsiniz Soldan sağa. 1264 00:46:51,820 --> 00:47:01,120 1265 00:47:01,120 --> 00:47:04,000 >> Bizim kazanan şimdiye kadar bugün, birleştirmeli sıralama. 1266 00:47:04,000 --> 00:47:09,659 1267 00:47:09,659 --> 00:47:12,450 Bazı şeyleri bölünmesi nasıl dikkat [duyulamaz] yarısı ve dörtte içine. 1268 00:47:12,450 --> 00:47:17,510 1269 00:47:17,510 --> 00:47:21,660 Biz değil Gnome sıralama, hakkında konuştuk ve görsel oluşturur 1270 00:47:21,660 --> 00:47:24,450 ve biraz audally Farklı şekil ve ses. 1271 00:47:24,450 --> 00:47:27,060 1272 00:47:27,060 --> 00:47:30,160 Ileri ve geri gidiyor, şeyleri temizlemek. 1273 00:47:30,160 --> 00:47:32,230 Ayrıca Heapsort check out Bu adamın web sitesinde. 1274 00:47:32,230 --> 00:47:36,100 1275 00:47:36,100 --> 00:47:36,810 >> Ve bu kadar. 1276 00:47:36,810 --> 00:47:38,210 Size yakın zaman göreceksiniz. 1277 00:47:38,210 --> 00:47:42,647 1278 00:47:42,647 --> 00:47:48,334 >> [Whooshing VE MÜZİK] 1279 00:47:48,334 --> 00:50:24,839