1 00:00:00,000 --> 00:00:11,270 2 00:00:11,270 --> 00:00:14,910 >> HOPARLÖR: Bu CS50 Tüm hakkıdır. 3 00:00:14,910 --> 00:00:19,020 Bu haftanın üç sonu ve eğer Eğer zaten avantaj almamış 4 00:00:19,020 --> 00:00:21,790 öğle olacağını biliyorum nerede zamanki gibi bu Cuma 5 00:00:21,790 --> 00:00:25,430 Eğer iyi konuşma keyfini Fire and Ice ve gıda 6 00:00:25,430 --> 00:00:27,980 CS50 en bazı Personel ve sınıf arkadaşları. 7 00:00:27,980 --> 00:00:30,170 Burada bu URL'ye gidin. 8 00:00:30,170 --> 00:00:33,420 >> Şimdi çağırmak, ya olabilir yakında tanımak olabilir, 9 00:00:33,420 --> 00:00:35,970 Burada bu şeyler, hangi sonunda dışarı verilir 10 00:00:35,970 --> 00:00:37,850 Birçok sınıflar için dönem. 11 00:00:37,850 --> 00:00:40,870 Sözde sınav mavi kitaplar, hangi Eğer sınavlara cevaplarınızı yazın. 12 00:00:40,870 --> 00:00:44,240 Şimdi ben burada var 26 gibi Bunların her biri mavi kitaplar, 13 00:00:44,240 --> 00:00:47,580 Z. aracılığıyla bir isim, A yazılır Ve aslında isimler basit, A yönündedir 14 00:00:47,580 --> 00:00:50,490 Z. aracılığıyla Ve biri el bugün gol 15 00:00:50,490 --> 00:00:53,910 ne devam olacak biz hangi Pazartesi günü başladı 16 00:00:53,910 --> 00:00:57,830 çok kod bakarak, ama gerçekten fikirler ve problem çözme bakarak. 17 00:00:57,830 --> 00:01:00,170 Hedeflerinden biri ve Bu dersin vaatleri 18 00:01:00,170 --> 00:01:02,985 Daha fazla düşünmek için size öğretmek için dikkatle, daha metodik, 19 00:01:02,985 --> 00:01:05,400 ve daha verimli sorunları çözmek için. 20 00:01:05,400 --> 00:01:09,526 Ve gerçekten de, gerçekten bunu yapabilirsiniz Hatta bir kod satırı dokunmadan. 21 00:01:09,526 --> 00:01:12,150 Yani filler bir çift var yukarı bugün burada, turuncu ve mavi, 22 00:01:12,150 --> 00:01:15,780 biz bir gönüllü alabilir, belki geriye normalden daha gelen. 23 00:01:15,780 --> 00:01:18,070 Nasıl orada hakkında, aşağı gel. 24 00:01:18,070 --> 00:01:24,180 hedefi için olacak yardım artı burada, bu sınavı yönetmek. 25 00:01:24,180 --> 00:01:24,935 Adınız ne? 26 00:01:24,935 --> 00:01:25,768 >> İZLEYİCİ: Mary Beth. 27 00:01:25,768 --> 00:01:27,560 HOPARLÖR: Mary Beth, yukarı gel. 28 00:01:27,560 --> 00:01:29,560 Senin için burada mikrofonu alayım. 29 00:01:29,560 --> 00:01:32,172 30 00:01:32,172 --> 00:01:32,880 Tanıştığımıza memnun oldum. 31 00:01:32,880 --> 00:01:34,005 >> İZLEYİCİ: Nice to meet you. 32 00:01:34,005 --> 00:01:36,790 HOPARLÖR: Pekala, ben var Burada mavi kitaplar A'dan Z'ye yoluyla, 33 00:01:36,790 --> 00:01:41,680 ve ben iddia gidiyorum Ben, öğrencilerden biri var 34 00:01:41,680 --> 00:01:45,770 ve onlar biraz rasgele geliyorlar üç saatlik sınav bloğunun sonunda, 35 00:01:45,770 --> 00:01:49,400 bu yüzden bazı biten konum Bu gibi yarı-rasgele düzen. 36 00:01:49,400 --> 00:01:54,510 Şimdi sadece bir an iş gidiyor Bu onlar olsun ne kadar aslında şey olmak 37 00:01:54,510 --> 00:01:56,820 sonunda döndü sınıf, büyük olasılıkla. 38 00:01:56,820 --> 00:02:01,120 İşiniz şimdi oldukça, olacak sadece, bizim için bu mavi kitapları sıralamak için 39 00:02:01,120 --> 00:02:05,220 A, Z ile 40 00:02:05,220 --> 00:02:08,400 >> İZLEYİCİ: Ah, bu sonsuza kadar alacak. 41 00:02:08,400 --> 00:02:13,747 >> HOPARLÖR: Ve biz izleyecek Bunu gibi, herhangi bir baskı. 42 00:02:13,747 --> 00:02:15,330 HEDEF KİTLE: Hayır, herhangi bir baskı ya da bir şey. 43 00:02:15,330 --> 00:02:19,230 44 00:02:19,230 --> 00:02:23,570 >> HOPARLÖR: Ve eğlence için, en bir zamanlayıcı koyalım. 45 00:02:23,570 --> 00:02:26,680 46 00:02:26,680 --> 00:02:28,700 >> İZLEYİCİ: Çok eğlenceli, çok eğlenceli. 47 00:02:28,700 --> 00:02:36,741 48 00:02:36,741 --> 00:02:38,574 >> HOPARLÖR: Senin için mikrofon tutabilir. 49 00:02:38,574 --> 00:02:40,240 Pekala, biz sadece bizim hızını iki katına ettik. 50 00:02:40,240 --> 00:02:44,190 51 00:02:44,190 --> 00:02:49,060 Bu arada Yani, benim ne poz verelim Mary Beth için soru olacak 52 00:02:49,060 --> 00:02:51,540 O ne yapıyor olduğunu, nasıl olduğunu o bu çözümü hakkında gidiyor? 53 00:02:51,540 --> 00:02:54,040 Ve aslında, sahip olmayabilir Hiç bir şey düşündüm 54 00:02:54,040 --> 00:02:57,440 Eğer pick kadar basit Böyle 26 kitap kadar, 55 00:02:57,440 --> 00:02:59,350 Doğal var olan Onlara sipariş. 56 00:02:59,350 --> 00:03:01,335 Süreci nedir Bu aslında kullanmak? 57 00:03:01,335 --> 00:03:03,770 Oldukça rastgele sadece Gördüğünüz ilk bir toplama 58 00:03:03,770 --> 00:03:05,250 ve onun yerine koyarak? 59 00:03:05,250 --> 00:03:09,680 Ilk etrafında ellerini hareket etmeyin Bir sonra B arıyor arıyor? 60 00:03:09,680 --> 00:03:11,722 Eğer bir göz atın musunuz yan yana bir çift 61 00:03:11,722 --> 00:03:14,680 ve sadece bir dakika bekleyin, bu demek doğru değil, ve sonra sipariş takas? 62 00:03:14,680 --> 00:03:16,960 Biz Pazartesi günü zaten gördüm yolları bir dizi var ki 63 00:03:16,960 --> 00:03:22,140 hangi biz bu yapmak ve Nitekim biz burada sonuna yakın olarak, 64 00:03:22,140 --> 00:03:26,360 Ben belki not alacağını Neyin Mary Beth yapıyor. 65 00:03:26,360 --> 00:03:30,040 Biz öyle görünüyor birkaç yığınları var, bir üç küçük olanları, bir büyük. 66 00:03:30,040 --> 00:03:33,790 67 00:03:33,790 --> 00:03:36,415 >> İZLEYİCİ: Ben bunları sipariş ediyorum Ben iki harf bulduğunuzda 68 00:03:36,415 --> 00:03:39,540 Ben biliyorum, bir dizide birlikte olduklarını, I do not böylece onları bir araya koymak 69 00:03:39,540 --> 00:03:42,915 tutma konusunda endişelenmenize gerek kitap bir bütün dizisinin iz. 70 00:03:42,915 --> 00:03:45,706 Bu, bir ilk, ah, sadece var Ben burada bu yığını var. 71 00:03:45,706 --> 00:03:47,580 Neredeyse gibi Yani,: SPEAKER Bir puzzle parçaları olduğunu 72 00:03:47,580 --> 00:03:49,860 doğru şekli var birbirleri ile maç. 73 00:03:49,860 --> 00:03:51,026 HEDEF KİTLE: Oldukça fazla, evet. 74 00:03:51,026 --> 00:03:55,320 HOPARLÖR: Tamam, mükemmel. 75 00:03:55,320 --> 00:03:59,850 Ve şimdi bu her kazık muhtemelen sıralanır? 76 00:03:59,850 --> 00:04:00,990 >> İZLEYİCİ: Evet. 77 00:04:00,990 --> 00:04:09,900 Z. All aracılığıyla Pekala, A: >> HOPARLÖR Doğru, tebrikler, bunu yaptım. 78 00:04:09,900 --> 00:04:11,461 Sen seçim var. 79 00:04:11,461 --> 00:04:11,960 Mavi? 80 00:04:11,960 --> 00:04:13,530 Pekala, bunun için teşekkür ederim. 81 00:04:13,530 --> 00:04:16,679 Yani Mary Beth teklif vermedi ne onun yaklaşımı oldu, 82 00:04:16,679 --> 00:04:19,720 ama başka bir yaklaşım nedir nasıl Bunları sıralama hakkında gidebilir? 83 00:04:19,720 --> 00:04:21,130 Ne yapardın? 84 00:04:21,130 --> 00:04:24,060 yenmek için kayıt olurdu bir dakika ve 50 saniye ya da öylesine, 85 00:04:24,060 --> 00:04:26,039 artı ben unuttum olanları saymak. 86 00:04:26,039 --> 00:04:27,080 Ne yapardın? 87 00:04:27,080 --> 00:04:27,579 Evet? 88 00:04:27,579 --> 00:04:28,735 HEDEF KİTLE: yığını alın. 89 00:04:28,735 --> 00:04:29,776 Baştan başlatır. 90 00:04:29,776 --> 00:04:32,284 Senin kağıtları kontrol edin. 91 00:04:32,284 --> 00:04:36,586 Ve üst bir yüksek ise daha belki, onlar vardır 92 00:04:36,586 --> 00:04:38,980 alt biridir yüksek, daha sonra onları geçmek. 93 00:04:38,980 --> 00:04:41,300 >> HOPARLÖR: Tamam, bu yüzden başlayan üst ve alt kısmında, 94 00:04:41,300 --> 00:04:43,716 ve sonra yolunuzu çalışma içe böyle, onları takas? 95 00:04:43,716 --> 00:04:46,580 Benzer Tamam, bu yüzden biraz kabarcık tür ruhu içinde, 96 00:04:46,580 --> 00:04:49,160 ancak aşırı seçerek değil komşu çiftleri. 97 00:04:49,160 --> 00:04:52,080 Ama kısa var olduğunu Farklı şekillerde mutlaka bir demet 98 00:04:52,080 --> 00:04:54,210 Biz bunu, ve olabilir açıkçası, ben tür size düşünüyorum 99 00:04:54,210 --> 00:04:55,700 Sağ, bir kaç yaklaşımları kabul? 100 00:04:55,700 --> 00:05:00,567 Dört sıralı kazık tür yapılmış ve Sonra birlikte etkili onları birleşti. 101 00:05:00,567 --> 00:05:02,650 Ve başka, daresay, var tamamen tekniği. 102 00:05:02,650 --> 00:05:06,950 Sen, büyük bir yığın olarak ele vermedi Eğer, dört dörtlü içine sorunu bölünmüş 103 00:05:06,950 --> 00:05:09,820 olacak, ve sonra bir şekilde eğer Sonunda onları birleşti. 104 00:05:09,820 --> 00:05:13,410 >> Yani sonuçta, düşünelim, Biz bunu nasıl başka. 105 00:05:13,410 --> 00:05:15,860 Biz kavramı resmiyet kabarcık sıralama son kez, 106 00:05:15,860 --> 00:05:18,780 ve kabarcık sıralama hatırlama olan bir Biz görüntülenmiştir algoritma 107 00:05:18,780 --> 00:05:22,640 buraya sınıf arkadaşlarının sekiz, görünüşte rastgele ilk sıralanır. 108 00:05:22,640 --> 00:05:26,110 Ve biz o takdirde, çiftler halinde karar İki element, düzenin dışında 109 00:05:26,110 --> 00:05:26,950 sadece onları takas. 110 00:05:26,950 --> 00:05:28,930 Bu yüzden, dört ve iki tanesi Açıkçası bozuk, 111 00:05:28,930 --> 00:05:31,080 böylece bu iki sınıf arkadaşları pozisyonları açık. 112 00:05:31,080 --> 00:05:35,390 Ve sonra, dört ve altı tekrarlanan Daha sonra altı ve sekiz, her tekrarında, 113 00:05:35,390 --> 00:05:36,980 sağa hareket. 114 00:05:36,980 --> 00:05:42,590 >> Peki, kaç eşli sekiz kişiyi verilen yürüyüş sırasında karşılaştırmalar ben yaptım 115 00:05:42,590 --> 00:05:45,220 Böyle bir tekrarında sağa sola? 116 00:05:45,220 --> 00:05:48,410 Kaç karşılaştırmalar? 117 00:05:48,410 --> 00:05:49,197 Yedi, değil mi? 118 00:05:49,197 --> 00:05:51,405 Sekiz varsa Çünkü İnsanlar ancak çift var 119 00:05:51,405 --> 00:05:53,880 Onları ve hareketli tutmak bir, sağa hop 120 00:05:53,880 --> 00:05:56,060 Eğer sekiz olması için gidiyoruz değil karşılaştırmalar karşılaştırın olamaz çünkü 121 00:05:56,060 --> 00:05:59,226 kendisine karşı bir eleman, ya da olur Sadece anlamsız, bu yüzden yedi var. 122 00:05:59,226 --> 00:06:01,290 Ya da daha genel olarak, eğer Biz n insanlar var, biz 123 00:06:01,290 --> 00:06:04,300 n eksi 1 karşılaştırmalar yapmak kabarcık sıralama ile. 124 00:06:04,300 --> 00:06:08,150 >> Peki ne kadar iyi şimdi düşünelim veya Kötü kabarcık sıralama aslında, ve deneyin 125 00:06:08,150 --> 00:06:13,570 ile kendimizi kelime vermek Böyle eleştiri algoritmaları hangi, 126 00:06:13,570 --> 00:06:14,430 ve yakında kendi. 127 00:06:14,430 --> 00:06:16,970 Ile ilk geçişte Yani kabarcık sıralama, ilk kez 128 00:06:16,970 --> 00:06:20,909 Ben genelinde sağa sola yürüdü sahne, beni n eksi 1 karşılaştırmalar aldı. 129 00:06:20,909 --> 00:06:22,950 Ve bu olacak benim ölçü birimi, değil mi? 130 00:06:22,950 --> 00:06:26,170 Ben tür konuşma ve gezinme oldu, biraz biraz yavaş, hızlı, 131 00:06:26,170 --> 00:06:29,300 böylece saniye benim sayısını sayma özellikle söylüyorum değil, 132 00:06:29,300 --> 00:06:32,260 ancak sayısını sayma Ben Pazartesi günü yaptığı işlemler, 133 00:06:32,260 --> 00:06:35,900 İki kişiyi karşılaştırarak, hissediyor bir ölçü birimi gibi güzel. 134 00:06:35,900 --> 00:06:40,980 >> Yani n eksi 1, ilk defa adımlar, ama sonra sonra ne oldu? 135 00:06:40,980 --> 00:06:46,610 Tek seferde bir ters nedir Aksi takdirde sıralanmamış liste boyunca? 136 00:06:46,610 --> 00:06:49,840 Eğer eleman hakkında bana söyleyebilir neler Oradaki tüm yol kimdi? 137 00:06:49,840 --> 00:06:51,300 Evet? 138 00:06:51,300 --> 00:06:52,870 Bu doğru, büyük unsur oldu? 139 00:06:52,870 --> 00:06:55,710 Sayı sekiz, hatta she olsa burada başladı, her zaman 140 00:06:55,710 --> 00:06:57,860 karşı onu karşılaştırıldığında Bir komşu, o tuttu 141 00:06:57,860 --> 00:07:00,480 sağa kadar köpüren Listenin tarafta. 142 00:07:00,480 --> 00:07:02,710 Ve gerçekten de, bu nerede algoritması adını alır. 143 00:07:02,710 --> 00:07:07,630 >> Şimdi bu mantığa göre, kaç karşılaştırmalar Ben ikinci kez yapmak gerekir 144 00:07:07,630 --> 00:07:09,800 Soldan sağa o pas yapmak? 145 00:07:09,800 --> 00:07:10,730 n eksi 2, değil mi? 146 00:07:10,730 --> 00:07:14,297 I eğer sadece benim zaman israf olacaktır birine karşı sekiz karşılaştırarak devam 147 00:07:14,297 --> 00:07:16,630 Başka biz zaten biliyoruz çünkü o doğru yerde idi. 148 00:07:16,630 --> 00:07:19,760 Yani bir bir parçasıdır optimizasyon, sonraki geçiş böylece 149 00:07:19,760 --> 00:07:23,899 artı eksi n iki adım olacak, burada, n, insan sayısıdır. 150 00:07:23,899 --> 00:07:26,940 Şimdi tür bile, tahmin edebilirsiniz Eğer bir bilgisayar bilimcisi değilseniz, 151 00:07:26,940 --> 00:07:27,680 bu nasıl biter. 152 00:07:27,680 --> 00:07:31,259 Bu algoritma sonunda, muhtemelen Eğer sadece bir karşılaştırma sol var. 153 00:07:31,259 --> 00:07:33,800 Sen tür düzeltmek zorunda durumda iki listenin başında 154 00:07:33,800 --> 00:07:36,540 ve bir düzenin dışında ve bir ve iki olmalıdır 155 00:07:36,540 --> 00:07:40,330 bu nedenle bu dibe artı 1 Final karşılaştırılması. 156 00:07:40,330 --> 00:07:44,500 >> Şimdi nokta, nokta, bu kadar dalgaların nokta tür suludur detay bazı eller, 157 00:07:44,500 --> 00:07:46,452 ama sadece gitmek önde ve basitleştirmek edelim. 158 00:07:46,452 --> 00:07:48,660 Yüksek gelen hatırlayacak olursak Sizin okul, açıkçası, bir sürü 159 00:07:48,660 --> 00:07:50,340 vardı matematik kitapları Biraz hile levha 160 00:07:50,340 --> 00:07:52,550 Ön kapak veya Seni gösterdi arka kapak 161 00:07:52,550 --> 00:07:56,400 ne gibi serisi toplamları Bu sonuçta kadar ekledi. 162 00:07:56,400 --> 00:07:59,600 Genel durumda, bir varsa n gibi değişken ve aslında bu bir, 163 00:07:59,600 --> 00:08:01,634 Eğer baktı eğer senin eski okul matematik kitabı, 164 00:08:01,634 --> 00:08:04,050 Eğer bu aslında görürdünüz Burada bu toplamı kadar ekler 165 00:08:04,050 --> 00:08:07,970 n kere n eksi 1, tüm bölü 2. 166 00:08:07,970 --> 00:08:11,172 Yani şimdi bana sadece şart izin Bu yüzden inanç bir sıçrama üzerine, doğrudur 167 00:08:11,172 --> 00:08:12,880 bu toplar ne kadar, ve biz olabilir 168 00:08:12,880 --> 00:08:14,341 Daha genel bir durumda olduğunu kanıtlamaktadır. 169 00:08:14,341 --> 00:08:15,590 Ama şimdi gelin bunu genişletmek edelim. 170 00:08:15,590 --> 00:08:19,920 Yani bu çarpın izin böylece var n kare, eksi n, tüm 2'ye bölünür. 171 00:08:19,920 --> 00:08:23,200 Yani, gerçekten n kare var eksi n üzerinde 2, 2 bölü, 172 00:08:23,200 --> 00:08:25,010 böylece tüm güzel ve ilginç. 173 00:08:25,010 --> 00:08:27,060 Ama ne biz olur plug-in değeri? 174 00:08:27,060 --> 00:08:29,724 Ben sekiz yoktu varsayalım İnsanlar, ancak bir milyon söylüyorlar. 175 00:08:29,724 --> 00:08:31,890 Ve bir milyon sırf bu, oldukça büyük bir sayı var 176 00:08:31,890 --> 00:08:34,039 en bu in fiş ve ne görelim. 177 00:08:34,039 --> 00:08:39,039 Ben bu formüle bir milyon fiş Yani eğer Ben, bir milyon kare almak için gidiyorum 178 00:08:39,039 --> 00:08:42,868 2 bölü eksi bir milyon, 2 bölü. 179 00:08:42,868 --> 00:08:44,159 Şimdi ne olacak ki eşit olacak? 180 00:08:44,159 --> 00:08:47,354 Yani 500 milyar, eksi 500.000. 181 00:08:47,354 --> 00:08:49,270 Ve aslında yaparsam Bu matematik dışarı, o aracı 182 00:08:49,270 --> 00:08:53,920 bir milyon sıralama kabarcık tür insanlar 183 00:08:53,920 --> 00:09:01,800 Bana 499.999.500.000 sürebilir sonunda adımlar veya karşılaştırmalar, 184 00:09:01,800 --> 00:09:02,900 biz sadece extrapolating ediyoruz. 185 00:09:02,900 --> 00:09:06,860 >> Bu oldukça yavaş hissediyor, ama açıkçası belirli bir girişi ölçüm 186 00:09:06,860 --> 00:09:09,160 Bu gibi tüm söylüyorum değildir. 187 00:09:09,160 --> 00:09:14,050 Ama gerçekten de n olarak öneririz yok Daha büyük ve daha büyük, bu algoritma alır 188 00:09:14,050 --> 00:09:16,280 tür hissediyor kötü ve kötü, ya da gerçekten 189 00:09:16,280 --> 00:09:20,450 Bunun acısını hissetmeye başlar üstel, bu n, kare 190 00:09:20,450 --> 00:09:21,770 hangi oldukça hızlı ekler. 191 00:09:21,770 --> 00:09:25,340 Ve bu ayrıntı değil Aslında, insanlar üzerinde kayıp 192 00:09:25,340 --> 00:09:29,640 birkaç yıl önce belli bir senatör kim kampanya, bir görüşme için oturdu 193 00:09:29,640 --> 00:09:32,180 Google'ın Eric ile Schmidt, zaman CEO'su, 194 00:09:32,180 --> 00:09:36,380 ve bir soru ile meydan çok bugün keşfetmek gibisin. 195 00:09:36,380 --> 00:09:38,468 Bir göz atalım. 196 00:09:38,468 --> 00:09:45,280 >> [VİDEO OYNATMA] 197 00:09:45,280 --> 00:09:48,560 >> -Senatör, Sen buradasın Google'da, ve ben gibi 198 00:09:48,560 --> 00:09:53,382 cumhurbaşkanlığı düşünmek Bir iş görüşmesi olarak. 199 00:09:53,382 --> 00:09:56,434 Şimdi, almak zor Başkan olarak bir iş, 200 00:09:56,434 --> 00:09:58,100 ve şimdi zorluklarına yoluyla gidiyoruz. 201 00:09:58,100 --> 00:10:01,860 Bu Google'da bir iş için de zor. 202 00:10:01,860 --> 00:10:05,490 Biz sorularınız varsa, ve biz Bizim adayların soru sormak, 203 00:10:05,490 --> 00:10:09,770 ve bu bir Larry Schwimmer değil. 204 00:10:09,770 --> 00:10:14,760 Ne-- siz ben düşünüyorum Şaka, işte burada. 205 00:10:14,760 --> 00:10:17,930 En etkili yolu nedir Bir milyon 32-bit tamsayı sıralamak? 206 00:10:17,930 --> 00:10:21,800 207 00:10:21,800 --> 00:10:24,350 >> -Well-- 208 00:10:24,350 --> 00:10:25,200 >> -Özür Dilerim, belki-- 209 00:10:25,200 --> 00:10:27,400 >> -Hayır, Hayır, hayır. 210 00:10:27,400 --> 00:10:30,700 Ben kabarcık sıralama düşünüyorum gitmek için yanlış bir yol olacaktır. 211 00:10:30,700 --> 00:10:34,165 212 00:10:34,165 --> 00:10:38,180 >> Haydi, kim ona bunu söyledim? 213 00:10:38,180 --> 00:10:40,590 Ben bilgisayar görmedim Arka plan bilim. 214 00:10:40,590 --> 00:10:42,130 >> -We've Orada bizim casusları var. 215 00:10:42,130 --> 00:10:44,930 216 00:10:44,930 --> 00:10:48,444 >> -Tamam, En farklı soralım Görüşme bir soru. 217 00:10:48,444 --> 00:10:49,300 >> [SON VİDEO OYNATMA] 218 00:10:49,300 --> 00:10:52,290 >> HOPARLÖR: Yani bahsediyoruz ama özel sayılar, 219 00:10:52,290 --> 00:10:53,890 tüm bu yararlı olacak değil. 220 00:10:53,890 --> 00:10:56,810 Bu bir hayat dersi bu balonu değil sıralama, bir milyon girişleri verilen, 221 00:10:56,810 --> 00:10:58,590 gibi birçok milyar 500 gibi adımlar olabilir. 222 00:10:58,590 --> 00:11:01,120 Gerçekten genelleme olamaz Çok etkili bir şekilde gelen 223 00:11:01,120 --> 00:11:03,560 ve iyi tasarım kararları programları yazarken. 224 00:11:03,560 --> 00:11:07,070 Yani nasıl olsa odaklanmak izin Bu sonuç kolaylaştırmak olabilir. 225 00:11:07,070 --> 00:11:11,780 >> Yani burada sarı vurgulanmış ettik n sonucu, 2 bölü 226 00:11:11,780 --> 00:11:14,330 yani bir milyon kare 2 ile ayrılır ve daha sonra 227 00:11:14,330 --> 00:11:16,710 Ben vurgulanır kadarıyla nihai cevap oldu 228 00:11:16,710 --> 00:11:20,180 Biz kapalı çıkarılır kez n bölü 2. 229 00:11:20,180 --> 00:11:24,850 Ve ben şimdi yapmaya gidiyorum iddia olduğunu Eğer kapalı çıkarma durumunda kimin umurunda halt 230 00:11:24,850 --> 00:11:30,060 2 üzerinde biraz eski n birinci Bu formülün parçası çok daha büyük? 231 00:11:30,060 --> 00:11:33,910 Diğer hakim terimi, burada n, 2 bölü 232 00:11:33,910 --> 00:11:37,510 gibi, açık bir şekilde, çok daha büyük olduğunu n, bir milyon gibi büyük olur 233 00:11:37,510 --> 00:11:41,450 Bu gerçekten büyük bir fark var 500.000.000.000 arasındaki gün sonu 234 00:11:41,450 --> 00:11:45,730 ve 499999500000? 235 00:11:45,730 --> 00:11:46,349 Tam olarak değil. 236 00:11:46,349 --> 00:11:48,640 Ve böylece ne için gidiyoruz Bilgisayar bilim adamları gibi yapmak 237 00:11:48,640 --> 00:11:53,270 Bu alt mertebeden terimleri görmezden ve Bu ve gerçekten böyle bir şey almak 238 00:11:53,270 --> 00:11:56,050 Sadece onu basitleştirmek önemli olacak terim. 239 00:11:56,050 --> 00:12:00,315 büyük, bizim veri setleri, büyük olsun Bizim veritabanları, daha fazla web sayfaları olsun 240 00:12:00,315 --> 00:12:02,690 biz daha fazla aramak zorunda arkadaşlar Facebook'ta var. 241 00:12:02,690 --> 00:12:07,340 N büyüdükçe >> biz gerçekten konum en büyük umurumda olacak 242 00:12:07,340 --> 00:12:11,560 ve bu tür herhangi bir analizde süreli Bizim algoritmaları performans. 243 00:12:11,560 --> 00:12:16,230 Ve ben ne biliyorum, söylemek için gidiyorum, kabarcık sıralama büyük O sırasına üzerinde, 244 00:12:16,230 --> 00:12:18,060 n sırasına kare. 245 00:12:18,060 --> 00:12:20,090 Tam n değil Gördüğümüz gibi kare, 246 00:12:20,090 --> 00:12:22,060 ama kimin umurunda gerçekten bu küçük terimler hakkında, 247 00:12:22,060 --> 00:12:24,390 ve açıkçası, kim gerçekten Biz 2 ile bölmek umurunda? 248 00:12:24,390 --> 00:12:25,870 Bu sadece bir sabit faktör var. 249 00:12:25,870 --> 00:12:29,480 Ve 250 karşı 500 milyar olduğunu milyar anlaşma gerçekten büyük? 250 00:12:29,480 --> 00:12:32,190 Ben sadece bir yıl beklemek, kelimenin tam anlamıyla benim laptop izin 251 00:12:32,190 --> 00:12:34,810 donanımda iki kat daha hızlı olsun ve farkı bu tür 252 00:12:34,810 --> 00:12:36,650 Sadece zamanla doğal gider. 253 00:12:36,650 --> 00:12:39,300 >> Yaklaşık nedir bakım ifadesi, bölüm 254 00:12:39,300 --> 00:12:42,489 değişir gidiyor ifade Bizim girişi büyük ve büyüdükçe. 255 00:12:42,489 --> 00:12:45,280 Ve gerçekten de, gerçek dünyada, giderek neler var 256 00:12:45,280 --> 00:12:48,330 bizim sorunlara giriş ve algoritmalar büyüyor. 257 00:12:48,330 --> 00:12:53,470 Yani büyük O gösterimi olacak, asimptotik gösterimi, biz sadece 258 00:12:53,470 --> 00:12:57,160 Bilgisayar bilim adamları tanımlamak için kullanın performans, ya da çalışma süresi, 259 00:12:57,160 --> 00:12:58,130 bir algoritma. 260 00:12:58,130 --> 00:13:00,800 Biz algoritmaları karşılaştırabilirsiniz Böylece Yazılı farklı bilgisayarlarda 261 00:13:00,800 --> 00:13:04,170 farklı kişiler tarafından kullanılarak Bazı temelde benzer metrik 262 00:13:04,170 --> 00:13:07,557 karşılaştırmaların sayısı gibi sen Belki swap sayısını yapma, ya da 263 00:13:07,557 --> 00:13:08,140 Eğer yapıyoruz. 264 00:13:08,140 --> 00:13:11,910 >> Ne biz gitmiyoruz sayısı zaman miktarıdır 265 00:13:11,910 --> 00:13:13,981 Bu saat geçer tipik haliyle duvar üzerinde. 266 00:13:13,981 --> 00:13:16,230 Ne endişe etmeyeceğiz yaklaşık ne kadar bellek 267 00:13:16,230 --> 00:13:17,820 En bugün kullanıyorsanız Bu olsa, en az 268 00:13:17,820 --> 00:13:19,370 Biz ölçmek olabilir başka bir kaynak. 269 00:13:19,370 --> 00:13:23,610 Biz bizim analizler temel denemek için gidiyoruz sadece temel operasyonlar, olanlar, 270 00:13:23,610 --> 00:13:25,930 açıkçası, en görsel görebilirsiniz. 271 00:13:25,930 --> 00:13:30,700 N büyük O gibi bir şey So kare, ben n Ç kare iddia 272 00:13:30,700 --> 00:13:35,820 bir üst sözde ile bağlı olduğu kabarcık tür çalışma süresi. 273 00:13:35,820 --> 00:13:38,820 Diğer bir deyişle, eğer var olduğunu iddia etmek istedim 274 00:13:38,820 --> 00:13:41,370 kaç bu üst sınırı bir algoritma sürebilir adımları, 275 00:13:41,370 --> 00:13:46,240 o n büyük O'da olacak Bu durumda kare, bir üst sınır. 276 00:13:46,240 --> 00:13:49,710 >> Yerine değiştirirsem ne Hikaye değil, kabarcık sıralama hakkında olmak 277 00:13:49,710 --> 00:13:50,910 ancak bu üst sınır hakkında. 278 00:13:50,910 --> 00:13:54,030 Bir algoritma düşünebilir biz zaten baktım ki 279 00:13:54,030 --> 00:13:59,530 Kendilerinin üst sınır, maksimum zaman ya da operasyonların ölçmek, 280 00:13:59,530 --> 00:14:04,300 sınırlı olduğu söylenebilir istiyorum n ile, doğrusal bir fonksiyonu, 281 00:14:04,300 --> 00:14:07,260 değil kavisli olan bir kuadratik bir? 282 00:14:07,260 --> 00:14:10,780 Bir algoritma nedir ki Her zaman daha fazla alır 283 00:14:10,780 --> 00:14:12,860 n, adım, ya da bu gibi daha 2n adımlar veya 3n adımları? 284 00:14:12,860 --> 00:14:13,360 Evet? 285 00:14:13,360 --> 00:14:15,030 >> İZLEYİCİ: Bulma Bir listedeki en büyük sayı? 286 00:14:15,030 --> 00:14:16,930 >> HOPARLÖR: Mükemmel bulma Bir listedeki büyük sayıda. 287 00:14:16,930 --> 00:14:18,940 Ben bir liste verilmiş yaşıyorum Örneğin insanlar, 288 00:14:18,940 --> 00:14:21,440 kim her biri bir numara tutuyor maksimum sayı nedir 289 00:14:21,440 --> 00:14:23,770 adımlar beni almalı, makul akıllı bir kişi, 290 00:14:23,770 --> 00:14:27,530 Bu listede en büyük kişiyi bulmak için? 291 00:14:27,530 --> 00:14:28,100 n, değil mi? 292 00:14:28,100 --> 00:14:31,320 En kötü durumda, nerede Çünkü En büyük değeri olabilir? 293 00:14:31,320 --> 00:14:32,700 Doğru, sonunda tüm yol. 294 00:14:32,700 --> 00:14:34,575 En kötü durumda Yani Üst bağlı, ben belki 295 00:14:34,575 --> 00:14:36,450 tüm yol gitmek zorunda Burada ve benzeri olmak, 296 00:14:36,450 --> 00:14:39,170 oh, burada sayı sekiz var, ya bu değer ne olursa olsun. 297 00:14:39,170 --> 00:14:41,330 Şimdi sadece aptalca olurdu Ben, doğru devam etti olur? 298 00:14:41,330 --> 00:14:43,840 Daha fazla ve daha fazla eleman arıyorsunuz Bunlardan son orada olup olmadığını? 299 00:14:43,840 --> 00:14:45,340 Yani kesinlikle n bir üst sınırdır. 300 00:14:45,340 --> 00:14:47,420 Ben almak gerekmez daha fazla adım. 301 00:14:47,420 --> 00:14:51,580 >> Bunun yerine eğer ben önerdi ne Bu dünyada algoritmaları vardır 302 00:14:51,580 --> 00:14:57,750 olan bir çalışan zaman var Günlük n büyük O tarafından sınırlanan, n log? 303 00:14:57,750 --> 00:15:00,390 Nerede daha önce gördük? 304 00:15:00,390 --> 00:15:00,890 Evet? 305 00:15:00,890 --> 00:15:03,309 >> İZLEYİCİ: Telefon rehberi probleminde? 306 00:15:03,309 --> 00:15:04,850 HOPARLÖR: Telefon rehberi problemi gibi. 307 00:15:04,850 --> 00:15:07,754 Nasıl ölçüsü neydi kadar zaman ya da kaç gözyaşı onu 308 00:15:07,754 --> 00:15:10,170 Benim gibi birini bulmak aldı Telefon defterinde Mike Smith? 309 00:15:10,170 --> 00:15:13,212 Biz günlük n olduğunu iddia ve Hatta yabancı ya da eğer o var 310 00:15:13,212 --> 00:15:15,170 ne küçük bir puslu logaritma veya üs oldu, 311 00:15:15,170 --> 00:15:17,650 sadece günlük n hatırlıyorum genel olarak işleme değinmektedir, 312 00:15:17,650 --> 00:15:20,790 Bu durumda, bölme tekrar ve tekrar yarısında şey, 313 00:15:20,790 --> 00:15:25,790 ve tekrar ve tekrar, böyle öyle Bunu giderek küçük olur. 314 00:15:25,790 --> 00:15:28,470 >> Peki emin atıfta n log, Telefon rehberi örnek, 315 00:15:28,470 --> 00:15:32,662 teoride ikili arama, ne zaman biz , gemide sanal kapılar vardı 316 00:15:32,662 --> 00:15:34,370 veya Sean iken bir şey arıyor. 317 00:15:34,370 --> 00:15:37,374 O ikili arama kullanmış olsaydık, n log ne kadar üst sınır olacak 318 00:15:37,374 --> 00:15:38,040 geçen süre. 319 00:15:38,040 --> 00:15:44,027 Ama koştu o algoritmalar n ne anahtar detay kabul log? 320 00:15:44,027 --> 00:15:45,360 Liste, sağ sıralanır olduğunu? 321 00:15:45,360 --> 00:15:47,789 Sizin algoritması ise yanlış senin girdi, sıralanır 322 00:15:47,789 --> 00:15:49,830 ve henüz kullanıyorsanız İkili arama gibi bir şey 323 00:15:49,830 --> 00:15:51,704 Eğer atlamak olabilir çünkü Sağ öğe üzerinde 324 00:15:51,704 --> 00:15:53,600 Farkında olmadan gerçekten var. 325 00:15:53,600 --> 00:15:55,600 >> Şimdi bu bir büyük O ne demek olabilir? 326 00:15:55,600 --> 00:15:59,117 Bu algoritma anlamına gelmez , ve tek bir adım alır 327 00:15:59,117 --> 00:16:01,200 o sadece bir sürer demektir adımlannın sabit sayısı. 328 00:16:01,200 --> 00:16:04,060 Belki öyle, belki değil, 1 var 10, belki de 1,000 var, 329 00:16:04,060 --> 00:16:07,750 ancak bağımsızdır sorunun büyüklüğü. 330 00:16:07,750 --> 00:16:10,850 Ne kadar büyük n, sabit zaman algoritması 331 00:16:10,850 --> 00:16:12,747 hep adım aynı sayıda alır. 332 00:16:12,747 --> 00:16:15,080 Peki bir algoritma olabilir biz yaklaşık ya da sadece konuştuk 333 00:16:15,080 --> 00:16:20,418 sezgisel o size geliyor hep sözde sabit zamanda çalışır? 334 00:16:20,418 --> 00:16:20,918 Evet? 335 00:16:20,918 --> 00:16:22,001 >> İZLEYİCİ: iki sayı ekleyin. 336 00:16:22,001 --> 00:16:25,320 HOPARLÖR: İki numara ekle 2 artı 2 yapılır, 4 eşittir. 337 00:16:25,320 --> 00:16:27,227 Yani işe yarayabilir, başka ne? 338 00:16:27,227 --> 00:16:28,560 Nasıl daha gerçek dünya hakkında, evet? 339 00:16:28,560 --> 00:16:30,686 >> İZLEYİCİ: Bulma Bir listedeki ilk şey. 340 00:16:30,686 --> 00:16:32,810 HOPARLÖR: İlk bulma Bir listede eleman, emin olun. 341 00:16:32,810 --> 00:16:34,540 Biz aslında durduk Zaten diziler hakkında, 342 00:16:34,540 --> 00:16:36,540 at almak nasıl Bir dizideki ilk elemanı, 343 00:16:36,540 --> 00:16:40,465 ne kadar uzun Dizi C kodu nedir? 344 00:16:40,465 --> 00:16:43,090 Sadece dirsek gibi kullanmak sıfır gösterim, bam, sen oradasın. 345 00:16:43,090 --> 00:16:46,120 Ve bir kenara olarak gerçekten diziler, Destek şey genellikle bilinen 346 00:16:46,120 --> 00:16:49,240 Rasgele erişim olarak rastgele erişimli Bellek, kelimenin tam anlamıyla can çünkü 347 00:16:49,240 --> 00:16:50,284 herhangi bir yerde atlamak. 348 00:16:50,284 --> 00:16:52,700 Biz sadece bu daha da yapabilirsiniz biz hafta sıfır geri sarma 349 00:16:52,700 --> 00:16:53,900 biz Scratch yaptım. 350 00:16:53,900 --> 00:16:59,707 Ne için aldınız ne kadar zaman Scratch blok yürütmek söylemek? 351 00:16:59,707 --> 00:17:00,790 Sadece zaman sabiti, değil mi? 352 00:17:00,790 --> 00:17:03,960 Bir şey söylemek söyle şey, önemli değil 353 00:17:03,960 --> 00:17:07,359 Büyük çizikler dünya nasıl, her zaman var zaman aynı miktarda alacak 354 00:17:07,359 --> 00:17:08,490 sadece bir şey söylemek için. 355 00:17:08,490 --> 00:17:11,089 >> Bu sabit zaman Yani, ama kapak tarafı nedir? 356 00:17:11,089 --> 00:17:13,030 Bu üst olsaydı sınırları, ne isterseniz 357 00:17:13,030 --> 00:17:17,089 alt sınır tanımlamak için Bizim algoritmaların çalışma süresi? 358 00:17:17,089 --> 00:17:19,852 Neredeyse en iyi durumda potansiyel, eğer sen, 359 00:17:19,852 --> 00:17:23,060 bu terimler en iyi şekilde geçerli olabilir ama davalar, en kötü durumda, ortalama vakalar daha fazla 360 00:17:23,060 --> 00:17:26,359 Genellikle, ama sadece odak sağlar alt sınırları daha genel. 361 00:17:26,359 --> 00:17:31,920 Ne var bir algoritma var bir düşük değerli n adımlarının bağlı 362 00:17:31,920 --> 00:17:33,350 veya 2n adımlar, yoksa 3n adımları? 363 00:17:33,350 --> 00:17:36,241 N, bazı adımlar faktörü Bu onun alt sınır var. 364 00:17:36,241 --> 00:17:36,740 Evet? 365 00:17:36,740 --> 00:17:37,910 >> İZLEYİCİ: Kabarcık sıralama? 366 00:17:37,910 --> 00:17:41,610 >> HOPARLÖR: Kabarcık sıralama alır Eğer minimal n adımları, neden? 367 00:17:41,610 --> 00:17:42,279 Neden? 368 00:17:42,279 --> 00:17:45,320 Neden bu başlangıç ​​sana gelmek gerekir sezgisel, öyle olsa bile sadece 369 00:17:45,320 --> 00:17:46,530 Henüz? 370 00:17:46,530 --> 00:17:47,030 Evet? 371 00:17:47,030 --> 00:17:47,990 >> İZLEYİCİ: [duyulamaz]. 372 00:17:47,990 --> 00:17:51,652 373 00:17:51,652 --> 00:17:52,360 KONUŞMACI: Kesinlikle. 374 00:17:52,360 --> 00:17:55,810 Mümkün olan en iyi senaryoda kabarcık sıralama, ve algoritmalar bir sürü, 375 00:17:55,810 --> 00:17:58,769 Sana sekiz kişi el, eğer kim zaten sıralanır, 376 00:17:58,769 --> 00:18:00,560 bu aptalca olurdu Sizin için, algoritma, 377 00:18:00,560 --> 00:18:02,202 ileri ve geri gitmek için defadan fazla, değil mi? 378 00:18:02,202 --> 00:18:04,285 En kısa sürede senin kadar Çünkü bir kez listede yürümek, 379 00:18:04,285 --> 00:18:08,090 Eğer, fark oh gerektiğini, ben yapılan hiçbir swapları, bu liste, çıkış sıralanır. 380 00:18:08,090 --> 00:18:09,700 Ama sen n adımlar atmaya gidiyor. 381 00:18:09,700 --> 00:18:12,033 >> Ve tersine, ne başka var Bu konuda düşünme yolu? 382 00:18:12,033 --> 00:18:15,240 Kabarcık sıralama bir omega olduğunu, yani n, konuşmak, 383 00:18:15,240 --> 00:18:19,050 Eğer bakarsanız, çünkü daha az n elemanları, ne 384 00:18:19,050 --> 00:18:23,009 temel sorun vardır? 385 00:18:23,009 --> 00:18:24,550 O sıralanır eğer sağ bilmiyorum. 386 00:18:24,550 --> 00:18:26,800 Biz sekiz kudreti bakış insanlarda İnsanlar ve, gibi oh, o sıralanır var olmak 387 00:18:26,800 --> 00:18:28,430 beni n adımlar sürmedi, ama yaptım. 388 00:18:28,430 --> 00:18:30,810 Gözlerin bile nazik sana rağmen bir, vizyon büyük bir alan var 389 00:18:30,810 --> 00:18:33,184 sekiz elemanları baktı, Eğer, sekiz kişi baktı 390 00:18:33,184 --> 00:18:34,610 Bu etkili bir sekiz adım var. 391 00:18:34,610 --> 00:18:38,612 Ve ben bütün yürümek sadece Liste, evet sıralanır, fark yok. 392 00:18:38,612 --> 00:18:41,320 Ben durdurmak Eğer yarım tüm düşünme Doğru, bu oldukça şimdiye kadar sıralanır var, 393 00:18:41,320 --> 00:18:42,520 o sıralanır değil oran nedir? 394 00:18:42,520 --> 00:18:44,186 Bu doğru olacak değil algoritmaları. 395 00:18:44,186 --> 00:18:46,250 Daha hızlı, ama yanlış olabilir. 396 00:18:46,250 --> 00:18:48,500 >> Şimdi biz bir yol olan var bir alt sınır açıklayan, 397 00:18:48,500 --> 00:18:49,710 ve sürekli zaman hakkında ne? 398 00:18:49,710 --> 00:18:54,565 Bir düşük olan bir algoritmadır biri kendi çalışma zamanında bağlı? 399 00:18:54,565 --> 00:18:58,350 1 adım 2 adım, 10 adım, ama sabit n bağımsız olarak, 400 00:18:58,350 --> 00:18:59,310 girdi boyutu? 401 00:18:59,310 --> 00:19:03,930 402 00:19:03,930 --> 00:19:04,600 Evet, arka. 403 00:19:04,600 --> 00:19:05,309 >> İZLEYİCİ: Printf? 404 00:19:05,309 --> 00:19:06,183 HOPARLÖR: Bu nedir? 405 00:19:06,183 --> 00:19:07,184 HEDEF KİTLE: Printf? 406 00:19:07,184 --> 00:19:07,850 KONUŞMACI: Printf. 407 00:19:07,850 --> 00:19:08,400 Emin, tamam. 408 00:19:08,400 --> 00:19:10,720 Bu yüzden adımlar sabit sayıda alır. 409 00:19:10,720 --> 00:19:13,170 Ve ben şimdi şimdi-- gerekir Biz C kodu hakkında konuşuyor 410 00:19:13,170 --> 00:19:16,040 ve Scratch, bir şey diyelim ki gibi, printf ile, 411 00:19:16,040 --> 00:19:17,710 dikkatli olsun başlamalıdır. 412 00:19:17,710 --> 00:19:21,090 Printf sürer Çünkü giriş, bir dize var, 413 00:19:21,090 --> 00:19:23,220 ve dizeleri teknik uzunluğu var. 414 00:19:23,220 --> 00:19:25,530 Şimdi almak istiyorsanız size, sakıncası yoksa, 415 00:19:25,530 --> 00:19:29,430 teknik o printf iddia olabilir değişken uzunluk girişi sürer, 416 00:19:29,430 --> 00:19:32,270 ve kesinlikle daha fazla sürebilir Zaman, bu uzun bir dize yazdırmak için 417 00:19:32,270 --> 00:19:33,560 Bu uzun daha. 418 00:19:33,560 --> 00:19:36,570 >> Yani biz sadece ne düşünün sıralama ve örnekler arıyor? 419 00:19:36,570 --> 00:19:40,450 Telefonda Mike Smith hakkında neler Kitap, ya da daha genel olarak ikili arama? 420 00:19:40,450 --> 00:19:42,220 En iyi durumda, ne olur acaba? 421 00:19:42,220 --> 00:19:45,577 Ben, bam, telefon defterini açmak ve Mike Smith'in numara var. 422 00:19:45,577 --> 00:19:46,660 Ben hemen onu arayabilirsin. 423 00:19:46,660 --> 00:19:49,390 >> Belki iki adım, bir adım aldı ancak adımlar sabit sayıda 424 00:19:49,390 --> 00:19:50,230 Ben şanslı var ise. 425 00:19:50,230 --> 00:19:52,570 Ve açıkçası, biz gördüm Pazartesi günü sınıf arkadaşı 426 00:19:52,570 --> 00:19:54,710 Arka arkaya iki kez oldukça şanslı olsun. 427 00:19:54,710 --> 00:19:57,050 Ve bu gerçekten sabit oldu bir alt sınırları içinde zaman 428 00:19:57,050 --> 00:20:01,280 Söz konusu algoritma bulmak için Bu kapalı arkasındaki numara 50 429 00:20:01,280 --> 00:20:01,830 kapılar. 430 00:20:01,830 --> 00:20:06,400 >> Şimdi, bir kenara, keşfetmek gibi hem büyük O, üst sınır olduğunu 431 00:20:06,400 --> 00:20:09,310 ve omega, düşük, bağlı , aynı birdir 432 00:20:09,310 --> 00:20:11,830 Aynı formül olduğunu parantez, siz de yapabilirsiniz 433 00:20:11,830 --> 00:20:15,170 sadece fantezi olmak demek, bir şey teta 434 00:20:15,170 --> 00:20:18,270 n veya başka bir değer teta evi. 435 00:20:18,270 --> 00:20:20,661 Bu sadece zaman büyük anlamı Ç ve omega aynıdır. 436 00:20:20,661 --> 00:20:21,910 Şimdi seçim sıralama hakkında ne? 437 00:20:21,910 --> 00:20:23,400 Şimdi bu yeni kelimeleri kullanmak edelim. 438 00:20:23,400 --> 00:20:27,407 Seçim tür, ne kalmıştık Yine yapıyor, ve tekrar ve tekrar? 439 00:20:27,407 --> 00:20:29,990 Ben üzerinden ileri ve geri gidiyordu Liste, kimin arıyor? 440 00:20:29,990 --> 00:20:33,260 441 00:20:33,260 --> 00:20:34,730 küçük sayı. 442 00:20:34,730 --> 00:20:37,560 >> Peki kaç adım, nasıl Birçok karşılaştırmalar I did 443 00:20:37,560 --> 00:20:43,250 anlamaya için yapmak zorunda olan Listede en küçük elemanı oldu? 444 00:20:43,250 --> 00:20:44,437 n eksi 1, değil mi? 445 00:20:44,437 --> 00:20:47,770 Ben sadece ben biri ile başlamak Çünkü eğer Verilen ve ben ona karşılaştırarak başlar, 446 00:20:47,770 --> 00:20:49,519 Onu ya da onu, onu sonra Onu, onu ya da onu, ben ya 447 00:20:49,519 --> 00:20:52,010 Sadece elemanları eşleştirebilirsiniz Birlikte n eksi 1 kez. 448 00:20:52,010 --> 00:20:55,630 Yani seçim sıralama benzer alır n eksi 1, ilk defa adımlar. 449 00:20:55,630 --> 00:20:59,540 O beni sürer >> kaç adım İkinci küçük elemanı bulmak? 450 00:20:59,540 --> 00:21:02,920 n eksi 2, ben olduğum için aptal olmak Ben aynı insanlar bakarak devam edersem 451 00:21:02,920 --> 00:21:06,280 Yine ben zaten onu seçtiyseniz ya da onu ve onların yerine koyun. 452 00:21:06,280 --> 00:21:09,270 Üçüncü adım, n, eksi 3, n eksi 4. 453 00:21:09,270 --> 00:21:11,020 Biz bu desen gördüm önce ve gerçekten 454 00:21:11,020 --> 00:21:13,460 Seçim sıralama benzer sınır bir üst vardır 455 00:21:13,460 --> 00:21:16,210 n biz toplamı kadar yaparsanız kare. 456 00:21:16,210 --> 00:21:19,790 Alt sınır, seçim sıralama nedir? 457 00:21:19,790 --> 00:21:25,350 Minimal, ne kadar zaman gerekir seçimi Biz Pazartesi günü tanımlandığı gibi sıralamak almak? 458 00:21:25,350 --> 00:21:29,370 459 00:21:29,370 --> 00:21:30,490 İki seçenek önerilmesi. 460 00:21:30,490 --> 00:21:32,360 Belki daha önce olduğu gibi, n var. 461 00:21:32,360 --> 00:21:35,040 Belki bunun gibi, kare n var Üst sınır olarak şimdi. 462 00:21:35,040 --> 00:21:35,874 >> İZLEYİCİ: n kare. 463 00:21:35,874 --> 00:21:36,664 HOPARLÖR: kare n. 464 00:21:36,664 --> 00:21:37,368 Neden? 465 00:21:37,368 --> 00:21:40,060 >> İZLEYİCİ: Eğer Çünkü [duyulamaz] tanımlamak için. 466 00:21:40,060 --> 00:21:41,510 >> HOPARLÖR: Kesinlikle. 467 00:21:41,510 --> 00:21:45,077 Ben seçim sıralama tanımlanan en azından oldukça naif oldu, devam, 468 00:21:45,077 --> 00:21:46,160 küçük eleman bulmak. 469 00:21:46,160 --> 00:21:47,770 Küçük eleman bulmak, tekrar gitmek. 470 00:21:47,770 --> 00:21:49,490 Küçük eleman bulmak, tekrar gitmek. 471 00:21:49,490 --> 00:21:51,700 Hiçbir tür yok Orada ki optimizasyonu 472 00:21:51,700 --> 00:21:54,350 Bana sonra iptal izin olabilir Sadece n ya da öylesine adımlar. 473 00:21:54,350 --> 00:21:57,080 Bu yüzden, gerçekten seçim sıralama, n omega kare. 474 00:21:57,080 --> 00:22:00,667 >> Ben aldı ekleme tür, ne Ben verildi, ve sonra onu plopped kim 475 00:22:00,667 --> 00:22:01,750 ya da onu doğru yerde? 476 00:22:01,750 --> 00:22:04,958 Sonra, ikinci kişiye ilerledi doğru yerde ona plopped. 477 00:22:04,958 --> 00:22:07,910 Sonra gelecek kişi, plopped Onu ya da onu doğru yerde. 478 00:22:07,910 --> 00:22:10,537 Bu çok olduğunu fark lineer, tabiri caizse. 479 00:22:10,537 --> 00:22:12,620 Ben değilim, düz bir çizgi değilim ileri ve geri gitmiyor, 480 00:22:12,620 --> 00:22:16,080 Ben asla gerçekten geriye bakarak, ama ettik Onu taktığınızda ne oluyor 481 00:22:16,080 --> 00:22:20,302 başında içine onu ya Liste biz Pazartesi günü yaptığımız gibi? 482 00:22:20,302 --> 00:22:21,010 Ne oluyor? 483 00:22:21,010 --> 00:22:21,510 Evet? 484 00:22:21,510 --> 00:22:23,122 HEDEF KİTLE: [duyulamaz]. 485 00:22:23,122 --> 00:22:24,830 HOPARLÖR: Evet, bu Doğru, yakalamak oldu? 486 00:22:24,830 --> 00:22:26,746 Sen hatırlayacağınız senin sınıf arkadaşları, onlar eğer 487 00:22:26,746 --> 00:22:29,670 herhangi bir hareket ile yapıyor kendi ayakları, bu bir operasyon oldu. 488 00:22:29,670 --> 00:22:33,610 Yani eğer orada üç kişi burada olduğumuzu ve Yeni bir kişi, orada yol üzerinde aitti 489 00:22:33,610 --> 00:22:37,360 Bu gibi uzun sahnede, emin, o ya da o sadece sonuna kadar gidebiliriz. 490 00:22:37,360 --> 00:22:40,074 Ama biz düşünmeye eğer Bilgisayar ve bellek dizi 491 00:22:40,074 --> 00:22:41,990 Bu insanlar gidiyor üzerinde shuffle zorunda 492 00:22:41,990 --> 00:22:43,260 o kişi için yer açmak için. 493 00:22:43,260 --> 00:22:46,930 Böylece bu durumda n eksi 1 sürümeleri, n, eksi 2 sürümeleri n 494 00:22:46,930 --> 00:22:50,660 eksi 3 sürümeleri sadece tür olduğunu değil önümde, arkamda oluyor 495 00:22:50,660 --> 00:22:52,710 daha önce olduğu gibi, bir anlamda. 496 00:22:52,557 --> 00:22:54,640 Şimdi bir kenara olarak, ve gibi online görmüş olabilir 497 00:22:54,640 --> 00:22:57,699 hakkında çevresinde alay başlarsanız sıralar, pek çok farklı olanları var 498 00:22:57,699 --> 00:22:59,490 Bunların dışında orada bazı diğerlerinden daha iyi. 499 00:22:59,490 --> 00:23:02,200 Gerçekten de, Saçma sıralama biridir Bu bakmak için eğlenceli tür. 500 00:23:02,200 --> 00:23:06,650 Saçma sıralama bir dizi alır sayılar ya da bir deste demek, 501 00:23:06,650 --> 00:23:09,870 rastgele onları karıştırır, ve kontroller onlar sıralanır eğer. 502 00:23:09,870 --> 00:23:12,130 Değilse Ve, yine öyle. 503 00:23:12,130 --> 00:23:14,140 Değilse Ve, yine öyle. 504 00:23:14,140 --> 00:23:15,440 Değilse, yine öyle. 505 00:23:15,440 --> 00:23:17,060 İnanılmaz aptal. 506 00:23:17,060 --> 00:23:19,520 >> Ve gerçekten, sen okursanız Wikipedia makalesi gibi, 507 00:23:19,520 --> 00:23:21,200 onun takma aptal tür. 508 00:23:21,200 --> 00:23:25,180 Sonunda çalışacaktır, umarım yeterli zaman verildiğinde, 509 00:23:25,180 --> 00:23:28,240 ama zaman bu miktarı oldukça zaman alabilir. 510 00:23:28,240 --> 00:23:31,650 Ben, diyelim eğer hız şeyler Yani Daha önce Mary Beth'in Örneğin kadar, 511 00:23:31,650 --> 00:23:35,150 Birkaç daha fazla eleman sağlayarak, ama iki işlemci. 512 00:23:35,150 --> 00:23:37,100 İki kişi, eğer Beni katılmadan sakıncası olur değil. 513 00:23:37,100 --> 00:23:40,972 Nasıl yaklaşık 1 buraya, ve en orada kimse go-- izin? 514 00:23:40,972 --> 00:23:41,722 Oradaki kimse? 515 00:23:41,722 --> 00:23:42,221 TAMAM MI. 516 00:23:42,221 --> 00:23:44,190 Siyah Sen gömlek, evet, aşağı gel. 517 00:23:44,190 --> 00:23:45,000 Pekala, senin adın ne? 518 00:23:45,000 --> 00:23:45,720 >> İZLEYİCİ: Peter. 519 00:23:45,720 --> 00:23:46,100 >> HOPARLÖR: Bu nedir? 520 00:23:46,100 --> 00:23:46,766 >> İZLEYİCİ: Peter. 521 00:23:46,766 --> 00:23:49,450 HOPARLÖR: Peter David, nice to meet you. 522 00:23:49,450 --> 00:23:53,670 Pekala, biz burada Peter var eğer buraya masaya gelmek istiyorum. 523 00:23:53,670 --> 00:23:54,550 Ve senin adın ne? 524 00:23:54,550 --> 00:23:55,216 >> İZLEYİCİ: Elena. 525 00:23:55,216 --> 00:23:55,970 KONUŞMACI: Elena. 526 00:23:55,970 --> 00:23:57,030 Tamam, seninle tanışmak güzel. 527 00:23:57,030 --> 00:23:58,060 Elena Peter buluşuyor. 528 00:23:58,060 --> 00:23:59,170 Peter, Elena. 529 00:23:59,170 --> 00:24:02,290 Ve Andrew gerekir burada da yukarı, lütfen. 530 00:24:02,290 --> 00:24:06,107 Ve meydan gidiyor bir deste sıralamak olmak. 531 00:24:06,107 --> 00:24:08,190 Ve yabancı ise, güverte Kartların gerekir sonuçta 532 00:24:08,190 --> 00:24:11,064 gibi küçük bir şey sıralanabilir Bu biz sonra, kulüpleri yapacağız nerede 533 00:24:11,064 --> 00:24:13,660 maça, ardından kupa ve Bir biri olarak ace gelen elmas, 534 00:24:13,660 --> 00:24:15,570 Kral kadar tüm yol. 535 00:24:15,570 --> 00:24:20,890 >> Kartları Sana vereceğim miktar 52 olacak. 536 00:24:20,890 --> 00:24:23,160 Biz benzer gidiyoruz Sadece bir an zaman sizi. 537 00:24:23,160 --> 00:24:26,410 Biz Andrew atmak için gidiyoruz Burada ekranda, 538 00:24:26,410 --> 00:24:28,170 Bunu gibi öylesine izlemek için. 539 00:24:28,170 --> 00:24:31,070 Ve böylece bu tüm bu , daha görünür 540 00:24:31,070 --> 00:24:33,490 Bu Ben Amazon üzerinde var kartlar. 541 00:24:33,490 --> 00:24:42,861 Yani rastgele zaten sıralanır ve sizi zaman zaman gidiyoruz. 542 00:24:42,861 --> 00:24:44,610 Ve biz gidiyoruz gerçek bu sefer tutmak 543 00:24:44,610 --> 00:24:47,820 bu yüzden size baskı denemek için gidiyoruz aksi halde, bu sıkıcı olsun çünkü 544 00:24:47,820 --> 00:24:48,460 hızlı. 545 00:24:48,460 --> 00:24:53,860 Eğer 52 sıralamak devam olsaydı Şimdi birlikte bazı yollarla unsurlar. 546 00:24:53,860 --> 00:25:04,710 547 00:25:04,710 --> 00:25:07,180 >> Ve yine, bu seyretmek gibi adamlar sonunda neler yapmak 548 00:25:07,180 --> 00:25:10,200 bariz bir üretecek Sonuç, gerçekten düşünmek 549 00:25:10,200 --> 00:25:12,962 nasıl her yapıyorsun, bunu nasıl açıklayabilir. 550 00:25:12,962 --> 00:25:15,045 Yine, bunlar için Tüm işlemler, algoritmalar 551 00:25:15,045 --> 00:25:17,090 Bir insan olarak kabul ediyoruz ki. 552 00:25:17,090 --> 00:25:22,349 Ama muhtemelen uzun yaşadım sezgi, sizden çok önce bile 553 00:25:22,349 --> 00:25:24,390 Bir alma konusunda düşünce bilgisayar bilimi sınıfı size 554 00:25:24,390 --> 00:25:27,223 sezgi vardı olabilir hangi böyle sorunları çözmek için. 555 00:25:27,223 --> 00:25:29,560 Ama bir kez Tanımadığınız desenler ve başlar 556 00:25:29,560 --> 00:25:32,407 ile adımları resmileştirmek için Eğer bu sorunları çözüyoruz, 557 00:25:32,407 --> 00:25:35,490 Eğer çok çözebilir bulacaksınız daha ilginç ve çok daha karmaşık 558 00:25:35,490 --> 00:25:39,190 Hızlı sorunlar. 559 00:25:39,190 --> 00:25:42,351 Yani seyirci birisi, ne algoritmanın en az bir element 560 00:25:42,351 --> 00:25:43,350 Burada kullanıyor olduğunuzu? 561 00:25:43,350 --> 00:25:44,275 >> İZLEYİCİ: [Duyulmaz] 562 00:25:44,275 --> 00:25:45,150 HOPARLÖR: Bu nedir? 563 00:25:45,150 --> 00:25:47,062 HEDEF KİTLE: takım olarak. 564 00:25:47,062 --> 00:25:47,770 HOPARLÖR: takım olarak. 565 00:25:47,770 --> 00:25:50,630 Böylece ilk onlar kümelendiği elmas hep birlikte 566 00:25:50,630 --> 00:25:52,560 o, bütün görünüyor Birlikte görünüyor kalpleri, 567 00:25:52,560 --> 00:25:56,520 ve benzeri, saygı olmadan kartlarındaki numaraları için. 568 00:25:56,520 --> 00:26:00,900 Ve şimdi onlar Örneğin, görünür, sayısına göre dizerek için. 569 00:26:00,900 --> 00:26:06,870 570 00:26:06,870 --> 00:26:08,910 Çok iyi. 571 00:26:08,910 --> 00:26:12,370 >> Pekala, ne oluyor Daha sonra burada son adım olacak? 572 00:26:12,370 --> 00:26:16,950 Dört sıralı suit, bir kez ne dört yığınları yapmam gerekiyor 573 00:26:16,950 --> 00:26:20,059 birini elde etmek için oldukça basit, güverte sıralanır? 574 00:26:20,059 --> 00:26:21,350 Yani biz onları tekrar birleştirmek gerekir. 575 00:26:21,350 --> 00:26:25,160 >> Yani ilginç bir fikir var ki Yine, daresay, hatta çok sezgisel 576 00:26:25,160 --> 00:26:28,140 Eğer tokatladı asla olabilir eğer Bunun üzerine etiket bu tür. 577 00:26:28,140 --> 00:26:31,900 Bölme Bu temel kavramı Sorun değil yarısı bu süre içinde, 578 00:26:31,900 --> 00:26:33,410 ama en az dört parçaya. 579 00:26:33,410 --> 00:26:36,810 Hemen hemen Çözme temelde aynı sorunlar 580 00:26:36,810 --> 00:26:40,480 birbirinden ayrı olarak, ve sonra sonuçları birleştirme. 581 00:26:40,480 --> 00:26:46,940 582 00:26:46,940 --> 00:26:50,140 Ve mükemmel, bitti. 583 00:26:50,140 --> 00:26:52,140 Pekala, büyük bir yuvarlak alkış, eğer biz yapabilirdik. 584 00:26:52,140 --> 00:26:56,480 >> [Alkış] 585 00:26:56,480 --> 00:26:59,740 >> HOPARLÖR: Ben ne olacak hiç bir fikrim yok Bu yapmak, ama burada gitmek. 586 00:26:59,740 --> 00:27:01,690 Çok teşekkür ederim. 587 00:27:01,690 --> 00:27:04,660 Yani, iki dakika görelim ve sekiz saniye, 588 00:27:04,660 --> 00:27:07,490 Eğer arkadaşlarınıza meydan istiyorsanız. 589 00:27:07,490 --> 00:27:12,160 Ne o gidiyor Bu uzak almak bir olmak 590 00:27:12,160 --> 00:27:13,830 daha genel olarak kaldıraç olabilir? 591 00:27:13,830 --> 00:27:16,080 Peki, geri düşünüyorum sayıların bu dizi, 592 00:27:16,080 --> 00:27:19,060 ve bazı geri şimdi düşünüyorum biz geçmişte yazdık pseudocode, 593 00:27:19,060 --> 00:27:22,080 ve bunun için yalancı kod oldu Telefon rehberi problem çözme. 594 00:27:22,080 --> 00:27:25,150 Bu sayede pseudocode I Bir daha metodik bir şekilde numaralandırılmış 595 00:27:25,150 --> 00:27:28,400 Ben bir çok sezgisel nasıl yaptığını anlatan Telefonu bölünmesi insan algoritması 596 00:27:28,400 --> 00:27:31,650 yarısında kitap, tekrar, tekrar, tekrar Ben bulana kadar Mike Smith gibi biri, 597 00:27:31,650 --> 00:27:33,790 O telefon defterinde gerçekten eğer. 598 00:27:33,790 --> 00:27:37,610 >> Ama ben tür ben ararım ne kullanılır Burada bir çok tekrarlayıcı bir yaklaşım, 599 00:27:37,610 --> 00:27:42,160 Özellikle haber hat 8 ve satır 11. 600 00:27:42,160 --> 00:27:46,750 Bunlar iteratif kanıtıdır yaklaşım, bir döngü yaklaşımı, 601 00:27:46,750 --> 00:27:49,040 tam olarak çünkü Onlar neden davranış. 602 00:27:49,040 --> 00:27:52,910 Bu satırlar, hem gitmek demek çizgi, üç, ve mümkün tür 603 00:27:52,910 --> 00:27:55,140 o düşünüyorum senin Bir döngü olarak zihnin gözü. 604 00:27:55,140 --> 00:27:59,080 Bu adıma kadar geri gitmek için söylüyor Üç ve tekrar, tekrar ve tekrar, 605 00:27:59,080 --> 00:28:00,010 ve yine. 606 00:28:00,010 --> 00:28:04,410 >> Ama ne bir anahtar fikir kaldıraç eğer Burada biz son kez yaptım, 607 00:28:04,410 --> 00:28:10,280 ve çizgi 8 basitleştirmek ve hat 11 ve komşularının 608 00:28:10,280 --> 00:28:12,840 Sadece bu, sarı gibi. 609 00:28:12,840 --> 00:28:16,480 Bu temelde kısaltarak değil çok pseudocode, 610 00:28:16,480 --> 00:28:20,530 ancak temelde değişiyor Benim algoritma doğası. 611 00:28:20,530 --> 00:28:24,220 Ne şimdi söylüyorum Aşama 7, adım 10'da, 612 00:28:24,220 --> 00:28:29,140 Mike aramak için aynı şekilde, 613 00:28:29,140 --> 00:28:31,580 ama sadece sol yarım veya sağ yarısı. 614 00:28:31,580 --> 00:28:33,420 >> Yani başka bir deyişle, eğer I, Aşama l'deki başlangıç 615 00:28:33,420 --> 00:28:36,150 , orta açık telefon kitap almak telefon rehberi, isimleri bakmak, 616 00:28:36,150 --> 00:28:39,010 Smith arasında ise, adı en Mike, başka çağrı 617 00:28:39,010 --> 00:28:44,340 Smith daha önce kitapta ise, yedi adım Kitabın sol yarısında Mike arayın. 618 00:28:44,340 --> 00:28:47,130 Ama bu tür gibi hissediyor Doğru, asılı beni terk ediyor? 619 00:28:47,130 --> 00:28:49,240 Sarı olarak, bir talimat, ama ben nasıl 620 00:28:49,240 --> 00:28:51,870 sol Mike aramak Telefon rehberinden yarısı? 621 00:28:51,870 --> 00:28:54,210 Ben bir Nerede var algoritması I 622 00:28:54,210 --> 00:28:57,100 Mike Smith gibi birisi için arama yapabilirsiniz? 623 00:28:57,100 --> 00:28:58,980 Peki, bu bize yüzüne bakıyor. 624 00:28:58,980 --> 00:29:03,090 Ben tam anlamıyla aynı kullanabilirsiniz Program etkin bir üstüne kadar gidiyor 625 00:29:03,090 --> 00:29:06,490 Tekrar ve tekrar çalışma aynı kod satırları. 626 00:29:06,490 --> 00:29:10,610 >> Peki bu bile hissetmeniz gerekir ama döngüsel bir tanım biraz gibi 627 00:29:10,610 --> 00:29:13,480 nerede birileri var yanıtlayan ediyoruz sadece sıralama sorarak sorusu 628 00:29:13,480 --> 00:29:15,990 Yine aynı soru, gibi neden, neden, neden? 629 00:29:15,990 --> 00:29:21,580 biz zor kodlanmış ettik çünkü gerçeklik özel çizgiler bir çift, adım 4, 630 00:29:21,580 --> 00:29:25,320 Bir, eğer, ve adım 12 olduğu hangi etkin bir dalıdır 631 00:29:25,320 --> 00:29:30,120 Biz bu eğreti önlemler var çünkü, Bu algoritma sona eğer biz 632 00:29:30,120 --> 00:29:32,050 Mike bulmak, ya da biz yapmazsan. 633 00:29:32,050 --> 00:29:36,810 Ama şimdi adım 7 ve 10, biz var ne bir özyinelemeli bir algoritma arayacağım. 634 00:29:36,810 --> 00:29:40,420 Ve yineleme gerçekten güçlü bir fikir Bu, ilk bakışta bükme küçük bir zihin var 635 00:29:40,420 --> 00:29:42,500 aşağıdaki gibi şimdi uygulayabilirsiniz. 636 00:29:42,500 --> 00:29:46,600 >> Birleştirme sıralama son sıralama olacak resmen en azından sınıfta bakmak. 637 00:29:46,600 --> 00:29:50,040 Ve bu temelde farklı kesinlikle bu son üç, ve gelen 638 00:29:50,040 --> 00:29:52,140 Son dört Biz Saçma sıralama eklerseniz. 639 00:29:52,140 --> 00:29:54,810 İşte birleştirme sıralama için pseudocode var. 640 00:29:54,810 --> 00:30:00,170 N elemanlarının girişi, yani verildiğinde n büyüklüğünde bir dizi, n, en az 2 olması durumunda 641 00:30:00,170 --> 00:30:01,040 dönmek. 642 00:30:01,040 --> 00:30:03,610 Peki neden bunu var aklı ilk kontrol edin? 643 00:30:03,610 --> 00:30:09,477 Seni el eğer ima neler var uzunluğu n bir dizi 2 azdır? 644 00:30:09,477 --> 00:30:11,060 Zaten doğru, tabii ki, sıralanır oluyor? 645 00:30:11,060 --> 00:30:13,640 Liste ya Çünkü trivially olan bir eleman, 646 00:30:13,640 --> 00:30:15,180 o çünkü kriteri Orada tek şey. 647 00:30:15,180 --> 00:30:18,138 Ya da, demek boyutu sıfır var sıralamak için hiçbir şey doğası gereği, böylece var 648 00:30:18,138 --> 00:30:18,720 o sıralanır. 649 00:30:18,720 --> 00:30:20,410 Orada yanlış sadece bir şey yok. 650 00:30:20,410 --> 00:30:22,310 Yani bizim sözde temel durum var. 651 00:30:22,310 --> 00:30:24,440 >> Bu ruhu benzer Biz Mike ile ne kadar. 652 00:30:24,440 --> 00:30:26,023 Mike telefon defterinde ise, onu aramak. 653 00:30:26,023 --> 00:30:27,740 Orada değilse, vazgeçmek. 654 00:30:27,740 --> 00:30:31,240 Bu sözde temel durum var, emin olmak için Günün sonunda bu algoritma 655 00:30:31,240 --> 00:30:33,540 Bazı durumlarda duracaktır. 656 00:30:33,540 --> 00:30:37,890 >> Ama burada inanç sıçrama, başka, şimdi var elemanların sol yarısı sıralamak 657 00:30:37,890 --> 00:30:39,740 sonra hakkını sıralamak elementlerin yarım, 658 00:30:39,740 --> 00:30:41,189 ve sonra sıralanmış yarıları birleştirme. 659 00:30:41,189 --> 00:30:43,230 Hissediyor Ve burada var gibi biz copping ediyoruz. 660 00:30:43,230 --> 00:30:46,900 Ben sıralamak istedim ettik n elemanları, ve ben 661 00:30:46,900 --> 00:30:50,712 sıralayarak, tamam, bunu yapmak söyleyerek Sol ve sağ sıralama. 662 00:30:50,712 --> 00:30:52,420 Ama ben bir tane söylüyorum Başka bir şey, ve bu 663 00:30:52,420 --> 00:30:55,530 öyle görünüyor ki anahtar tema Bugüne kadar sezgi olarak, 664 00:30:55,530 --> 00:30:57,380 birleştirme bu üçüncü adımı var. 665 00:30:57,380 --> 00:31:00,430 Hangi bile olsa , ruhu o kadar aptal görünüyor 666 00:31:00,430 --> 00:31:02,320 gibi sadece şeyler birleştirme Birlikte, öyle görünüyor 667 00:31:02,320 --> 00:31:05,380 doğru önemli bir adım olduğunu İki sorunların takılması ki 668 00:31:05,380 --> 00:31:07,330 devre sonunda ayrıldı. 669 00:31:07,330 --> 00:31:12,090 >> Yani olacak eğer, hadi yapalım, sıralama birleştirme bir daha gösteri ile mizah beni, 670 00:31:12,090 --> 00:31:14,730 sadece bu yüzden bazı var numaraları ile çalışmak. 671 00:31:14,730 --> 00:31:19,470 Ben sekiz stres alışverişinde Can Sekiz kişilik topları? 672 00:31:19,470 --> 00:31:29,320 Pekala, nasıl dört sen, üç size hakkında Bu bölümde, beş, altı, ve diyelim içinde 673 00:31:29,320 --> 00:31:30,720 7, 8, yukarı geliyor. 674 00:31:30,720 --> 00:31:35,120 675 00:31:35,120 --> 00:31:36,520 Tamam, evet, tamam. 676 00:31:36,520 --> 00:31:38,640 Eksi 8, oraya gidiyoruz, artı 1. 677 00:31:38,640 --> 00:31:39,150 Mükemmel. 678 00:31:39,150 --> 00:31:42,000 Pekala yukarı gel, haydi hızla size numaralarını vermek. 679 00:31:42,000 --> 00:31:50,800 İki numara, numara üç, dört numara, sayı beş, altı, yedi, sekiz. 680 00:31:50,800 --> 00:31:52,140 Ben doğru bu kez sekiz yaptım. 681 00:31:52,140 --> 00:31:56,390 >> Tamam, bu yüzden eğer yapabilirsen devam, ve orijinal düzende sıralamak izin 682 00:31:56,390 --> 00:31:59,810 Dün vardı baktım ki Bu gibi sakıncası olmaz eğer. 683 00:31:59,810 --> 00:32:03,620 Ve masanın önünde yapalım. 684 00:32:03,620 --> 00:32:06,510 Pekala, sıralama birleştirme. 685 00:32:06,510 --> 00:32:08,820 Gidiyor budur ilginç tür almak için, 686 00:32:08,820 --> 00:32:12,800 Kendimi veriyor gibi görünüyor, çünkü çok az bilgi bugün. 687 00:32:12,800 --> 00:32:15,149 >> Peki sıralama şeyden önce birleştirme n elemanlarının girişi, 688 00:32:15,149 --> 00:32:18,440 ve bu, tabii ki az iki Sekiz, ben yapmak için biraz daha fazla iş var. 689 00:32:18,440 --> 00:32:21,140 Şimdi zihinsel bir sınıf olarak Başka dalında şimdi, 690 00:32:21,140 --> 00:32:22,540 hangi üç adım anlamına gelir. 691 00:32:22,540 --> 00:32:25,017 Öncelikle, ben sıralamak zorunda elemanların sol yarısı. 692 00:32:25,017 --> 00:32:26,350 Peki nasıl bunu hakkında gidiyorsun? 693 00:32:26,350 --> 00:32:28,950 Eh, ben tür gidiyorum zihinsel burada liste bölmek, 694 00:32:28,950 --> 00:32:30,700 Eğer zorunda değilsiniz fiziksel hareket ve ben 695 00:32:30,700 --> 00:32:33,180 sadece odaklanmak olacak Burada elemanların sol yarısı. 696 00:32:33,180 --> 00:32:36,770 Yani sıralama hakkında nasıl gidiyor Şimdi boyutta dört bir liste? 697 00:32:36,770 --> 00:32:38,730 Benim algoritması nedir? 698 00:32:38,730 --> 00:32:42,580 Önce kontrol hayır, ikiden n az, Böylece tekrar başka bir bloğa devam. 699 00:32:42,580 --> 00:32:43,900 Sıralama elemanların yarı yaptı. 700 00:32:43,900 --> 00:32:45,608 >> Peki şimdi tekrar, zihinsel, ve bu nerede 701 00:32:45,608 --> 00:32:49,550 Eğer bir sürü tahakkuk zorunda zihinsel tarih, eğer sen. 702 00:32:49,550 --> 00:32:51,940 Şimdi sol sıralama ediyorum Sol yarısı yarısı. 703 00:32:51,940 --> 00:32:57,000 Pekala, şimdi benim aynı birleştirme çağrı sıralama algoritması, daha az iki N edilir? 704 00:32:57,000 --> 00:33:00,590 Hayır, iki, bu yüzden sıralamak zorunda sol yarım ve sağ yarım. 705 00:33:00,590 --> 00:33:02,042 Yani burada biz sol yarısını sıralamak, gidin. 706 00:33:02,042 --> 00:33:03,750 Neden sadece yok bir adım ileri götürmek. 707 00:33:03,750 --> 00:33:04,415 Adınız ne? 708 00:33:04,415 --> 00:33:04,860 >> İZLEYİCİ: Darren. 709 00:33:04,860 --> 00:33:05,260 >> HOPARLÖR: Dan. 710 00:33:05,260 --> 00:33:06,040 Dan öne çekildi. 711 00:33:06,040 --> 00:33:06,748 >> İZLEYİCİ: Darren. 712 00:33:06,748 --> 00:33:09,000 HOPARLÖR: Darren, bitti. 713 00:33:09,000 --> 00:33:10,090 Eğer Darren veya Dan dedin? 714 00:33:10,090 --> 00:33:10,550 >> İZLEYİCİ: Darren. 715 00:33:10,550 --> 00:33:11,216 >> HOPARLÖR: Darren. 716 00:33:11,216 --> 00:33:14,422 Tamam, Darren çekildi ileri ve şimdi sıralanır. 717 00:33:14,422 --> 00:33:16,130 Ve bu neredeyse bir olduğunu anlamsız iddia, değil mi? 718 00:33:16,130 --> 00:33:18,862 Gerçekten ulaşmak için görünmüyor şey, ama en devam edelim. 719 00:33:18,862 --> 00:33:20,820 Şimdi bana hakkını sıralamak izin elementlerin yarım. 720 00:33:20,820 --> 00:33:21,200 Adınız ne? 721 00:33:21,200 --> 00:33:21,690 >> İZLEYİCİ: Luke. 722 00:33:21,690 --> 00:33:22,273 >> HOPARLÖR: Luke. 723 00:33:22,273 --> 00:33:23,400 Hadi, ileri adım. 724 00:33:23,400 --> 00:33:25,640 Bitti, ben Luke sıralamış. 725 00:33:25,640 --> 00:33:28,570 Sol yarısı şimdi sıralanır ve Doğru yarısı şimdi, sıralanır 726 00:33:28,570 --> 00:33:30,770 ama yine, burada önemli bir adım var. 727 00:33:30,770 --> 00:33:32,940 Ne sonraki yapmam gerekiyor? 728 00:33:32,940 --> 00:33:33,941 Sıralanır yarıları Birleştirme. 729 00:33:33,941 --> 00:33:36,648 Şimdi sadece zorunda gidiyoruz ileri geri bu şekilde herkes, 730 00:33:36,648 --> 00:33:38,620 Ben tür ihtiyacım var çünkü Bazı çizik alanı. 731 00:33:38,620 --> 00:33:40,411 Neredeyse bu gibi adamlar masanın üzerinde, 732 00:33:40,411 --> 00:33:42,460 ve ben bazı oda ihtiyacım onları hareket etmek. 733 00:33:42,460 --> 00:33:44,170 Yani birleştirmek için gidiyorum bakarak siz 734 00:33:44,170 --> 00:33:45,960 Sol ve sağ yarısında yarıda. 735 00:33:45,960 --> 00:33:48,740 Ve tabii ki, ilk kim geliyor, Sol yarım veya sağ yarısı? 736 00:33:48,740 --> 00:33:52,710 Yani sağ yarısı, yani bitti Luke geçelim Burada Darren orijinal konumuna getirin. 737 00:33:52,710 --> 00:33:57,640 Ve şimdi sol yarısını birleştirmek için, Darren orada hareket edecek. 738 00:33:57,640 --> 00:33:59,750 >> Yani hemen hemen gibi hissediyor Bir kabarcık sıralama etkisi, 739 00:33:59,750 --> 00:34:02,482 ama benim temel algoritma, Bu sefer çok farklı. 740 00:34:02,482 --> 00:34:04,815 Şeyler nereden Ama şimdi var Biraz can sıkıcı senin yüzünden 741 00:34:04,815 --> 00:34:06,810 zihinsel sarmak zorunda Ben nerede kalmıştık. 742 00:34:06,810 --> 00:34:09,893 Ben sadece Sıralı yarıyı birleşti ettik, hangi Benim algoritması nerede olduğumu demek? 743 00:34:09,893 --> 00:34:12,229 744 00:34:12,229 --> 00:34:13,770 Ben sağ, sağ yarısını sıralamak zorunda? 745 00:34:13,770 --> 00:34:15,910 >> Kelimenin tam anlamıyla, geri alırsanız video, sen olacak 746 00:34:15,910 --> 00:34:18,339 Bu var olduğunu görmek Luke ve Darren noktası 747 00:34:18,339 --> 00:34:21,370 Sol sıralayarak Sol yarısı yarısı. 748 00:34:21,370 --> 00:34:23,430 Sonra o birleşti Sıralanan yarısı, hangi 749 00:34:23,430 --> 00:34:27,941 Bir sonraki adım, sıralama demektir Sol yarısı sağ yarısı. 750 00:34:27,941 --> 00:34:29,649 Pekala, diyelim daha hızlı yapmak. 751 00:34:29,649 --> 00:34:33,282 Pekala, altı, ben iddia gidiyorum Şimdi ileri gel, sıralanır. 752 00:34:33,282 --> 00:34:33,990 Adınız ne? 753 00:34:33,990 --> 00:34:34,589 >> İZLEYİCİ: Adriano. 754 00:34:34,589 --> 00:34:35,200 >> HOPARLÖR: Adriano. 755 00:34:35,200 --> 00:34:36,010 Adriano şimdi sıralanır. 756 00:34:36,010 --> 00:34:36,450 Ve senin adın ne? 757 00:34:36,450 --> 00:34:37,080 >> İZLEYİCİ: Alex. 758 00:34:37,080 --> 00:34:38,379 >> HOPARLÖR: Alex şimdi sıralanır. 759 00:34:38,379 --> 00:34:40,750 Sol yarım, sağ yarısı, Son adım nedir? 760 00:34:40,750 --> 00:34:41,250 Birleştirme. 761 00:34:41,250 --> 00:34:44,310 Oldukça önemsiz, ben değilim altı birleştirmek olacak, 762 00:34:44,310 --> 00:34:46,930 geri adım atmak, Sekiz, bir adım geri almak. 763 00:34:46,930 --> 00:34:49,530 Ve şimdi bu fark yararlı bir paket, ne 764 00:34:49,530 --> 00:34:53,930 Şimdi sol yarısı doğrudur Liste, bağımsız biz başladı nasıl? 765 00:34:53,930 --> 00:34:55,090 Bu sıralanır. 766 00:34:55,090 --> 00:34:57,750 >> Şimdi sıralanır değil şeylerin büyük düzeni, 767 00:34:57,750 --> 00:35:00,250 ancak bağımsız sıralanır diğer yarısı. 768 00:35:00,250 --> 00:35:04,100 Ben tutarsan Şimdi ne adım I am on Hikaye nasıl başladı sarma? 769 00:35:04,100 --> 00:35:05,680 Şimdi sağ yarısı sıralamak zorunda. 770 00:35:05,680 --> 00:35:07,630 Yani şimdi biz dönerken konum Hikayenin başlangıcı, 771 00:35:07,630 --> 00:35:08,921 ve en daha hızlı yapalım. 772 00:35:08,921 --> 00:35:11,320 Yani sıralamak için gidiyorum Bütün listesinin sağ yarısı. 773 00:35:11,320 --> 00:35:13,060 Bir sonraki adım nedir? 774 00:35:13,060 --> 00:35:15,840 Sağ yarısında sol yarısını sıralayın. 775 00:35:15,840 --> 00:35:18,715 Sol yarısını sırala Sağ yarısında sol yarısı. 776 00:35:18,715 --> 00:35:19,590 Ve senin adın ne? 777 00:35:19,590 --> 00:35:20,230 >> İZLEYİCİ: Ömer. 778 00:35:20,230 --> 00:35:21,970 >> HOPARLÖR: Ömer, ileri adım, bitti. 779 00:35:21,970 --> 00:35:22,860 Sol yarım sıralanır. 780 00:35:22,860 --> 00:35:23,330 Ve senin adın ne? 781 00:35:23,330 --> 00:35:23,820 >> İZLEYİCİ: Chris. 782 00:35:23,820 --> 00:35:25,620 >> HOPARLÖR: Chris, bir adım atmak ileri, şimdi sıralanır. 783 00:35:25,620 --> 00:35:27,010 Şimdi önemli bir adım nedir? 784 00:35:27,010 --> 00:35:27,510 Birleştirme. 785 00:35:27,510 --> 00:35:30,509 Yani bir yerde birleştirmek için gidiyor Burada, geri adım atması eğer, 786 00:35:30,509 --> 00:35:32,930 ve üç gidiyor birleştirme, bir adım geri almak. 787 00:35:32,930 --> 00:35:38,080 Yani sol yarısı Sağ yarım, şimdi sıralanır. 788 00:35:38,080 --> 00:35:41,747 Açıkçası, bu algoritma biz gibi hissediyor daha önce yol daha fazla zaman harcıyorsun, 789 00:35:41,747 --> 00:35:44,830 gerçek zamanlı olarak bunu ama eğer, biz olacak paketler olacak görmek. 790 00:35:44,830 --> 00:35:47,970 Şimdi burada ben sağ, ben Sağ yarısında yarısı, 791 00:35:47,970 --> 00:35:50,170 Beni go ahead ve sol yarısını sıralamak verelim. 792 00:35:50,170 --> 00:35:51,482 İleri Adım, senin adın ne? 793 00:35:51,482 --> 00:35:52,190 HEDEF KİTLE: Ramsey. 794 00:35:52,190 --> 00:35:53,210 HOPARLÖR: Ramsey şimdi sıralanır. 795 00:35:53,210 --> 00:35:53,570 Adınız ne? 796 00:35:53,570 --> 00:35:54,200 >> İZLEYİCİ: Marina. 797 00:35:54,200 --> 00:35:57,033 >> HOPARLÖR: Marina şimdi sıralanır iyi, ileri bir adım götürsem. 798 00:35:57,033 --> 00:36:00,690 Burada önemli bir adım şimdi ben, birleştirme edilir benim iki listelerden koparmak için gidiyoruz, 799 00:36:00,690 --> 00:36:01,720 sol ve sağ. 800 00:36:01,720 --> 00:36:05,150 Beş, ilk gelip gidiyor ve yedi yanındaki gelip gidiyor. 801 00:36:05,150 --> 00:36:06,410 Ve yine, bu kasıtlı olduğunu. 802 00:36:06,410 --> 00:36:08,535 onlar alıyorsun gerçeği ileri ve geri adım 803 00:36:08,535 --> 00:36:12,997 temsil etmek içindir ki biz değil kolayca yerine bu algoritmayı yapmak 804 00:36:12,997 --> 00:36:15,830 kabarcık sıralama, seçme ve sıralama gibi, ve yerleştirme sıralama nerede biz sadece 805 00:36:15,830 --> 00:36:16,960 insanları takas tuttu. 806 00:36:16,960 --> 00:36:19,940 Ben tam anlamıyla bir tür ihtiyaç karalama kağıdı olan 807 00:36:19,940 --> 00:36:21,827 Bu millet koymak Ben birleştirilmesi yaparken, 808 00:36:21,827 --> 00:36:23,410 ve sonra tekrar yerine koyabilirsiniz. 809 00:36:23,410 --> 00:36:27,260 Ben bir kullanıyorum çünkü bu anahtar yeni kaynak, uzay, sadece zaman. 810 00:36:27,260 --> 00:36:28,270 >> Tamam, bu inanılmaz. 811 00:36:28,270 --> 00:36:32,050 Sol yarısı doğru yarısı, sıralanır Sıralanan, şimdi anahtar birleştirme aşaması. 812 00:36:32,050 --> 00:36:33,450 Nasıl bu birleştirme gidiyorum? 813 00:36:33,450 --> 00:36:35,470 Eğer takip edeceğiz Yani benim Sol el ve sağ el, 814 00:36:35,470 --> 00:36:38,930 Ben sol elimi işaret gidiyorum Sol yarısında, benim sağ 815 00:36:38,930 --> 00:36:42,680 Sağ yarısında, ve şimdi var içinde birleştirmek için adım adım karar. 816 00:36:42,680 --> 00:36:44,650 Kim Açıkçası önce gelir? 817 00:36:44,650 --> 00:36:45,150 Bir numara. 818 00:36:45,150 --> 00:36:47,327 Yani buraya gel, Burada bizim karalama defteri var. 819 00:36:47,327 --> 00:36:49,910 Yani şimdi bir tane, ve haber sayı Sağ elimle ne yapacağım, 820 00:36:49,910 --> 00:36:54,152 Benim sağ bir hareket gidiyorum numara üç nokta üzerinde adım, 821 00:36:54,152 --> 00:36:55,860 ve şimdi yapmak zorunda Aynı karar. 822 00:36:55,860 --> 00:36:58,387 Ve aslında hakkını standı Luke burada eğer yapabilirsen ön, 823 00:36:58,387 --> 00:36:59,720 Bu bizim karalama defteri çünkü. 824 00:36:59,720 --> 00:37:00,610 Peki kim geliyor? 825 00:37:00,610 --> 00:37:05,000 Biz iki numaralı ile Luke var veya Chris numarası üç ile. 826 00:37:05,000 --> 00:37:07,460 Açıkçası Luke, sayı İki, bu yüzden buraya gelmek. 827 00:37:07,460 --> 00:37:11,270 >> Ama benim sol şimdi gidiyor Darren işaret etmek artırılır, 828 00:37:11,270 --> 00:37:15,160 ve burada anahtar ile take away var birleştirme, ben bunu yapmaya devam edeceğim, 829 00:37:15,160 --> 00:37:17,340 Açıkçası, eğer tür mantığını izleyin. 830 00:37:17,340 --> 00:37:19,670 Ama ellerim asla geriye gidecek, 831 00:37:19,670 --> 00:37:23,861 ki ben sadece hiç taşınıyorum demektir Benim birleştirme işlemi sol, 832 00:37:23,861 --> 00:37:26,360 ve bu anahtarı olacak Sadece bir an bizim analizi. 833 00:37:26,360 --> 00:37:27,859 >> Peki şimdi hızla bu kadar bitirelim. 834 00:37:27,859 --> 00:37:31,650 Yani üç yanında gelir, Daha sonra dört yanında gelir, 835 00:37:31,650 --> 00:37:38,750 ve şimdi beş altı, sonra, sonraki gelir Yedi, ve sonra nihayet sekiz ve. 836 00:37:38,750 --> 00:37:42,960 Yavaş algoritması gibi hissediyor Henüz, ama aslında biz eğer 837 00:37:42,960 --> 00:37:45,510 Aynı tür de çalıştırın Saat hızı, böylece 838 00:37:45,510 --> 00:37:48,106 ile aynı, konuşmak daha önce olduğu gibi saati geçiyor. 839 00:37:48,106 --> 00:37:48,605 Neden? 840 00:37:48,605 --> 00:37:51,100 Peki, bir atalım sonuçta bak. 841 00:37:51,100 --> 00:37:56,990 >> Geri buraya dönelim, bana izin görsel bir gösteri yukarı çekin 842 00:37:56,990 --> 00:37:59,030 biz sadece ne yaptığını. 843 00:37:59,030 --> 00:38:06,110 Bunun üzerine, burada yakınlaştırma Burada sayfa, Firefox söylüyorum 844 00:38:06,110 --> 00:38:08,200 Biz sıraya istiyorum Bu kutuya kadar, diyelim 845 00:38:08,200 --> 00:38:11,260 , kabarcık sıralama söylemek hangi biz artık iyi tanıdık 846 00:38:11,260 --> 00:38:14,130 Başka bir seçim sıralama, Oldukça basit bir, 847 00:38:14,130 --> 00:38:18,250 ve şimdi bugünün birleştirme sıralama, hangi Bizim iklim biten olacaktır. 848 00:38:18,250 --> 00:38:21,530 çok daha uzun sürdü bu yüzden nedeni Burada insanlar ve ben sözlü olduğunu 849 00:38:21,530 --> 00:38:23,480 Açıkçası, ben her adımı açıklayan ediyorum. 850 00:38:23,480 --> 00:38:26,920 Ama sadece bu, çok yürütmek durumunda gibi yaptığımız kabarcık sıralama ve seçme 851 00:38:26,920 --> 00:38:30,890 sıralama değil sadece görsel, izle sadece ne kadar daha verimli 852 00:38:30,890 --> 00:38:33,330 Bu kaldıraç bölünme ve fetih 853 00:38:33,330 --> 00:38:39,150 bu, bir veri seti için kullanılan zaman bile boyutu sekiz, ama hatta çok, 854 00:38:39,150 --> 00:38:39,970 çok daha büyük. 855 00:38:39,970 --> 00:38:44,585 Ben tarafından, sıralama yan birleştirme vermek bu algoritmaları ile yan. 856 00:38:44,585 --> 00:38:56,364 857 00:38:56,364 --> 00:38:58,530 Bu acı almak için gidiyor hızlı ve bitiş 858 00:38:58,530 --> 00:39:00,890 Özellikle iklim değil onlar sadece sıralanır sonuna kadar. 859 00:39:00,890 --> 00:39:05,280 Fakat anahtar olduğunu take away sıralama ne kadar hızlı birleştirme bakmak 860 00:39:05,280 --> 00:39:08,110 Eğer ben olduğumu düşünüyorum sürece, oldu sadece tür seninle karıştırmasını. 861 00:39:08,110 --> 00:39:13,100 Bu son bir kez yaparsanız, Şimdi bu yeniden izin, geri dönelim 862 00:39:13,100 --> 00:39:14,960 ve, kabarcık sıralama seçin ve sadece tekmeler için, 863 00:39:14,960 --> 00:39:17,330 en ekleme seçmenize izin sıralama, sadece iyi ölçmek için. 864 00:39:17,330 --> 00:39:20,020 Ve bu sefer yine diyelim birleştirme tür seçin ve atalım 865 00:39:20,020 --> 00:39:21,595 aslında yan bu yan çalıştırın. 866 00:39:21,595 --> 00:39:24,140 867 00:39:24,140 --> 00:39:26,930 >> Ve bir şans eseri, aslında değildir. 868 00:39:26,930 --> 00:39:31,140 Ne ben etkili yaptık Ben ettik olduğunu yine yarısında benim girişi bölünmüş 869 00:39:31,140 --> 00:39:32,240 ve tekrar ve tekrar. 870 00:39:32,240 --> 00:39:35,590 Ve yapabilirsiniz, sadece çok kez var yarıya içine girdi bölmek, sol 871 00:39:35,590 --> 00:39:36,240 ve sağ. 872 00:39:36,240 --> 00:39:39,425 Ne görmeye devam formülü Bu yarıda bölünme açıklar 873 00:39:39,425 --> 00:39:41,050 Tekrar ve tekrar, ve tekrar ve tekrar? 874 00:39:41,050 --> 00:39:41,890 >> İZLEYİCİ: n açın. 875 00:39:41,890 --> 00:39:42,760 >> HOPARLÖR: n açın. 876 00:39:42,760 --> 00:39:46,300 Ama sonra bir diğer önemli adım var, Bu algoritma günlük n adımlar değildir. 877 00:39:46,300 --> 00:39:48,992 Sadece log n olsaydı adımlar, Aynı sorun olurdu 878 00:39:48,992 --> 00:39:51,200 Biz olamaz nerede daha önce olduğu gibi Her şeyin en sıralanır. 879 00:39:51,200 --> 00:39:54,480 Sen minimal n elemanlı bakmak zorunda Emin olmak için n elemanlar sıralanır, 880 00:39:54,480 --> 00:39:55,950 aksi takdirde bir inanç sıçrama. 881 00:39:55,950 --> 00:39:59,810 >> Yani minimal oturum n adımlar, ama oluyor Bu anahtar birleştirme adımı ne olacak 882 00:39:59,810 --> 00:40:04,370 Ben birleşti benim sol yarım ve sağ Yarım ve sahnede yürüdü? 883 00:40:04,370 --> 00:40:06,980 Bu birleştirme kaç adım? 884 00:40:06,980 --> 00:40:10,150 Bu n var, ama ben sadece etmedi son bir kez birleştirme. 885 00:40:10,150 --> 00:40:15,089 Her üzerindeki bu yuvalanmış çağrıları her günü bu yuvalanmış birleştirmelerinin, ben hala sıralanır. 886 00:40:15,089 --> 00:40:18,380 Daha sonra bu iki bu iki adam, birleşti çocuklar, daha sonra bu iki adam ve benzeri. 887 00:40:18,380 --> 00:40:19,955 >> Bu yüzden tekrar birleştirme, ve yine yoktu. 888 00:40:19,955 --> 00:40:20,580 Kaç kere? 889 00:40:20,580 --> 00:40:23,510 Yani her zaman bölünmüş Liste yarısında, bir birleştirme yaptım. 890 00:40:23,510 --> 00:40:25,460 Bir birleştirme yapmak, yarısı listeyi bölün. 891 00:40:25,460 --> 00:40:28,570 Listeyi bölünmesi Yani eğer Günlük n kere yapılabilir, 892 00:40:28,570 --> 00:40:33,880 ve birleştirme sonuçta n alır adımlar, şimdi ne üst olabilir 893 00:40:33,880 --> 00:40:37,000 çalışan üzerinde bağlı Bizim algoritmanın zaman? 894 00:40:37,000 --> 00:40:37,980 n log. 895 00:40:37,980 --> 00:40:40,560 >> Ve gerçekten de, bu ne var Burada elde ettik. 896 00:40:40,560 --> 00:40:44,650 Yani görsel zaman görmek hissediyorum Bu üç şey yan yana çalıştırmak 897 00:40:44,650 --> 00:40:47,930 n n karşı karesi n günlük n karşı kare. 898 00:40:47,930 --> 00:40:51,010 Göreceğiz temelde Hangi, Bugün ancak gelecekte sadece, 899 00:40:51,010 --> 00:40:52,760 çok, çok daha hızlıdır. 900 00:40:52,760 --> 00:40:56,010 Bu adamlar için alkış yuvarlak, Ben stres topları ile onları ödüllendirecek. 901 00:40:56,010 --> 00:41:00,260 En Bugün burada erteleme edelim, ve biz Pazartesi günü göreceksiniz. 902 00:41:00,260 --> 00:41:02,255