1 00:00:00,000 --> 00:00:11,904 >> [MÜZİK OYUN] 2 00:00:11,904 --> 00:00:12,910 >> PROFESÖR: Pekala. 3 00:00:12,910 --> 00:00:16,730 Bu CS50 ve bu Haftanın üç sonu. 4 00:00:16,730 --> 00:00:20,230 Yani biz bugün burada değilsin, değil Sanders içinde Bunun yerine Weidner Kütüphanesi'nde Tiyatrosu. 5 00:00:20,230 --> 00:00:23,170 Hangi İçinde stüdyo Hauser Studio olarak bilinen, 6 00:00:23,170 --> 00:00:28,310 ya da biz Stüdyo H söylüyorlar, ya da yerine getirecektir O şaka zevk biz say--, 7 00:00:28,310 --> 00:00:30,540 o aslında var sınıf arkadaşı Mark, çevrimiçi, 8 00:00:30,540 --> 00:00:32,420 Kim Twitter üzerinden kadar önerdi. 9 00:00:32,420 --> 00:00:34,270 Şimdi hakkında serin ne bir stüdyoda burada olmak 10 00:00:34,270 --> 00:00:38,410 Ben bu yeşil çevrili ediyorum ki Duvarlar, bir yeşil ekran veya chromakey, 11 00:00:38,410 --> 00:00:43,290 yani CS50 en anlamına gelir konuşmak Bana habersizce üretim ekibi, 12 00:00:43,290 --> 00:00:47,380 Şu anda, koyarak olabilir Beni en dünyanın herhangi bir yerinde, 13 00:00:47,380 --> 00:00:48,660 iyi ya da kötü. 14 00:00:48,660 --> 00:00:51,800 >> Şimdi ne olacak ileride sorun set yatıyor İki, bu hafta sizin elinizde 15 00:00:51,800 --> 00:00:53,830 ama problem seti Üç önümüzdeki hafta, 16 00:00:53,830 --> 00:00:56,600 Sizinle meydan olacak 15 sözde oyun, 17 00:00:56,600 --> 00:00:58,960 Eski bir parti lehine olduğunu aldığınız çağırmak olabilir 18 00:00:58,960 --> 00:01:02,030 bir sürü sahip bir çocuk olarak aşağı, yukarı kayabilir sayılar, 19 00:01:02,030 --> 00:01:05,790 sol ve sağ, ve bir boşluk var bulmaca, içinde hangi içine 20 00:01:05,790 --> 00:01:07,840 aslında bu puzzle parçaları kayabilir. 21 00:01:07,840 --> 00:01:11,150 Sonuçta bu alıyorsunuz bazı yarı rastgele sırayla bulmaca, 22 00:01:11,150 --> 00:01:12,940 ve hedef olduğunu alt, üst sıralamak, 23 00:01:12,940 --> 00:01:16,310 bir ila soldan sağa kadar 15 tüm yol boyunca. 24 00:01:16,310 --> 00:01:19,360 >> Ne yazık ki, uygulama Elinizde gerekecek 25 00:01:19,360 --> 00:01:21,590 Yazılım olacak dayalı değil, fiziksel olarak. 26 00:01:21,590 --> 00:01:25,280 Aslında yazmak zorunda gidiyoruz kodu hangi bir öğrenci veya kullanıcı kutu ile 27 00:01:25,280 --> 00:01:26,760 15 oyun. 28 00:01:26,760 --> 00:01:29,030 Ve aslında, hacker 15 oyunun baskı, 29 00:01:29,030 --> 00:01:32,155 Bir meydan okuma uygulamak olacak, Bu eski okul sadece oyun 30 00:01:32,155 --> 00:01:35,010 Oyun değil, çözme Bunun, tanrı modunu uygulamak, 31 00:01:35,010 --> 00:01:38,280 bu yüzden, konuşmak için aslında insan için bulmaca çözer, 32 00:01:38,280 --> 00:01:41,080 ipucu sağlayarak, ipucu sonra, ipucu sonra. 33 00:01:41,080 --> 00:01:42,280 Bu önümüzdeki hafta Bu yüzden daha fazla. 34 00:01:42,280 --> 00:01:43,720 Ama önümüzde ne var. 35 00:01:43,720 --> 00:01:47,610 >> Şimdilik hatırlamak bu hafta başlarında eğer sen, biz, bu televizyon dizi film vardı 36 00:01:47,610 --> 00:01:52,560 böylece biz sıralama yaptıklarını iyi bilge n o büyük bir üst sınır oldu 37 00:01:52,560 --> 00:01:53,210 karesi. 38 00:01:53,210 --> 00:01:56,520 Diğer bir deyişle, kabarcık sıralama, seçmeli sıralama, ekleme sıralama, 39 00:01:56,520 --> 00:01:59,120 hepsi farklı ise Onların uygulanmasında, 40 00:01:59,120 --> 00:02:03,480 çalışan karesi bir n içine intikal Çok kötü durumda zaman. 41 00:02:03,480 --> 00:02:06,010 Ve biz genelde varsayalım sıralama çok kötü durum 42 00:02:06,010 --> 00:02:08,814 biri senin girdiler tamamen ters. 43 00:02:08,814 --> 00:02:11,980 Ve gerçekten de epeyce adımlar attı Bu algoritmaların her uygulamaktır. 44 00:02:11,980 --> 00:02:15,110 >> Şimdi sınıfın en sonunda hatırlama, biz kabarcık sıralama karşılaştırıldığında 45 00:02:15,110 --> 00:02:19,390 Diğer birine karşı seçim tür karşı biz, zaman birleştirme tür denilen 46 00:02:19,390 --> 00:02:22,120 ve bunu alıyor öneriyoruz hafta bir ders avantajı 47 00:02:22,120 --> 00:02:24,060 sıfır, böl ve fethet. 48 00:02:24,060 --> 00:02:28,810 Ve her nasılsa bir çeşit elde logaritmik sonuçta çalışma süresi, 49 00:02:28,810 --> 00:02:31,024 yerine bir şey Bu tamamen kuadratik var. 50 00:02:31,024 --> 00:02:33,440 Ve bu oldukça logaritmik değil o biraz daha fazla var. 51 00:02:33,440 --> 00:02:36,520 Ama sınıftan hatırlayacak olursak, çok daha hızlı, çok oldu. 52 00:02:36,520 --> 00:02:38,210 En bıraktığımız yerden bir göz atalım. 53 00:02:38,210 --> 00:02:41,880 54 00:02:41,880 --> 00:02:45,370 >> Seçim karşı Kabarcık sıralama sıralama birleştirme sıralama karşı. 55 00:02:45,370 --> 00:02:47,700 Şimdi tüm çalıştırıyorsanız teori, aynı zamanda. 56 00:02:47,700 --> 00:02:50,510 CPU aynı hızda çalışıyor. 57 00:02:50,510 --> 00:02:54,990 Ama ne kadar sıkıcı bu hissedebiliyorum çok çabuk olmaya devam etmektedir, 58 00:02:54,990 --> 00:02:58,790 ve ne kadar hızlı, ne zaman enjekte hafta Zero'nun algoritmalar biraz 59 00:02:58,790 --> 00:03:00,080 biz şeyleri hızlandırabilir. 60 00:03:00,080 --> 00:03:01,630 >> Yani mark sıralama muhteşem görünüyor. 61 00:03:01,630 --> 00:03:05,220 Nasıl sipariş, bunu kaldıraç daha hızlı sayıları sıralamak için. 62 00:03:05,220 --> 00:03:07,140 Peki geri düşünelim Bir maddeye biz 63 00:03:07,140 --> 00:03:10,380 bu hafta sıfır geri vardı Bir telefon rehberi birisi arıyor, 64 00:03:10,380 --> 00:03:12,380 ve hatırlatmak Biz teklif pseudocode, 65 00:03:12,380 --> 00:03:14,560 hangi aracılığıyla biz bulabilirsiniz Mike Smith gibi biri, 66 00:03:14,560 --> 00:03:16,310 Böyle küçük bir şey görünüyordu. 67 00:03:16,310 --> 00:03:20,820 >> Şimdi özellikle bir göz atın çizgisinde 7 ve 8, 10 ve 11, 68 00:03:20,820 --> 00:03:25,240 Biz tuttu sayede hangi o döngü neden Tekrar ve tekrar hat 3 gidiş, 69 00:03:25,240 --> 00:03:26,520 ve tekrar. 70 00:03:26,520 --> 00:03:31,790 Ama biz görebilirsiniz çıkıyor Bu algoritma, burada pseudocode, 71 00:03:31,790 --> 00:03:33,620 daha bütünsel biraz. 72 00:03:33,620 --> 00:03:35,960 Aslında, ben ne arıyorum Burada ekranda at, 73 00:03:35,960 --> 00:03:41,180 için arama için bir algoritma Bazı sayfaları kümesinden Mike Smith. 74 00:03:41,180 --> 00:03:45,520 Ve gerçekten biz bu basitleştirmek bu çizgiler 7 ve 8'de algoritması 75 00:03:45,520 --> 00:03:49,860 10 ve 11 sadece bu demek ki ben sarı Burada sunulan ettik. 76 00:03:49,860 --> 00:03:52,210 Diğer bir deyişle, Mike Smith, önceki kitapta olduğu 77 00:03:52,210 --> 00:03:55,004 Biz adım belirtmek gerekmez Adım şimdi nasıl onu bulmak gitmek. 78 00:03:55,004 --> 00:03:56,920 Biz belirtmek zorunda değilsiniz 3. satırda geri dönmek için, 79 00:03:56,920 --> 00:03:58,960 neden sadece yerine değil, örneğin, daha genel olarak, 80 00:03:58,960 --> 00:04:01,500 in Mike arama Kitabın sol yarısı. 81 00:04:01,500 --> 00:04:03,960 >> Bunun tersine, eğer Mike aslında daha sonra kitapta, 82 00:04:03,960 --> 00:04:07,540 Neden biz sadece unquote arama alıntı yok Kitabın sağ yarısında Mike. 83 00:04:07,540 --> 00:04:11,030 Diğer bir deyişle, neden sadece yok çeşit kendimizi diyerek punt, 84 00:04:11,030 --> 00:04:13,130 bu Mike için arama Kitabın alt kümesi, 85 00:04:13,130 --> 00:04:16,279 ve bizim mevcut bırakın algoritma bize 86 00:04:16,279 --> 00:04:18,750 in Mike aramak için nasıl Kitabın o sol yarısı. 87 00:04:18,750 --> 00:04:20,750 Diğer bir deyişle, eden algoritma olup olmadığını çalışıyor 88 00:04:20,750 --> 00:04:24,670 Bu bu kalınlıkta bir telefon rehberi, kalınlık, veya herhangi kalınlık. 89 00:04:24,670 --> 00:04:27,826 Yani biz recursively can Bu algoritmayı tanımlar. 90 00:04:27,826 --> 00:04:29,950 Diğer bir deyişle, ilgili Burada ekran bir algoritma 91 00:04:29,950 --> 00:04:33,130 Mike Smith için arama için Bir telefon kitabın sayfaları arasında. 92 00:04:33,130 --> 00:04:37,410 Yani hat 7 ve 10, diyelim sadece tam olduğunu söylüyorlar. 93 00:04:37,410 --> 00:04:40,250 Ve ben bu terimi bir an kullanmak önce, ve aslında, yineleme 94 00:04:40,250 --> 00:04:42,450 terim, şimdi içindir ve bu süreç 95 00:04:42,450 --> 00:04:47,210 nasılsa tarafından döngüsel bir şey yapma Eğer zaten kodu kullanarak, 96 00:04:47,210 --> 00:04:49,722 ve tekrar çağırarak ve tekrar ve tekrar. 97 00:04:49,722 --> 00:04:51,930 Şimdi önemli olacak Biz bir şekilde alt o 98 00:04:51,930 --> 00:04:53,821 dışarı ve sonsuz uzun bunu yapmayız. 99 00:04:53,821 --> 00:04:56,070 Aksi halde biz gidiyoruz gerçekten sonsuz bir döngüye sahiptir. 100 00:04:56,070 --> 00:04:59,810 Ama biz bu fikri ödünç alabilir bakalım Bir özyineleme, yine bir şey yapıyor 101 00:04:59,810 --> 00:05:03,600 ve tekrar ve tekrar, çözmek için birleştirme yoluyla sıralama sorunu 102 00:05:03,600 --> 00:05:05,900 sıralama, daha verimli. 103 00:05:05,900 --> 00:05:06,970 >> O yüzden birleştirmeli sıralama vermek. 104 00:05:06,970 --> 00:05:07,920 Hadi bir bakalım. 105 00:05:07,920 --> 00:05:10,850 Yani burada pseudocode ile, bir Biz sıralama uygulamak, hangi 106 00:05:10,850 --> 00:05:12,640 Birleştirme sıralama denilen bu algoritmayı kullanarak. 107 00:05:12,640 --> 00:05:13,880 Ve oldukça basit bu var. 108 00:05:13,880 --> 00:05:15,940 N elemanlarının girişi, Diğer bir deyişle, eğer 109 00:05:15,940 --> 00:05:18,830 Verilen n elemanlar ve numaralar ve Giriş ya da her neyse harfler, 110 00:05:18,830 --> 00:05:22,430 Eğer n elemanları, eğer verilen eğer burada n, 2 den az, sadece geri döner. 111 00:05:22,430 --> 00:05:22,930 Sağ? 112 00:05:22,930 --> 00:05:26,430 N, O, 2 daha az ise nedeniyle demek ki elemanların listemi 113 00:05:26,430 --> 00:05:30,446 boyut 0 ya da 1 ya da değil ve Bu önemsiz durumlarda her iki, 114 00:05:30,446 --> 00:05:31,570 liste zaten sıralanır. 115 00:05:31,570 --> 00:05:32,810 Hiçbir liste varsa, o tür var. 116 00:05:32,810 --> 00:05:35,185 Ve uzunlukta bir liste varsa 1, tabii ki sıralanmış oluyor. 117 00:05:35,185 --> 00:05:38,280 Yani algoritma sadece ihtiyacı Gerçekten ilginç bir şey yapmak, 118 00:05:38,280 --> 00:05:40,870 biz iki ya da daha fazla varsa elemanlar bize verilen. 119 00:05:40,870 --> 00:05:42,440 Yani o sihirli bakalım. 120 00:05:42,440 --> 00:05:47,500 Başka elemanların sol yarısını sıralamak Daha sonra elemanların sağ yarısını sıralamak, 121 00:05:47,500 --> 00:05:49,640 Sonra sıralanmış yarısını birleştirmek. 122 00:05:49,640 --> 00:05:52,440 Ve zihin bükme tür ne Burada, ben gerçekten yapmak olduğunu 123 00:05:52,440 --> 00:05:56,190 sana sahip görünüyor Henüz bir şey değil mi? 124 00:05:56,190 --> 00:05:59,560 Tüm Ben, bir liste verilir söyledim n elemanlar, sol yarısı sıralamak 125 00:05:59,560 --> 00:06:01,800 sonra sağ yarısı, daha sonra sıralanmış yarısını birleştirmek, 126 00:06:01,800 --> 00:06:03,840 ama nerede gerçek gizli sos nedir? 127 00:06:03,840 --> 00:06:05,260 Algoritma nerede? 128 00:06:05,260 --> 00:06:09,150 Peki bu iki satır çıkıyor İlk, elemanların çeşit sol yarısı, 129 00:06:09,150 --> 00:06:13,970 ve elemanların çeşit sağ yarısı, özyinelemeli aramalar, tabiri caizse. 130 00:06:13,970 --> 00:06:16,120 >> Sonuçta, bu da zaman içinde nokta, ben var 131 00:06:16,120 --> 00:06:18,950 hangi bir algoritma elemanlarının bir sürü sıralamak? 132 00:06:18,950 --> 00:06:19,450 Evet. 133 00:06:19,450 --> 00:06:20,620 Tam burada. 134 00:06:20,620 --> 00:06:25,180 Bu ekranda sağ burada ve bu yüzden adım aynı setini kullanabilirsiniz 135 00:06:25,180 --> 00:06:28,500 sol yarısı sıralamak için, sağ yarısı ben olabildiğince. 136 00:06:28,500 --> 00:06:30,420 Ve gerçekten, tekrar ve tekrar. 137 00:06:30,420 --> 00:06:34,210 Yani bir şekilde ya da başka ve biz yakında olacak , birleştirme tür sihirli görmek 138 00:06:34,210 --> 00:06:37,967 çok kesin gömülü olduğu çizgi, sıralı yarıları birleştirme. 139 00:06:37,967 --> 00:06:39,300 Ve bu oldukça sezgisel görünüyor. 140 00:06:39,300 --> 00:06:41,050 Sen seni iki yarıyı almak ve nasılsa, onları bir arada birleştirme, 141 00:06:41,050 --> 00:06:43,260 ve biz bu göreceğiz somut bir anda. 142 00:06:43,260 --> 00:06:45,080 >> Ama bu tam bir algoritmadır. 143 00:06:45,080 --> 00:06:46,640 Ve en tam olarak neden görelim. 144 00:06:46,640 --> 00:06:50,912 Peki biz bu aynı verilen konum varsayalım Ekranda burada sekiz elemanları, tek 145 00:06:50,912 --> 00:06:53,120 sekize kadar, ama onlar değil görünüşte rastgele sırayla. 146 00:06:53,120 --> 00:06:55,320 Ve eldeki hedeftir Bu öğeleri sıralamak için. 147 00:06:55,320 --> 00:06:58,280 Eh ben nasıl hakkında gidebilir Tekrar kullanarak yapıyor, 148 00:06:58,280 --> 00:07:00,407 Bu pseudocode göre, birleştirmeli sıralama? 149 00:07:00,407 --> 00:07:02,740 Ve yine, bu ingrain Aklını, sadece bir an için. 150 00:07:02,740 --> 00:07:05,270 Ilk vaka güzel önemsiz, bu 2'den az ise, 151 00:07:05,270 --> 00:07:07,060 Sadece yapılması gereken hiçbir iş yoktur, geri dönün. 152 00:07:07,060 --> 00:07:09,290 Yani gerçekten sadece üç var adımlar gerçekten akılda tutulması gereken. 153 00:07:09,290 --> 00:07:11,081 Tekrar ve tekrar, ben istiyorum olacak 154 00:07:11,081 --> 00:07:13,980 sol yarısı sıralamak için, Doğru yarısını sıralamak 155 00:07:13,980 --> 00:07:15,890 ve sonra bir kez kendi iki yarısı, sıralanır 156 00:07:15,890 --> 00:07:18,710 Ben onları bir arada birleştirmek istediğiniz tek sıralı liste halinde. 157 00:07:18,710 --> 00:07:19,940 Yani akılda tutmak. 158 00:07:19,940 --> 00:07:21,310 >> Yani burada asıl liste. 159 00:07:21,310 --> 00:07:23,510 Bunu bir şekilde bu tedavi edelim Dizi, biz başladık olarak 160 00:07:23,510 --> 00:07:25,800 haftada iki, burada a, bellek bitişik blok. 161 00:07:25,800 --> 00:07:28,480 Bu durumda, sekiz içeren sayılar, arka arkaya arkaya. 162 00:07:28,480 --> 00:07:30,700 Ve şimdi birleştirme tür uygulayalım. 163 00:07:30,700 --> 00:07:33,300 Yani ilk sıralamak istiyorum Bu listenin sol yarısı, 164 00:07:33,300 --> 00:07:37,370 ve bu nedenle, haydi 4, 8, 6, ve 2 üzerine odaklanır. 165 00:07:37,370 --> 00:07:41,000 >> Şimdi hakkında nasıl gitmek Boyut 4 listesini sıralama? 166 00:07:41,000 --> 00:07:45,990 Peki ben şimdi düşünmek zorundayız Sol yarısının sol sıralama. 167 00:07:45,990 --> 00:07:47,720 Yine, Sadece bir an için geri saralım. 168 00:07:47,720 --> 00:07:51,010 Sözde kod, bu ise, ve sekiz elemanları verilen ediyorum, 169 00:07:51,010 --> 00:07:53,230 8 açıkça daha fazladır daha ya da 2'ye eşittir. 170 00:07:53,230 --> 00:07:54,980 Yani ilk olgu geçerli değildir. 171 00:07:54,980 --> 00:07:58,120 Yani sekiz öğeleri sıralamak, ben birinci elemanların sol yarısını sıralamak 172 00:07:58,120 --> 00:08:01,930 Sonra ben o zaman ben birleştirme, sağ yarısını sıralamak İki sıralı yarısı, büyüklüğü 4 her. 173 00:08:01,930 --> 00:08:02,470 TAMAM. 174 00:08:02,470 --> 00:08:07,480 >> Sadece bana söyledim ama eğer sıralama Şimdi büyüklüğü 4 olan sol yarısı, 175 00:08:07,480 --> 00:08:09,350 nasıl sol yarısını sıralayabilirim? 176 00:08:09,350 --> 00:08:11,430 Peki ben bir varsa dört elementin giriş, 177 00:08:11,430 --> 00:08:14,590 Ben ilk sol sıralamak İki, sonra sağ iki 178 00:08:14,590 --> 00:08:16,210 ve sonra onları biraraya birleştirmek. 179 00:08:16,210 --> 00:08:18,700 Yani yine, biraz olur Bir zihin burada oyun bükme, 180 00:08:18,700 --> 00:08:21,450 Senin yüzünden, tür, var Eğer hikayenin neresinde hatırlıyorum, 181 00:08:21,450 --> 00:08:23,620 ama günün sonunda, elemanların herhangi bir numara verilir, 182 00:08:23,620 --> 00:08:25,620 İlk sıralamak istiyorum sol yarım, sonra sağ yarısı, 183 00:08:25,620 --> 00:08:26,661 daha sonra birlikte onları birleştirmek. 184 00:08:26,661 --> 00:08:28,630 En tam da bunu başlayalım. 185 00:08:28,630 --> 00:08:30,170 Burada sekiz elemanlarının giriş var. 186 00:08:30,170 --> 00:08:31,910 Şimdi burada sol yarısında bakıyoruz. 187 00:08:31,910 --> 00:08:33,720 Nasıl dört elementin sıralayabilirim? 188 00:08:33,720 --> 00:08:35,610 Peki ilk sol yarısını sıralayın. 189 00:08:35,610 --> 00:08:37,720 Şimdi nasıl sol yarısını sıralayabilirim? 190 00:08:37,720 --> 00:08:39,419 Eh iki unsuru verildi. 191 00:08:39,419 --> 00:08:41,240 Yani bu iki unsur sıralamak edelim. 192 00:08:41,240 --> 00:08:44,540 2 ya da daha büyük 2'ye eşit, tabii. 193 00:08:44,540 --> 00:08:46,170 Böylece ilk vaka geçerli değildir. 194 00:08:46,170 --> 00:08:49,010 >> Yani şimdi sol sıralamak zorunda Bu iki eleman yarısı kadardır. 195 00:08:49,010 --> 00:08:50,870 Sol yarısı, tabii ki sadece 4'ü. 196 00:08:50,870 --> 00:08:54,020 Peki nasıl bir elemanın bir listesini sıralamak mı? 197 00:08:54,020 --> 00:08:57,960 Eh şimdi, bu özel temel durum kontör, tabiri caizse, geçerlidir. 198 00:08:57,960 --> 00:09:01,470 1, 2'den küçük olduğunda, ve benim listesinin gerçekten boyutu 1 göstermektedir. 199 00:09:01,470 --> 00:09:02,747 Yani ben sadece dönün. 200 00:09:02,747 --> 00:09:03,580 Ben bir şey yapmıyorum. 201 00:09:03,580 --> 00:09:06,770 Ve gerçekten, ben var ne bakmak yapılan 4 zaten sıralanır. 202 00:09:06,770 --> 00:09:09,220 Sanki zaten değilim Burada kısmen başarılı. 203 00:09:09,220 --> 00:09:11,750 >> Şimdi bu tür aptalca görünüyor iddia, ama bu doğrudur etmek. 204 00:09:11,750 --> 00:09:13,700 4 boyutunda 1 listesidir. 205 00:09:13,700 --> 00:09:15,090 Zaten sıralanmış oluyor. 206 00:09:15,090 --> 00:09:16,270 O sol yarısı. 207 00:09:16,270 --> 00:09:18,010 Şimdi sağ yarısını sıralayın. 208 00:09:18,010 --> 00:09:22,310 Benim giriş 8, tek unsurdur Benzer şekilde, zaten sıralanır. 209 00:09:22,310 --> 00:09:25,170 Aptal, çok, ama yine Bu temel prensip 210 00:09:25,170 --> 00:09:28,310 Şimdi inşa etmek için izin gidiyor Bunun başarıyla. 211 00:09:28,310 --> 00:09:32,260 4 şimdi, 8 sıralanır sıralanır Bu son adım neydi? 212 00:09:32,260 --> 00:09:35,330 Bu nedenle, üçüncü ve son adım, herhangi bir zaman, bir liste, geri çağırma sıralama ediyoruz 213 00:09:35,330 --> 00:09:38,310 , iki yarısını birleştirmek oldu Sol ve sağ. 214 00:09:38,310 --> 00:09:39,900 O yüzden tam olarak yapalım. 215 00:09:39,900 --> 00:09:41,940 Benim sol yarısı, tabii ki, 4'tür. 216 00:09:41,940 --> 00:09:43,310 Benim sağ yarısı 8'dir. 217 00:09:43,310 --> 00:09:44,100 >> Yani bu yapalım. 218 00:09:44,100 --> 00:09:46,410 Önce tahsis gidiyorum bazı ek bellek, 219 00:09:46,410 --> 00:09:48,680 Ben burada temsil edeceğiz sadece ikincil bir dizi olarak, 220 00:09:48,680 --> 00:09:49,660 bu sığacak kadar büyük. 221 00:09:49,660 --> 00:09:52,243 Ama uzanan hayal edebiliyorum Bu dikdörtgen tüm uzunluğu, 222 00:09:52,243 --> 00:09:53,290 daha sonra gerekirse. 223 00:09:53,290 --> 00:09:58,440 Ben 4 alıp 8 ve birleştirme nasıl Birlikte büyüklüğü 1 bu iki liste? 224 00:09:58,440 --> 00:10:00,270 Burada da oldukça basit. 225 00:10:00,270 --> 00:10:03,300 4 Sonra, önce gelir 8 geliyor. 226 00:10:03,300 --> 00:10:07,130 Ben sıralamak isterseniz Çünkü sol yarım, sonra sağ yarısı, 227 00:10:07,130 --> 00:10:09,900 ve daha sonra bu iki yarısı birleştirme Birlikte, sıralı sırayla, 228 00:10:09,900 --> 00:10:11,940 4 Sonra, önce gelir 8 geliyor. 229 00:10:11,940 --> 00:10:15,810 >> Yani biz bile ilerleme gibi görünüyor Ben herhangi bir fiili çalışma yapmadım ama. 230 00:10:15,810 --> 00:10:17,800 Biz hikayenin neresinde Ama unutmayın. 231 00:10:17,800 --> 00:10:19,360 Biz aslında sekiz elemanları aldı. 232 00:10:19,360 --> 00:10:21,480 Biz 4 olan sol yarısı, sıralanmış. 233 00:10:21,480 --> 00:10:24,450 Sonra sol yarısı kriteri 2 oldu sol yarısı, bir. 234 00:10:24,450 --> 00:10:25,270 Ve işte başlıyoruz. 235 00:10:25,270 --> 00:10:26,920 Biz o adımı bitirdik. 236 00:10:26,920 --> 00:10:29,930 >> Biz sıralama ettik Yani eğer biz şimdi, 2 yarım bıraktı 237 00:10:29,930 --> 00:10:32,130 2 sağ yarısını sıralamak gerekir. 238 00:10:32,130 --> 00:10:35,710 Yani 2 sağ yarısı Burada bu iki değer, 6 ve 2. 239 00:10:35,710 --> 00:10:40,620 O halde şimdi büyüklükte bir giriş atalım 2, ardından da sol yarısı sıralamak ve 240 00:10:40,620 --> 00:10:42,610 sağ yarısı, ve sonra onları biraraya birleştirmek. 241 00:10:42,610 --> 00:10:45,722 Peki nasıl büyüklükte bir listesini sıralamak do 1, sadece 6 sayı içeren? 242 00:10:45,722 --> 00:10:46,430 Zaten bitti. 243 00:10:46,430 --> 00:10:48,680 Büyüklüğü 1 Bu liste sıralanır. 244 00:10:48,680 --> 00:10:52,140 >> Ben başka bir listesini sıralamak nasıl Boyut 1 olarak adlandırılan sağ yarısını. 245 00:10:52,140 --> 00:10:54,690 Eh o da, zaten sıralanır. 246 00:10:54,690 --> 00:10:56,190 2 numaralı yalnız. 247 00:10:56,190 --> 00:11:00,160 Yani şimdi ben iki yarısı var, sol ve Tamam, ben onları bir araya birleştirmek gerekir. 248 00:11:00,160 --> 00:11:01,800 Gidip kendime bazı ekstra boşluk vereyim. 249 00:11:01,800 --> 00:11:05,580 Ve orada, 2 koyun daha sonra 6 Orada, bu suretle 250 00:11:05,580 --> 00:11:10,740 Bu listeyi sıralama, sol ve sağ ve sonuçta birlikte birleştirme. 251 00:11:10,740 --> 00:11:12,160 Yani biraz daha durumdayım. 252 00:11:12,160 --> 00:11:16,250 Ben, bitmiş çünkü değilim açıkça 4, 8, 2, 6 istediğim son sipariş değildir. 253 00:11:16,250 --> 00:11:20,640 Ama şimdi, bu boyutta 2 iki listeleri vardır her ikisi de sırasıyla kriteri edilmiştir. 254 00:11:20,640 --> 00:11:24,580 Yani şimdi zihninizi en içinde geri sarma durumunda göz, ​​bu bizi nereye mi? 255 00:11:24,580 --> 00:11:28,520 Daha sonra, sekiz elemanları ile başladı ben 4, sol yarısında aşağı whittled 256 00:11:28,520 --> 00:11:31,386 Daha sonra 2 sol yarısı ve Daha sonra 2 sağ yarısı, 257 00:11:31,386 --> 00:11:34,510 Ben sol sıralama, bu nedenle, bitmiş 2 yarısı ve 2'nin sağ yarısı, 258 00:11:34,510 --> 00:11:37,800 Üçüncü ve son adım burada ne var? 259 00:11:37,800 --> 00:11:41,290 Birlikte birleştirmek zorunda büyüklüğü 2 iki listeleri. 260 00:11:41,290 --> 00:11:42,040 O yüzden önümüzdeki gidelim. 261 00:11:42,040 --> 00:11:43,940 Ve burada ekranda vermek Bana bazı ek bellek, 262 00:11:43,940 --> 00:11:47,170 teknik olsa da, ben fark ettik boşluk kadar üst bir sürü var 263 00:11:47,170 --> 00:11:47,670 Orada. 264 00:11:47,670 --> 00:11:50,044 Özellikle olmak istiyorum verimli kullanım alanı bilge, 265 00:11:50,044 --> 00:11:52,960 Ben sadece elemanları hareketli başlayabileceğini ileri ve geri, alt ve üst. 266 00:11:52,960 --> 00:11:55,460 Ama Görsel netlik için, Ben, aşağıda bir yere koymak için gidiyorum 267 00:11:55,460 --> 00:11:56,800 güzel ve temiz şeyleri tutmak için. 268 00:11:56,800 --> 00:11:58,150 >> Yani büyüklüğü 2 iki liste var. 269 00:11:58,150 --> 00:11:59,770 İlk liste 4 ve 8 sahiptir. 270 00:11:59,770 --> 00:12:01,500 İkinci liste 2 ve 6 sahiptir. 271 00:12:01,500 --> 00:12:03,950 Hadi şu birleşmesine izin Birlikte sıralı sırayla. 272 00:12:03,950 --> 00:12:09,910 2, tabii ki, önce gelir, daha sonra 4, sonra 6, daha sonra 8. 273 00:12:09,910 --> 00:12:12,560 Ve şimdi biz almak gibi görünüyor ilginç bir yerde. 274 00:12:12,560 --> 00:12:15,720 Şimdi ben kriteri ettik yarısı listelemek ve tesadüfen, bu kadar 275 00:12:15,720 --> 00:12:18,650 tüm çift sayılar, ancak gerçekten, sadece bir tesadüftür. 276 00:12:18,650 --> 00:12:22,220 Ve ben şimdi sol sıralamış Yarım, 2, 4, 6 ve 8 olacak şekilde. 277 00:12:22,220 --> 00:12:23,430 Hiçbir şey sipariş dışında. 278 00:12:23,430 --> 00:12:24,620 Bu ilerleme gibi hissediyor. 279 00:12:24,620 --> 00:12:26,650 >> Ben ettik gibi şimdi hissediyor Şimdi sonsuza konuşuyor, 280 00:12:26,650 --> 00:12:29,850 ne yani eğer bu görülecektir Algoritma gerçekten daha verimli olduğunu. 281 00:12:29,850 --> 00:12:31,766 Ama biz doğru gidiyoruz Süper yöntemli. 282 00:12:31,766 --> 00:12:34,060 Bir bilgisayar, tabii ki, bunu böyle yapardı. 283 00:12:34,060 --> 00:12:34,840 Yani biz neredeyiz? 284 00:12:34,840 --> 00:12:36,180 Biz sekiz elemanları ile başladı. 285 00:12:36,180 --> 00:12:37,840 Ben 4 sol yarısını sıralanır. 286 00:12:37,840 --> 00:12:39,290 Ben ile yapılabilir gibi görünüyor. 287 00:12:39,290 --> 00:12:42,535 Şimdi bir sonraki adım için 4 sağ yarısını sıralayın. 288 00:12:42,535 --> 00:12:44,410 Ve bu bölüm gidebiliriz Biraz daha fazlasından 289 00:12:44,410 --> 00:12:47,140 hızlı, sen her ne kadar Sadece, geri sarma ya da duraklatmak için hoş geldiniz 290 00:12:47,140 --> 00:12:49,910 En içinden düşünüyorum Kendi hızı, ama ne 291 00:12:49,910 --> 00:12:53,290 Şimdi bir fırsat olduğunu var Dört kesin aynı algoritmayı yapmak 292 00:12:53,290 --> 00:12:54,380 Farklı numaralar. 293 00:12:54,380 --> 00:12:57,740 >> O yüzden önümüzdeki gidelim ve odaklanmak biz buradayız sağ yarısı. 294 00:12:57,740 --> 00:13:01,260 Bu sol yarısı sağ yarısı, ve şimdi 295 00:13:01,260 --> 00:13:04,560 sol sol yarısı O sağ yarısında yarısı, 296 00:13:04,560 --> 00:13:08,030 ve ben boyutta bir listesini sıralamak nasıl 1 Sadece 1 numara içeren? 297 00:13:08,030 --> 00:13:09,030 Çoktan bitti. 298 00:13:09,030 --> 00:13:11,830 Ben bir liste için aynı şeyi nasıl sadece 7 içeren büyüklüğü 1? 299 00:13:11,830 --> 00:13:12,840 Çoktan bitti. 300 00:13:12,840 --> 00:13:16,790 O zaman bu yarısı için üç adım Bu iki unsur birleştirmek olduğunu 301 00:13:16,790 --> 00:13:20,889 büyüklüğü 2, 1 ve 7 yeni liste halinde. 302 00:13:20,889 --> 00:13:23,180 Tüm yapmış görünmemektedir o kadar ilginç bir çalışma. 303 00:13:23,180 --> 00:13:24,346 Bir sonraki ne görelim. 304 00:13:24,346 --> 00:13:29,210 Ben sadece sol yarısını kriteri Benim asıl girişin sağ yarısı. 305 00:13:29,210 --> 00:13:32,360 Şimdi hakkını sıralamak edelim 5 ve 3 içeren yarısı. 306 00:13:32,360 --> 00:13:35,740 Tekrar solda bakalım Yarım, sıralı, sağ yarısı, sıralı, 307 00:13:35,740 --> 00:13:39,120 ve birlikte bu iki birleştirme bazı ek uzaya, 308 00:13:39,120 --> 00:13:41,670 3 Daha sonra, önce gelir 5 geliyor. 309 00:13:41,670 --> 00:13:46,190 Ve şimdi, biz sıralamış sağ yarısında sol yarısı 310 00:13:46,190 --> 00:13:49,420 Özgün bir sorun, ve Doğru yarısı sağ yarısı 311 00:13:49,420 --> 00:13:50,800 Özgün bir sorun. 312 00:13:50,800 --> 00:13:52,480 Üçüncü ve son adım nedir? 313 00:13:52,480 --> 00:13:54,854 Peki birlikte bu iki yarısını birleştirmek için. 314 00:13:54,854 --> 00:13:57,020 Yani beni kendime biraz olsun izin Yine ekstra alan, ancak, ben 315 00:13:57,020 --> 00:13:58,699 Bu yedek alan kadar üst kullanıyor olabilir. 316 00:13:58,699 --> 00:14:00,490 Ama biz devam edeceğiz görsel basit. 317 00:14:00,490 --> 00:14:07,070 Şimdi beni 1'de birleşmesine izin ve daha sonra 3 ve 5, ve daha sonra 7. 318 00:14:07,070 --> 00:14:10,740 Böylece şimdi beni terk Orijinal problemin sağ yarısı 319 00:14:10,740 --> 00:14:12,840 Bu mükemmel olarak sıralanmış. 320 00:14:12,840 --> 00:14:13,662 >> Peki ne kalır? 321 00:14:13,662 --> 00:14:16,120 Ben deyip duruyorsun gibi hissediyorum tekrar ve tekrar aynı şeyler, 322 00:14:16,120 --> 00:14:18,700 ama bu yansıtıcı var: Biz özyineleme kullanıyoruz aslında. 323 00:14:18,700 --> 00:14:21,050 Bir kullanarak süreci tekrar ve tekrar algoritması, 324 00:14:21,050 --> 00:14:23,940 küçük alt kümeleri üzerinde orijinal sorun. 325 00:14:23,940 --> 00:14:27,580 Yani şimdi sol sıralamış Orijinal sorunun yarısı. 326 00:14:27,580 --> 00:14:30,847 Ben sağ sıralı yarısı var Özgün bir sorun. 327 00:14:30,847 --> 00:14:32,180 Üçüncü ve son adım nedir? 328 00:14:32,180 --> 00:14:33,590 Oh, birleştirme ediyor. 329 00:14:33,590 --> 00:14:34,480 O yüzden böyle yapalım. 330 00:14:34,480 --> 00:14:36,420 En bazı ek tahsis edelim Bellek, ama Tanrım, biz 331 00:14:36,420 --> 00:14:37,503 Şimdi her yerde koyabilirsiniz. 332 00:14:37,503 --> 00:14:40,356 Biz çok alan mevcut olması Bize, ama biz basit tutacağız. 333 00:14:40,356 --> 00:14:42,730 Yerine geri gitmeyi ve ileri bizim orijinal bellek ile, 334 00:14:42,730 --> 00:14:44,480 Sadece bunu diyelim görsel aşağıda aşağı 335 00:14:44,480 --> 00:14:47,240 birleştirme kadar bitirmek için sol yarım ve sağ yarım. 336 00:14:47,240 --> 00:14:49,279 >> Birleştirerek Eee, ne yapmam gerekiyor? 337 00:14:49,279 --> 00:14:50,820 Ben sırayla öğeleri almak istiyorum. 338 00:14:50,820 --> 00:14:53,230 Yani sol yarısı bakarak, İlk sayı 2 görüyoruz. 339 00:14:53,230 --> 00:14:55,230 Ben sağ yarısında bakmak, Ben ilk sayısını görmek 340 00:14:55,230 --> 00:14:58,290 çok açıktır ki, 1 olan sayı, ben dışarı koparmak istiyor musunuz 341 00:14:58,290 --> 00:15:00,430 ve benim son listenin ilk koydu? 342 00:15:00,430 --> 00:15:01,449 Tabii ki, 1. 343 00:15:01,449 --> 00:15:02,990 Şimdi aynı soruyu sormak istiyorum. 344 00:15:02,990 --> 00:15:05,040 Sol yarısı, ben ettik Hala sayı 2 aldım. 345 00:15:05,040 --> 00:15:07,490 Sağ yarısında, Ben 3 numaralı var. 346 00:15:07,490 --> 00:15:08,930 Hangisini seçmeliyim istiyorsun? 347 00:15:08,930 --> 00:15:11,760 Tabii ki, sayı 2 ve Şimdi adaylar dikkat 348 00:15:11,760 --> 00:15:13,620 sağda solda, 3 4 vardır. 349 00:15:13,620 --> 00:15:15,020 En, tabii ki, 3 seçelim. 350 00:15:15,020 --> 00:15:18,020 Şimdi adaylar 4 üzerinde sağ sol, 5. 351 00:15:18,020 --> 00:15:19,460 Biz, tabii ki, 4 seçin. 352 00:15:19,460 --> 00:15:21,240 Sağda solda, 5 6. 353 00:15:21,240 --> 00:15:22,730 Biz, tabii ki, 5 seçin. 354 00:15:22,730 --> 00:15:25,020 Sağda solda, 7 6. 355 00:15:25,020 --> 00:15:29,320 Biz 6 seçin ve sonra biz 7 seçin, ve sonra biz 8 seçin. 356 00:15:29,320 --> 00:15:30,100 Işte. 357 00:15:30,100 --> 00:15:34,370 >> Kelimelerin Yani çok sayıda sonra, biz Sekiz elemanların listesini sıralamış 358 00:15:34,370 --> 00:15:38,450 sekize kadar birinin bir liste halinde, Bu, her adımda artıyor 359 00:15:38,450 --> 00:15:40,850 ama ne kadar zaman yaptım bunu yapmak için bizi. 360 00:15:40,850 --> 00:15:43,190 Eh ben kasten ettik resimsel koydu şeyler dışarı 361 00:15:43,190 --> 00:15:46,330 Burada, böylece biz tür bakın veya bölünme takdir 362 00:15:46,330 --> 00:15:49,060 fetih o oluyor oldu. 363 00:15:49,060 --> 00:15:52,830 >> Eğer sonrasında geri bakmak Nitekim eğer, Ben bu noktalı çizgiler tüm bıraktım 364 00:15:52,830 --> 00:15:55,660 Yer tutuculara yapabilirsiniz, tür, tersten görmek, 365 00:15:55,660 --> 00:15:58,800 ne tür geri bakmak Tarih şimdi, benim orijinal liste 366 00:15:58,800 --> 00:16:00,250 büyüklüğü, 8, tabii ki,. 367 00:16:00,250 --> 00:16:03,480 Ve sonra önceden, ben büyüklüğü 4 iki liste ile ilgili, 368 00:16:03,480 --> 00:16:08,400 ve daha sonra büyüklüğü 2 dört listeleri, ve daha sonra büyüklüğü 1 sekiz listeleri. 369 00:16:08,400 --> 00:16:10,151 >> Peki bu ne, tür, size hatırlatmak? 370 00:16:10,151 --> 00:16:11,858 Kuyu, gerçekten, herhangi bir biz ettik algoritmalar 371 00:16:11,858 --> 00:16:14,430 bugüne kadar baktı nerede böl ve bölme ve bölme, 372 00:16:14,430 --> 00:16:19,500 şeyleri tekrar sahip tutmak ve yine, bu genel bir fikir ile sonuçlanır. 373 00:16:19,500 --> 00:16:23,100 Ve böylece bir şey var logaritmik burada olacak. 374 00:16:23,100 --> 00:16:26,790 Ve n oldukça günlüğü değil ama logaritmik bileşen var 375 00:16:26,790 --> 00:16:28,280 biz sadece yaptığına. 376 00:16:28,280 --> 00:16:31,570 >> Şimdi aslında nasıl düşünelim. 377 00:16:31,570 --> 00:16:34,481 Yani yine, n log oldu büyük bir çalışma süresi, 378 00:16:34,481 --> 00:16:36,980 Biz böyle bir şey yaptım ikili arama, biz şimdi dediğimiz gibi, 379 00:16:36,980 --> 00:16:40,090 böl ve fethet stratejisi hangi aracılığıyla Mike Smith bulundu. 380 00:16:40,090 --> 00:16:41,020 Şimdi teknik olarak. 381 00:16:41,020 --> 00:16:43,640 Bu bile, n log tabanı 2 var En matematik derslerinde olsa, 382 00:16:43,640 --> 00:16:45,770 10 genellikle varsayıyorum temelidir. 383 00:16:45,770 --> 00:16:48,940 Ama bilgisayar bilim adamları hemen hemen her zaman düşünmek ve tabanının 2 açısından konuşmak, 384 00:16:48,940 --> 00:16:52,569 Böylece biz genellikle sadece günlüğünü demek n yerine n log tabanı 2, 385 00:16:52,569 --> 00:16:55,110 ama onlar tam bir konum ve bilgisayar dünyasında aynı 386 00:16:55,110 --> 00:16:57,234 bilim ve bir kenara olarak, Bir sabit faktör var 387 00:16:57,234 --> 00:17:01,070 İkisi arasındaki fark, bu yüzden Daha resmi nedenlerle, zaten tartışmalı. 388 00:17:01,070 --> 00:17:04,520 >> Ama şimdi, biz umurumda ilgili bu örnektir. 389 00:17:04,520 --> 00:17:08,520 Yani örnek ispat etmeyelim, ama en En sayıların bir örnek kullanın 390 00:17:08,520 --> 00:17:10,730 elinde bir sağlamlık denetimi olarak, eğer olacaktır. 391 00:17:10,730 --> 00:17:14,510 Yani daha önce formül günlüğü üssü oldu N 2, ancak bu durumda n budur. 392 00:17:14,510 --> 00:17:18,526 Ben n orijinal numaralar vardı, ya da 8 Orijinal sayının özellikle. 393 00:17:18,526 --> 00:17:20,359 Şimdi biraz oldu süre, ama ben oldukça 394 00:17:20,359 --> 00:17:25,300 emin günlük taban 2 8 3 olan değer, 395 00:17:25,300 --> 00:17:29,630 ve aslında ne olduğunu hakkında güzel 3 kaç kez tam sayıdır 396 00:17:29,630 --> 00:17:33,320 Eğer bir liste bölebilirsiniz olduğunu tekrar ve tekrar uzunluğunda, 8, 397 00:17:33,320 --> 00:17:36,160 ve yine, kalacaksın kadar Sadece büyüklük 1 listeleri ile. 398 00:17:36,160 --> 00:17:36,660 Sağ? 399 00:17:36,660 --> 00:17:40,790 8, 4 gider 2'ye gider 1 gider ve işte 400 00:17:40,790 --> 00:17:43,470 tam olarak yansıtıcı resim biz sadece bir an önce vardı. 401 00:17:43,470 --> 00:17:47,160 Bu yüzden biraz aklı olarak nerede kontrol logaritma aslında yer almaktadır. 402 00:17:47,160 --> 00:17:50,180 >> Yani şimdi, başka ne burada söz konusu olan? n. 403 00:17:50,180 --> 00:17:53,440 Böylece her fark zaman, liste bölmek 404 00:17:53,440 --> 00:17:58,260 Tarihte tersten olsa Burada, ben hala n şeyler yapıyordu. 405 00:17:58,260 --> 00:18:02,320 Bu birleştirme aşaması olması gerekmektedir Ben, sayıların her birine dokunmak 406 00:18:02,320 --> 00:18:05,060 doğru kaydırın amacıyla kendine uygun bir yer. 407 00:18:05,060 --> 00:18:10,760 Yani olsa da bu yüksekliği diyagramı, n ya da 3'ün günlük boyutunu n olduğu 408 00:18:10,760 --> 00:18:13,860 özel olarak ise, bir başka deyişle, Burada üç tümen yaptı. 409 00:18:13,860 --> 00:18:18,800 Ne kadar iş ben yatay yaptın Bu tabloda her seferinde boyunca? 410 00:18:18,800 --> 00:18:21,110 >> Eh, ben n adımları yaptım Ben ettik çünkü eğer, işe 411 00:18:21,110 --> 00:18:24,080 , dört elementin ve dört unsuru var ve ben onları biraraya birleştirmek gerekir. 412 00:18:24,080 --> 00:18:26,040 Ben geçmesi gerekir Bu dört Bu dört, 413 00:18:26,040 --> 00:18:28,123 sonuçta onları birleştirmek için Geri sekiz unsurları içine. 414 00:18:28,123 --> 00:18:32,182 Tersine ben sekiz parmakları var I do not olan, buraya ve sekiz 415 00:18:32,182 --> 00:18:34,390 fingers-- sorry-- Ben ettik Eğer Buraya dört parmak var 416 00:18:34,390 --> 00:18:37,380 Ben, dört parmak yaptığımız Buraya, yapmam, hangi 417 00:18:37,380 --> 00:18:40,590 Daha sonra, aynı var: örnek olarak önce ben yaparsam 418 00:18:40,590 --> 00:18:44,010 olsa sekiz parmak var Ben, biraz, yapabileceğiniz toplam. 419 00:18:44,010 --> 00:18:47,950 Tam burada yapabilirsiniz sonra ben kesinlikle can 420 00:18:47,950 --> 00:18:50,370 Bu listelerin her birleştirme Birlikte boyutu 1. 421 00:18:50,370 --> 00:18:54,050 Ama ben kesinlikle bakmak zorunda her elemanın tam olarak bir kez. 422 00:18:54,050 --> 00:18:59,640 Yani bu işlemin yüksekliği, günlük n, Bu işlem genişliği, yani, konuşma 423 00:18:59,640 --> 00:19:02,490 bu yüzden görünüyor, ne n nihayetinde olduğunu olması 424 00:19:02,490 --> 00:19:06,470 büyüklük n kez çalışma süresi n oturum açın. 425 00:19:06,470 --> 00:19:08,977 >> Diğer bir deyişle, bölünmüş Liste, günlük n kere, 426 00:19:08,977 --> 00:19:11,810 ama biz yaptığımız her seferinde, biz elemanların her biri dokunmak 427 00:19:11,810 --> 00:19:13,560 Onları birleştirmek için Hep birlikte, hangi 428 00:19:13,560 --> 00:19:18,120 adımı n adet, bu yüzden var n kat n log edildi veya bir bilgisayar bilimcisi söyleyebilirim, 429 00:19:18,120 --> 00:19:20,380 asimptotik, hangi büyük kelime olurdu 430 00:19:20,380 --> 00:19:22,810 Üst açıklamak için Çalışan bir zaman bağlı, 431 00:19:22,810 --> 00:19:28,010 biz büyük bir o çalışan log n zaman, tabiri caizse. 432 00:19:28,010 --> 00:19:31,510 >> Şimdi, bu, çünkü önemli çalışan süreleri ne olduğunu hatırlamak 433 00:19:31,510 --> 00:19:34,120 kabarcık sıralama ve seçim ile sıralama ve yerleştirme sıralama, 434 00:19:34,120 --> 00:19:38,200 ve mevcut hatta birkaç diğerleri n biz nerede kalmıştık oldu karesi. 435 00:19:38,200 --> 00:19:39,990 Ve sen, biraz burada görebilirsiniz. 436 00:19:39,990 --> 00:19:45,720 N karesi ise besbelli n kat n, ama burada biz n defa n log, 437 00:19:45,720 --> 00:19:48,770 ve biz zaten biliyoruz hafta sıfır, bu günlük n, logaritmik, 438 00:19:48,770 --> 00:19:50,550 bir şey lineer daha iyidir. 439 00:19:50,550 --> 00:19:52,930 Sonuçta, resim hatırlama Kırmızı ve sarı ile 440 00:19:52,930 --> 00:19:56,500 Biz çekti ve yeşil çizgiler, Yeşil logaritmik hat çok daha düşük oldu. 441 00:19:56,500 --> 00:20:00,920 Ve bu nedenle, çok daha iyi ve daha hızlı Düz sarı ve kırmızı çizgiler yerine, 442 00:20:00,920 --> 00:20:05,900 n defa gerçekten isimli log n, daha iyi n kat daha n veya n karesi. 443 00:20:05,900 --> 00:20:09,110 >> Yani biz var gibi görünüyor Bir algoritma birleştirme tespit 444 00:20:09,110 --> 00:20:11,870 sıralama çok çalışan olduğunu Daha hızlı zamanı ve aslında, 445 00:20:11,870 --> 00:20:16,560 bu yüzden, bu hafta başlarında, zaman var Biz kabarcık arasındaki yarışma gördüm 446 00:20:16,560 --> 00:20:20,750 sıralama, seçme sıralama, birleştirme ve sıralama, sıralama gerçekten kazandı birleştirme. 447 00:20:20,750 --> 00:20:23,660 Ve gerçekten de, biz bile beklemedi kabarcık sıralama ve seçme sıralama için 448 00:20:23,660 --> 00:20:24,790 bitirmek için. 449 00:20:24,790 --> 00:20:27,410 >> Şimdi bir başka geçmek atalım Bu da, biraz daha fazla 450 00:20:27,410 --> 00:20:31,030 resmi perspektif, sadece durum, bu daha iyi rezonansa 451 00:20:31,030 --> 00:20:33,380 Bu üst düzey tartışma daha. 452 00:20:33,380 --> 00:20:34,880 Yani burada algoritma tekrar var. 453 00:20:34,880 --> 00:20:36,770 Kendimize soralım, Ne çalışma süresi 454 00:20:36,770 --> 00:20:39,287 Bu çeşitli adımlar algoritmaları biridir? 455 00:20:39,287 --> 00:20:41,620 İlk bölün edelim Olgu ve ikinci vaka. 456 00:20:41,620 --> 00:20:46,280 IF durumunda IF ve ELSE, Burada n, 2 den daha az ise, sadece geri döner. 457 00:20:46,280 --> 00:20:47,580 Zaman sabiti gibi hissediyor. 458 00:20:47,580 --> 00:20:50,970 Bu iki adımda gibi, tür, var, Burada n, 2 den daha az ise, o zaman geri döner. 459 00:20:50,970 --> 00:20:54,580 Ama biz Pazartesi günü yaptığı açıklamada olduğu gibi, sabit zaman, ya da 1 o büyük, 460 00:20:54,580 --> 00:20:57,130 iki adım, üç olabilir, adım da 1000 adım. 461 00:20:57,130 --> 00:20:59,870 Önemli olan olmasıdır adımda sabit bir sayı. 462 00:20:59,870 --> 00:21:03,240 Yani sarı pseudocode vurgulanan Burada, biz onu arayacağım, çalışır 463 00:21:03,240 --> 00:21:04,490 zaman sabiti. 464 00:21:04,490 --> 00:21:06,780 Yani daha resmi ve Bu ki-- gidiyoruz 465 00:21:06,780 --> 00:21:09,910 ölçüde olacak hangi biz n T şimdi-- bu hakkı resmileştirmek, 466 00:21:09,910 --> 00:21:15,030 Bir sorun çalışma süresi bu, girdi olarak alır n birşeyler 467 00:21:15,030 --> 00:21:19,150 , biri o büyük eşittir Burada n, 2 den az ise. 468 00:21:19,150 --> 00:21:20,640 Yani o şartına var. 469 00:21:20,640 --> 00:21:24,150 N daha az EĞER Yani, açık olmak 2, biz o zaman, çok kısa bir listesi var 470 00:21:24,150 --> 00:21:29,151 n çalışma süresi n, T, 1 ya da 0, bu çok özel durumda, 471 00:21:29,151 --> 00:21:30,650 Sadece sabit zaman olacak. 472 00:21:30,650 --> 00:21:32,691 O birini almaya gidiyor ne olursa olsun, iki adım adım. 473 00:21:32,691 --> 00:21:33,950 Bu adımlar sabit numara. 474 00:21:33,950 --> 00:21:38,840 >> Yani sulu kısım mutlaka olmalı pseudocode diğer olgu. 475 00:21:38,840 --> 00:21:40,220 ELSE durumda. 476 00:21:40,220 --> 00:21:44,870 Elementlerin sırala sol yarısı, sıralama doğru elemanların yarısı, sıralı yarısını birleştirmek. 477 00:21:44,870 --> 00:21:46,800 Bu adımların her ne kadar sürer? 478 00:21:46,800 --> 00:21:49,780 Peki, eğer çalışan n elemanlarını sıralamak için zaman 479 00:21:49,780 --> 00:21:53,010 , o da çok diyelim genel olarak, T, n, 480 00:21:53,010 --> 00:21:55,500 Daha sonra sol sıralama elemanların yarı 481 00:21:55,500 --> 00:21:59,720 ise, bir tür, demek gibi, 2 ile bölündüğünde, n T, 482 00:21:59,720 --> 00:22:03,000 ve benzer sağ yarısını sıralama unsurlardan olduğunu tür, demek gibi, 483 00:22:03,000 --> 00:22:06,974 N T 2 ayrılır ve daha sonra sıralanmış yarılarını birleştirme. 484 00:22:06,974 --> 00:22:08,890 Eh bende eğer bazı Burada elemanların sayısı, 485 00:22:08,890 --> 00:22:11,230 dört ve bazı numarayı gibi Burada elemanların, dört gibi, 486 00:22:11,230 --> 00:22:14,650 ve ben bu dört her birleştirmek zorunda içinde ve bu dört her biri bir arada 487 00:22:14,650 --> 00:22:17,160 arka arkaya, böylece sonuçta ben sekiz elemanları var. 488 00:22:17,160 --> 00:22:20,230 O n adımlarının o büyük olduğunu hissediyor? 489 00:22:20,230 --> 00:22:23,500 Ben parmaklarını ve her n var ise Onları yerine birleştirilecek vardır, 490 00:22:23,500 --> 00:22:25,270 başka n adımlar gibi. 491 00:22:25,270 --> 00:22:27,360 >> Yani aslında formulaically, Biz bu ifade edebiliriz 492 00:22:27,360 --> 00:22:29,960 ilk başta biraz scarily olsa bakışta, ama bir şey 493 00:22:29,960 --> 00:22:31,600 Bu tam olarak bu mantığı yakalar. 494 00:22:31,600 --> 00:22:35,710 Çalışma süresi, T n, IF n daha büyük ya da 2'ye eşittir. 495 00:22:35,710 --> 00:22:42,500 Bu durumda, ELSE durumda, n, T 2 ile bölündüğünde, n artı T 2'ye bölünür, 496 00:22:42,500 --> 00:22:45,320 artı n o büyük, bazı adım doğrusal sayısı 497 00:22:45,320 --> 00:22:51,630 belki tam olarak n, belki 2 kere n, ancak kabaca n emir. 498 00:22:51,630 --> 00:22:54,060 Böylece de nasıl biz ise formulaically bu ifade. 499 00:22:54,060 --> 00:22:56,809 Şimdi sürece bu bilemeyiz Eğer kafanızda o kaydettik 500 00:22:56,809 --> 00:22:58,710 ya o kadar bakmak geri kitabının, o 501 00:22:58,710 --> 00:23:00,501 Biraz olabilir sonunda sayfasını hile, 502 00:23:00,501 --> 00:23:03,940 ama bu, gerçekten, gidiyor n günlük n o büyük bize ver, 503 00:23:03,940 --> 00:23:06,620 nüks çünkü Eğer ekranda burada görüyoruz 504 00:23:06,620 --> 00:23:09,550 Aslında birlikte, dışarı yapsam örneklerin sonsuz sayıda, 505 00:23:09,550 --> 00:23:13,000 ya formulaically yaptım, sen-cekti Bu görüyoruz bu formüle çünkü 506 00:23:13,000 --> 00:23:17,100 kendisi t, özyinelemelidir n sağda bir şey yüzünden, 507 00:23:17,100 --> 00:23:21,680 soldan n adet t ve bu can Aslında ifade, sonuçta, 508 00:23:21,680 --> 00:23:24,339 n log n gibi büyük gitmek. 509 00:23:24,339 --> 00:23:26,130 Ikna değilse, işte Şimdilik sadece para cezası 510 00:23:26,130 --> 00:23:28,960 Gerçekten, işte o, iman almak, Bu nüks neden, ne 511 00:23:28,960 --> 00:23:31,780 ama bu sadece biraz daha seyir matematiksel yaklaşım 512 00:23:31,780 --> 00:23:36,520 Birleştirme tür çalışan anda tek başına pseudocode dayalı. 513 00:23:36,520 --> 00:23:39,030 >> Şimdi bir biraz atalım Bunun tüm havalandırma, 514 00:23:39,030 --> 00:23:41,710 ve bir göz atın Bazı eski senatör, kim 515 00:23:41,710 --> 00:23:44,260 Biraz tanıdık görünebilir, kim Google'ın Eric ile oturdu 516 00:23:44,260 --> 00:23:48,410 Bir röportaj için bir süre önce Schmidt, Sahnede, bütün bir demet önünde 517 00:23:48,410 --> 00:23:53,710 insanların, sonuçta bahsediyoruz Bir konu, bu oldukça geç tanıdık. 518 00:23:53,710 --> 00:23:54,575 Hadi bir bakalım. 519 00:23:54,575 --> 00:24:01,020 520 00:24:01,020 --> 00:24:03,890 >> Eric Schmidt,: Şimdi Senatör, Eğer Google'da buradayız 521 00:24:03,890 --> 00:24:09,490 ve ben düşünmek istiyorum Bir iş görüşmesi olarak başkanlığı. 522 00:24:09,490 --> 00:24:11,712 Şimdi başkan olarak bir iş bulmak zor. 523 00:24:11,712 --> 00:24:12,670 BAŞKAN OBAMA: Doğru. 524 00:24:12,670 --> 00:24:13,940 Eric Schmidt,: Ve sen Şimdi [duyulamaz] yapacaksın. 525 00:24:13,940 --> 00:24:15,523 O Google'da bir iş bulmak da zor. 526 00:24:15,523 --> 00:24:17,700 BAŞKAN OBAMA: Doğru. 527 00:24:17,700 --> 00:24:21,330 >> Eric Schmidt,: Biz sorularım var, ve bizim adayların soru sormak, 528 00:24:21,330 --> 00:24:24,310 ve bu bir Larry Schwimmer değil. 529 00:24:24,310 --> 00:24:25,890 >> BAŞKAN OBAMA: Tamam. 530 00:24:25,890 --> 00:24:27,005 >> Eric Schmidt,: ne olacak? 531 00:24:27,005 --> 00:24:28,130 Siz Şaka mı sanıyorsun? 532 00:24:28,130 --> 00:24:30,590 Tam burada. 533 00:24:30,590 --> 00:24:33,490 En etkili yolu Nedir Bir milyon 32 bit tamsayı sıralamak? 534 00:24:33,490 --> 00:24:37,560 535 00:24:37,560 --> 00:24:38,979 >> BAŞKAN OBAMA: Şey-- 536 00:24:38,979 --> 00:24:41,020 Eric Schmidt, Bazen, Belki üzgünüm, belki-- 537 00:24:41,020 --> 00:24:42,750 BAŞKAN OBAMA: Hayır, hayır, Hayır, hayır, hayır, bence-- 538 00:24:42,750 --> 00:24:43,240 Eric Schmidt,: Bu bu-- değil 539 00:24:43,240 --> 00:24:45,430 BAŞKAN OBAMA: Ben düşünüyorum, ben kabarcık düşünüyorum 540 00:24:45,430 --> 00:24:46,875 Sıralama gitmek yanlış bir yol olacaktır. 541 00:24:46,875 --> 00:24:49,619 542 00:24:49,619 --> 00:24:50,535 Eric Schmidt,: Hadi. 543 00:24:50,535 --> 00:24:52,200 Onu kim söyledi? 544 00:24:52,200 --> 00:24:54,020 TAMAM. 545 00:24:54,020 --> 00:24:55,590 Ben bilgisayar bilimi vermedi on-- 546 00:24:55,590 --> 00:24:58,986 >> BAŞKAN OBAMA: Biz ettik Orada bizim casusları var. 547 00:24:58,986 --> 00:24:59,860 PROFESÖR: Pekala. 548 00:24:59,860 --> 00:25:03,370 Şimdi arkamızda bırakalım algoritmaların teorik Dünyanın 549 00:25:03,370 --> 00:25:06,520 asimptotik analizinde bunların ve bazı konularda geri dönmek 550 00:25:06,520 --> 00:25:09,940 Haftanın sıfır ve bir, ve baştan bazı eğitim tekerlekleri kaldırmak için, 551 00:25:09,940 --> 00:25:10,450 eğer sen. 552 00:25:10,450 --> 00:25:13,241 Eğer gerçekten anlamak Böylece sonuçta yere kadar, ne 553 00:25:13,241 --> 00:25:16,805 , sizi başlık altında oluyor Yazmak derlemek ve programları çalıştırmak. 554 00:25:16,805 --> 00:25:19,680 Bu oldu, özellikle hatırlayın Biz baktı ilk C programı, 555 00:25:19,680 --> 00:25:22,840 Bir kanonik, basit bir program türlü, göreceli olarak, 556 00:25:22,840 --> 00:25:24,620 burada, bu Merhaba Dünya yazdırır. 557 00:25:24,620 --> 00:25:27,610 Ve ben süreç, dedi çağırmak olduğunu Bu kaynak kodu geçer 558 00:25:27,610 --> 00:25:28,430 tam olarak bu olduğunu. 559 00:25:28,430 --> 00:25:31,180 Sen kaynak kodu almak, pas bir derleyici ile, Clang gibi 560 00:25:31,180 --> 00:25:34,650 ve dışarı o nesne kodunu geliyor Bu, sıfır ve olanlar gibi görünebilir 561 00:25:34,650 --> 00:25:37,880 bilgisayarınızın CPU, merkezi o işlem ünitesi veya beyin, 562 00:25:37,880 --> 00:25:39,760 sonuçta anlar. 563 00:25:39,760 --> 00:25:42,460 >> O bir olduğunu çıkıyor Bir basitleştirme bit, 564 00:25:42,460 --> 00:25:44,480 Biz şimdi olduğunuzu pozisyon dışında kızdırmak için 565 00:25:44,480 --> 00:25:46,720 Gerçekten oldu ne olduğunu anlamak için başlık altında oluyor 566 00:25:46,720 --> 00:25:48,600 Çalıştırdığınız her zaman Clang, veya daha genel olarak, 567 00:25:48,600 --> 00:25:53,040 Her zaman, bir program yapmak Marka ve CF 50 IDE kullanarak. 568 00:25:53,040 --> 00:25:56,760 Özellikle, malzeme gibi Bu ilk olarak oluşturulur 569 00:25:56,760 --> 00:25:58,684 ne zaman ilk programı derlemek. 570 00:25:58,684 --> 00:26:00,600 Diğer bir deyişle, sizi Kaynak kodunuzu almak 571 00:26:00,600 --> 00:26:04,390 ve ilk ne var, derlemek Clang tarafından çıkarılan varlık 572 00:26:04,390 --> 00:26:06,370 montaj kodu olarak da bilinir bir şeydir. 573 00:26:06,370 --> 00:26:08,990 Ve aslında, tam olarak bu gibi görünüyor. 574 00:26:08,990 --> 00:26:11,170 >> Ben bir komut koştu Daha önce komut satırı. 575 00:26:11,170 --> 00:26:16,260 Clang çizgi başkentin s merhaba.c, ve bu dosyayı oluşturan 576 00:26:16,260 --> 00:26:19,490 Beni çağırdı hello.S için, bunların içinde tam olarak edildi 577 00:26:19,490 --> 00:26:22,290 Bu içeriği ve biraz daha Yukarıda ve daha aşağıda biraz 578 00:26:22,290 --> 00:26:25,080 ama juiciest koyduk Burada ekranda bilgiler. 579 00:26:25,080 --> 00:26:29,190 Eğer yakından bakarsanız, görürsünüz en az birkaç tanıdık anahtar kelimeler. 580 00:26:29,190 --> 00:26:31,330 Biz üstünde ana var. 581 00:26:31,330 --> 00:26:35,140 Biz ortada aşağı printf var. 582 00:26:35,140 --> 00:26:38,670 Ve biz de dünyanın merhaba var aşağı aşağıda tırnak içinde ters eğik çizgi n. 583 00:26:38,670 --> 00:26:42,450 >> Burada başka ve her şey çok düşük seviyede olduğu talimatları 584 00:26:42,450 --> 00:26:45,500 bilgisayarınızın CPU anladığı. 585 00:26:45,500 --> 00:26:50,090 Bellek taşımak CPU talimatları etrafında, bellekten bu yük dizeleri, 586 00:26:50,090 --> 00:26:52,750 ve sonuçta, baskı Ekranda şeyler. 587 00:26:52,750 --> 00:26:56,780 Şimdi ne olacak sonra bile olur Bu derleme kodu üretilir? 588 00:26:56,780 --> 00:26:59,964 Sonuçta, gerçekten yapmak, Hala nesne kodu oluşturmak. 589 00:26:59,964 --> 00:27:02,630 Ama adımlar gerçekten var başlık altında devam 590 00:27:02,630 --> 00:27:04,180 Böyle biraz daha bak. 591 00:27:04,180 --> 00:27:08,390 Kaynak kodu, montaj kodu olur bu daha sonra nesne kodu olur 592 00:27:08,390 --> 00:27:11,930 ve burada ameliyat sözler, o Eğer kaynak kodu derleme yaparken, 593 00:27:11,930 --> 00:27:16,300 sonra dışarı montaj kodu ve gelir Eğer derleme kod birleştirmek zaman, 594 00:27:16,300 --> 00:27:17,800 dışarı nesne kodunu geliyor. 595 00:27:17,800 --> 00:27:20,360 >> Şimdi Clang, süper sofistike derleyiciler bir sürü gibi, 596 00:27:20,360 --> 00:27:23,151 ve bu adımların hepsini yapıyor Birlikte ve mutlaka yok 597 00:27:23,151 --> 00:27:25,360 çıkış herhangi bir ara Hatta görebilirsiniz dosyaları. 598 00:27:25,360 --> 00:27:28,400 Bu sadece şeyler derler, Hangi genel bir terimdir olduğunu 599 00:27:28,400 --> 00:27:30,000 Tüm bu yöntem tarif edilmiştir. 600 00:27:30,000 --> 00:27:32,000 Ama eğer gerçekten istiyorsanız Özellikle olmak, var 601 00:27:32,000 --> 00:27:34,330 çok daha fazla hem de oraya gidiyor. 602 00:27:34,330 --> 00:27:38,860 >> Ama aynı zamanda o şimdi bile düşünelim süper basit bir program, merhaba.c, 603 00:27:38,860 --> 00:27:40,540 Bir işlevi çağrılır. 604 00:27:40,540 --> 00:27:41,870 Bu printf denir. 605 00:27:41,870 --> 00:27:46,900 Ama ben, gerçekten, printf yazmadım Bu tabiri caizse, c ile birlikte geliyor. 606 00:27:46,900 --> 00:27:51,139 Bu bir işlev hatırlama var Standart io.h, beyan hangi 607 00:27:51,139 --> 00:27:53,180 Bir başlık dosyası, hangi Bir konu aslında edeceğiz olduğunu 608 00:27:53,180 --> 00:27:55,780 uzun zaman önce daha derinlemesine dalmak. 609 00:27:55,780 --> 00:27:58,000 Ama bir başlık dosyasıdır tipik eşlik 610 00:27:58,000 --> 00:28:02,920 Bir kod dosyasında, kaynak kodu dosyası, bu yüzden tarafından Standart io.h bulunduğunu gibi çok 611 00:28:02,920 --> 00:28:05,930 >> Bazen önce, birisi, ya da birileri de yazdı 612 00:28:05,930 --> 00:28:11,040 in standart io.c adlı bir dosya ki bu gerçek tanımlar, 613 00:28:11,040 --> 00:28:15,220 veya printf uygulamaları, ve diğer fonksiyonların salkımları 614 00:28:15,220 --> 00:28:16,870 Aslında yazılır. 615 00:28:16,870 --> 00:28:22,140 Biz sahip düşünün Yani, verilen Buradan sola, hello.c üzerine, o zaman 616 00:28:22,140 --> 00:28:26,250 derlenmiş, bile, hello.S bize verir Clang bir yerde tasarruf rahatsız etmiyor 617 00:28:26,250 --> 00:28:31,360 biz onu görmek ve bu montaj kodu olabilir hello.o, içine monte olur ki 618 00:28:31,360 --> 00:28:34,630 Nitekim, varsayılan adıdır Eğer kaynak derleme zaman verilen 619 00:28:34,630 --> 00:28:39,350 nesne koduna kod ama değil Henüz çalıştırmak için oldukça hazır, 620 00:28:39,350 --> 00:28:41,460 Başka bir adım için ne var ve var 621 00:28:41,460 --> 00:28:44,440 Geçtiğimiz birkaç için oluyor hafta, size belki topraklarındaki. 622 00:28:44,440 --> 00:28:47,290 >> Özellikle bir yerde CS50 IDE ve bu, 623 00:28:47,290 --> 00:28:49,870 çok bir biraz olacak Bir an için oversimplification, 624 00:28:49,870 --> 00:28:54,670 orada, ya bir zamanlar oldu, Standart io.c adlı bir dosya, 625 00:28:54,670 --> 00:28:58,440 Birisi derlenmiş olduğu Standart io.s veya eşdeğeri, 626 00:28:58,440 --> 00:29:02,010 Birisi daha sonra monte olduğunu Standart io.o içine 627 00:29:02,010 --> 00:29:04,600 ya da bir içine çıkıyor biraz daha farklı bir dosya 628 00:29:04,600 --> 00:29:07,220 Farklı bir olabilir biçimi tamamen uzantıyı dosya, 629 00:29:07,220 --> 00:29:11,720 teoride ve kavramsal, tam ama Bu adımlar çeşit gerçekleşmesi gerekiyordu. 630 00:29:11,720 --> 00:29:14,060 Demek şimdi bu kadar Hangi Ben bir program yazıyorum zaman, 631 00:29:14,060 --> 00:29:17,870 merhaba.c, sadece diyor, merhaba dünya, ve başkasının kodu kullanıyorum 632 00:29:17,870 --> 00:29:22,480 Bir zamanlar üzerine printf gibi Zaman, standart io.c adlı bir dosyaya, 633 00:29:22,480 --> 00:29:26,390 Daha sonra her nasılsa gözlerimi almak zorunda Nesne kodu, benim sıfırlar ve olanları, 634 00:29:26,390 --> 00:29:29,260 ve bu kişinin nesne kodu veya sıfırlar ve olanları, 635 00:29:29,260 --> 00:29:34,970 ve her nasılsa içine bunları birbirine bağlamak Bu, merhaba denilen son bir dosya, 636 00:29:34,970 --> 00:29:38,070 yer alır sıfır tüm ve benim ana fonksiyonundan olanlar 637 00:29:38,070 --> 00:29:40,830 ve sıfırlar tüm ve printf için olanlar. 638 00:29:40,830 --> 00:29:44,900 >> Ve gerçekten de, son bir süreçtir denilen nesne kodunu bağlama. 639 00:29:44,900 --> 00:29:47,490 Bunu çıktısı ise bir yürütülebilir dosyadır. 640 00:29:47,490 --> 00:29:49,780 Yani adalet, en gün, hiçbir şey sonuna 641 00:29:49,780 --> 00:29:52,660 Haftanın tek beri değişti, ne zaman İlk program derleme başladı. 642 00:29:52,660 --> 00:29:55,200 Gerçekten de, tüm bu olmuştur Kaputun altında oluyor, 643 00:29:55,200 --> 00:29:57,241 ama şimdi biz bir konumda konum Nerede biz aslında can 644 00:29:57,241 --> 00:29:58,794 Bu çeşitli adımlar ayrı kızdırmak. 645 00:29:58,794 --> 00:30:00,710 Ve gerçekten de, sonunda Günün biz hala 646 00:30:00,710 --> 00:30:04,480 birler ve sıfırlar, sol hangi büyük segue şimdi aslında 647 00:30:04,480 --> 00:30:08,620 C bir özelliği, yani biz büyük olasılıkla kaldıraç yaşadım değil 648 00:30:08,620 --> 00:30:11,250 Bugüne kadar, bit operatörleri olarak da bilinir. 649 00:30:11,250 --> 00:30:15,220 Diğer bir deyişle, bu noktaya kadar, her biz ettik C C veya değişkenler verilerle ele, 650 00:30:15,220 --> 00:30:17,660 Biz gibi şeyler yaşadım karakter ve mantarlar ve ins 651 00:30:17,660 --> 00:30:21,990 ve uzun ve çiftler ve benzeri ama bunların hepsi en az sekiz bit. 652 00:30:21,990 --> 00:30:25,550 Henüz mümkün olmamıştım bireysel bitlerin işlemek, 653 00:30:25,550 --> 00:30:28,970 Hatta tek bir bit olsa da, biz Bir 0 ve 1 temsil edebilir biliyorum. 654 00:30:28,970 --> 00:30:32,640 Şimdi C çıkıyor, sen Bireysel bit erişebilirsiniz, 655 00:30:32,640 --> 00:30:35,530 Eğer sözdizimi biliyorsanız, hangi ile onlara ulaşmak için. 656 00:30:35,530 --> 00:30:38,010 >> Yani bir göz atalım Bitsel operatörleri. 657 00:30:38,010 --> 00:30:41,700 Yani resimdeki birkaç sembolleri olduğunu biz tür, çeşit, daha önce görmüştüm. 658 00:30:41,700 --> 00:30:45,580 Ben, dikey bir ve işareti bkz bar ve yanı sıra bazıları, 659 00:30:45,580 --> 00:30:49,430 ve bu işareti işareti hatırlamak Daha önce gördüğümüz bir şeydir. 660 00:30:49,430 --> 00:30:54,060 Eğer varsa mantıksal AND operatörü, İkisi birlikte, ya da mantıksal OR 661 00:30:54,060 --> 00:30:56,300 Operatör, nerede iki dikey çubuk var. 662 00:30:56,300 --> 00:31:00,550 Bit operatörleri, yaparız tek tek bit üzerinde işlem bkz 663 00:31:00,550 --> 00:31:03,810 sadece tek bir işareti kullanın Tek dikey çubuk, şapka simgesi 664 00:31:03,810 --> 00:31:06,620 Bir sonraki küçük geliyor tilde ve sonra sol 665 00:31:06,620 --> 00:31:08,990 braket dirseğini sola veya Sağ dirsek sağ ayraç. 666 00:31:08,990 --> 00:31:10,770 Bunların her biri farklı anlamları vardır. 667 00:31:10,770 --> 00:31:11,950 >> Aslında, en bir göz atalım. 668 00:31:11,950 --> 00:31:16,560 Eski okul bugün ve kullanım gidelim geçmişin bir dokunmatik ekran, 669 00:31:16,560 --> 00:31:18,002 bir beyaz tahta olarak da bilinir. 670 00:31:18,002 --> 00:31:19,710 Ve bu beyaz tahta bize izin gidiyor 671 00:31:19,710 --> 00:31:27,360 Bazı oldukça basit semboller ifade etmek, ya da daha doğrusu bazı oldukça basit formüller, 672 00:31:27,360 --> 00:31:29,560 biz sonuçta o can Kaldıraç, sipariş 673 00:31:29,560 --> 00:31:33,230 Bireysel erişmek için C program dahilinde bit. 674 00:31:33,230 --> 00:31:34,480 Diğer bir deyişle, hadi yapalım. 675 00:31:34,480 --> 00:31:37,080 Bir için diyelim ilk tartışma işareti ile ilgili anı, 676 00:31:37,080 --> 00:31:39,560 Hangi lojik AND operatörüdür. 677 00:31:39,560 --> 00:31:42,130 Diğer bir deyişle, bu sağlayan bir operatör 678 00:31:42,130 --> 00:31:45,930 Bana bir sol değişken olması tipik olarak, ve bir sağ-taraf değişkeni 679 00:31:45,930 --> 00:31:50,640 ya da ayrı ayrı bir değer, bu eğer ve Birlikte onları bana son bir sonuç verir. 680 00:31:50,640 --> 00:31:51,560 Yani ne demek istiyorsun? 681 00:31:51,560 --> 00:31:54,840 Bir programda, bir değişken varsa Bu değerlerin mağaza biri olduğunu, 682 00:31:54,840 --> 00:31:58,000 ya en basit tutmak ve sadece izin bireysel sıfırları ve olanları yazmak, 683 00:31:58,000 --> 00:32:00,940 işareti operatörü nasıl çalıştığını burada. 684 00:32:00,940 --> 00:32:06,400 0 işareti 0 0 eşit olacak. 685 00:32:06,400 --> 00:32:07,210 Şimdi neden? 686 00:32:07,210 --> 00:32:09,291 >> Bu çok benzer Boole ifadeleri, 687 00:32:09,291 --> 00:32:10,540 biz bugüne kadar ele aldık. 688 00:32:10,540 --> 00:32:15,800 Tüm sonra düşünüyorsanız, 0 Yanlış, 0, false false ve yanlış 689 00:32:15,800 --> 00:32:18,720 Konuştuğumuz gibi olduğunu mantıksal, ayrıca yanlış. 690 00:32:18,720 --> 00:32:20,270 Yani biz de burada 0 olsun. 691 00:32:20,270 --> 00:32:24,390 Eğer 0 işareti alırsak 1, iyi ki de 692 00:32:24,390 --> 00:32:29,890 çünkü bunun için, 0 olacak Sol taraftaki sentezleme, doğru ya da 1 olduğu 693 00:32:29,890 --> 00:32:32,360 gerçek ve doğru olması gerekir. 694 00:32:32,360 --> 00:32:36,320 Ama burada biz yanlış var ve gerçek ya da 0 ve 1. 695 00:32:36,320 --> 00:32:42,000 Şimdi yine, biz 1 işareti varsa 0, de, 0 olacak ki, 696 00:32:42,000 --> 00:32:47,240 ve biz 1 işareti 1 varsa, Sonunda biz 1 bit var. 697 00:32:47,240 --> 00:32:50,340 Başka bir deyişle Yani, biz yapmıyoruz Bu operatör ile ilginç şey 698 00:32:50,340 --> 00:32:51,850 Henüz, bu işareti operatörü. 699 00:32:51,850 --> 00:32:53,780 Bu lojik AND operatörü var. 700 00:32:53,780 --> 00:32:57,290 Fakat bu katkı maddeleri şunlardır hangi aracılığıyla yapabileceğimiz 701 00:32:57,290 --> 00:32:59,240 yakında göreceğimiz gibi ilginç şeyler. 702 00:32:59,240 --> 00:33:02,790 >> Şimdi sadece tek bakalım Burada sağ tarafta üzerinde dikey çubuk. 703 00:33:02,790 --> 00:33:06,710 Ben 0 bit ve I varsa VEYA onunla, bit 704 00:33:06,710 --> 00:33:11,030 VEYA operatörü başka 0 bit, bu beni 0 vermek için gidiyor. 705 00:33:11,030 --> 00:33:17,540 Ben 0 bit ve OR onu birlikte alırsak 1 bit, sonra 1 alacağım. 706 00:33:17,540 --> 00:33:19,830 Ve aslında, sadece için netlik, beni geri dönelim 707 00:33:19,830 --> 00:33:23,380 O yüzden benim dikey çubuklar 1'ler için yanlış değildir. 708 00:33:23,380 --> 00:33:26,560 Bana bütün yeniden edelim zaman 1 biraz daha var 709 00:33:26,560 --> 00:33:32,700 Ben eğer açıkça, böylece bir sonraki bakın 1 OR 0, bu 1 olacak olan, 710 00:33:32,700 --> 00:33:39,060 ve ben 1 VEYA 1 a varsa, de bir 1 olacak. 711 00:33:39,060 --> 00:33:42,900 Yani mantıklı bakın VEYA o olabilir Operatör çok farklı davranır. 712 00:33:42,900 --> 00:33:48,070 Bu 0 bana veriyor Veya 0 0 verir ama bana her kombinasyon bana 1 verir. 713 00:33:48,070 --> 00:33:52,480 Çok uzun bir tane 1 si Formül, sonuç 1 olacak. 714 00:33:52,480 --> 00:33:55,580 >> AND tersine, Operatör, işareti, 715 00:33:55,580 --> 00:34:00,940 Ben iki 1'lerinizi varsa denklemi, ben aslında 1 out alırım. 716 00:34:00,940 --> 00:34:02,850 Şimdi birkaç diğer var Operatörler de. 717 00:34:02,850 --> 00:34:04,810 Bunlardan biri biraz daha karmaşıktır. 718 00:34:04,810 --> 00:34:07,980 Bu yüzden bana go ahead ve silelim Bu biraz alan boşaltmak için. 719 00:34:07,980 --> 00:34:13,020 720 00:34:13,020 --> 00:34:16,460 Ve en az bir göz atalım Sadece bir an için şapka sembolü. 721 00:34:16,460 --> 00:34:18,210 Bu genellikle bir olan karakter yazabilirsiniz 722 00:34:18,210 --> 00:34:21,420 Klavyeniz tutma Shift ve senin ABD'nin üstüne numaraları sonra bir 723 00:34:21,420 --> 00:34:22,250 Klavye. 724 00:34:22,250 --> 00:34:26,190 >> Yani bu özel olduğunu YA operatör özel VEYA. 725 00:34:26,190 --> 00:34:27,790 Yani biz sadece VEYA operatörü gördüm. 726 00:34:27,790 --> 00:34:29,348 Bu özel VEYA operatörüdür. 727 00:34:29,348 --> 00:34:30,639 Aslında fark nedir? 728 00:34:30,639 --> 00:34:34,570 Peki Sadece formülüne bakalım, ve sonuçta madde olarak kullanmak. 729 00:34:34,570 --> 00:34:37,690 0 XOR 0. 730 00:34:37,690 --> 00:34:39,650 Ben söylemek için gidiyorum her zaman 0'dır. 731 00:34:39,650 --> 00:34:41,400 Bu XOR tanımı var. 732 00:34:41,400 --> 00:34:47,104 0 XOR 1 1 olacak. 733 00:34:47,104 --> 00:34:58,810 1 XOR 0, 1 olacak ve 1 XOR 1 olacak? 734 00:34:58,810 --> 00:34:59,890 Yanlış? 735 00:34:59,890 --> 00:35:00,520 Veya doğru? 736 00:35:00,520 --> 00:35:01,860 Bilmiyorum. 737 00:35:01,860 --> 00:35:02,810 0. 738 00:35:02,810 --> 00:35:04,700 Şimdi ne olacak oluyor burada? 739 00:35:04,700 --> 00:35:06,630 Peki düşünmek Bu operatörün adı. 740 00:35:06,630 --> 00:35:09,980 YA şekilde isim, tür, anlaşılacağı 741 00:35:09,980 --> 00:35:13,940 Cevap sadece olacak 1 giriş özel ise, 742 00:35:13,940 --> 00:35:15,560 münhasıran farklı. 743 00:35:15,560 --> 00:35:18,170 Yani burada girişler Aynı nedenle çıkış 0'dır. 744 00:35:18,170 --> 00:35:20,700 İşte girişler Aynı nedenle çıkış 0'dır. 745 00:35:20,700 --> 00:35:25,640 İşte çıkışlar bunlar farklı are özeldir ve bu nedenle çıkış 1'dir. 746 00:35:25,640 --> 00:35:28,190 Bu yüzden çok benzer VE, bu çok benzer 747 00:35:28,190 --> 00:35:32,760 ya da daha doğrusu o çok benzer YA, ancak özel bir şekilde. 748 00:35:32,760 --> 00:35:36,210 Bu on, artık 1 iki 1'lerinizi çünkü, 749 00:35:36,210 --> 00:35:38,621 ve özel olarak, bunlardan sadece biri. 750 00:35:38,621 --> 00:35:39,120 Pekala. 751 00:35:39,120 --> 00:35:40,080 Ne diğerleri? 752 00:35:40,080 --> 00:35:44,220 Peki tilde, bu arada, bir gerçekten güzel ve basit, minnetle. 753 00:35:44,220 --> 00:35:46,410 Ve bu bir tek terimli bir anlamına gelir operatörü 754 00:35:46,410 --> 00:35:50,400 Bu, sadece bir giriş olarak uygulanır tek işlenen, tabiri caizse. 755 00:35:50,400 --> 00:35:51,800 Değil sol ve sağ için. 756 00:35:51,800 --> 00:35:56,050 Başka bir deyişle, bir tilde alırsan 0 cevap karşısında olacak. 757 00:35:56,050 --> 00:35:59,710 Ve sen 1 tilde alırsak, Cevap karşısında olacak. 758 00:35:59,710 --> 00:36:02,570 Yani tilde operatörüdür biraz inkâr etmenin bir yoludur, 759 00:36:02,570 --> 00:36:06,000 veya bir biraz saygısız 0-1 ya da 0 1. 760 00:36:06,000 --> 00:36:09,820 >> Ve nihayet bizi bırakır Sadece son iki operatörlerle, 761 00:36:09,820 --> 00:36:13,840 Sol shift sözde ve sağ shift operatörü sözde. 762 00:36:13,840 --> 00:36:16,620 En nasıl bu işin bir göz atalım. 763 00:36:16,620 --> 00:36:20,780 Yazılı sola kaydırma operatörü, Böyle iki köşeli parantez içeren, 764 00:36:20,780 --> 00:36:22,110 aşağıdaki gibi çalışır. 765 00:36:22,110 --> 00:36:27,390 Eğer sola benim giriş, ya da benim işlenen, kaydırma operatörü oldukça basit bir 1'dir. 766 00:36:27,390 --> 00:36:33,750 Ve ben sonra bilgisayarı anlatmak 1, yedi yerde söylüyorlar vardiya sol 767 00:36:33,750 --> 00:36:37,150 Sonuç I sanki olduğunu Bu 1 almak ve taşımak 768 00:36:37,150 --> 00:36:40,160 üzerinde yedi yerde Sol ve varsayılan olarak, 769 00:36:40,160 --> 00:36:42,270 Biz varsaymak için gidiyoruz sağa alan 770 00:36:42,270 --> 00:36:44,080 sıfır ile doldurulur olacak. 771 00:36:44,080 --> 00:36:50,316 Bir başka deyişle, 1 vardiya 7 gidiyor sol ardından 1 bana vermek üzere 1, 2, 3, 772 00:36:50,316 --> 00:36:54,060 4, 5, 6, 7 sıfır. 773 00:36:54,060 --> 00:36:57,380 Bir bakıma Yani, yapmanız gereken 1 gibi küçük bir numara almak, 774 00:36:57,380 --> 00:37:00,740 ve açıkça çok yapmak Bu şekilde çok daha büyük, çok, 775 00:37:00,740 --> 00:37:06,460 ama biz aslında görmeye gidiyoruz Bunun için daha akıllı yaklaşımlar 776 00:37:06,460 --> 00:37:08,080 Bunun yerine, hem de, 777 00:37:08,080 --> 00:37:08,720 >> Pekala. 778 00:37:08,720 --> 00:37:10,060 Bu hafta üç için var. 779 00:37:10,060 --> 00:37:11,400 Size yakın zaman göreceksiniz. 780 00:37:11,400 --> 00:37:12,770 Bu CS50 oldu. 781 00:37:12,770 --> 00:37:17,270 782 00:37:17,270 --> 00:37:22,243 >> [MÜZİK OYUN] 783 00:37:22,243 --> 00:37:25,766 >> KONUŞMACI 1: O atıştırma oldu Bir hot fudge sundae yemek bar. 784 00:37:25,766 --> 00:37:28,090 Yüzünde her yerinden tüm vardı. 785 00:37:28,090 --> 00:37:30,506 O bir sakal gibi o çikolata giyiyor 786 00:37:30,506 --> 00:37:31,756 HOPARLÖR 2: Ne yapıyorsun? 787 00:37:31,756 --> 00:37:32,422 KONUŞMACI 3: Hmmm? 788 00:37:32,422 --> 00:37:33,500 Ne? 789 00:37:33,500 --> 00:37:36,800 >> HOPARLÖR 2: Sadece çift dip mi? 790 00:37:36,800 --> 00:37:38,585 Sen çift çip daldırma. 791 00:37:38,585 --> 00:37:39,460 KONUŞMACI 3: Afedersiniz. 792 00:37:39,460 --> 00:37:44,440 HOPARLÖR 2: Sen çip daldırma Bir lokma aldı ve tekrar daldırma. 793 00:37:44,440 --> 00:37:44,940 KONUŞMACI 3: 794 00:37:44,940 --> 00:37:48,440 HOPARLÖR 2: Bu koyarak gibi Yani dip sizin tüm ağız hakkı. 795 00:37:48,440 --> 00:37:52,400 Bir dahaki sefere, bir çip almak Sadece bir kez daldırın ve bitirin. 796 00:37:52,400 --> 00:37:53,890 >> KONUŞMACI 3: Dan ne biliyorsun? 797 00:37:53,890 --> 00:37:58,006 Sen daldırma istediğiniz şekilde daldırma. 798 00:37:58,006 --> 00:38:01,900 Ben daldırma istediğiniz şekilde daldırma edeceğiz. 799 00:38:01,900 --> 00:38:03,194