1 00:00:00,000 --> 00:00:11,100 2 00:00:11,100 --> 00:00:12,300 >> COLUMNA 1: Hola a todos! 3 00:00:12,300 --> 00:00:13,890 Benvido de volta á sección. 4 00:00:13,890 --> 00:00:17,480 Tan feliz de ver tantos de vós, tanto aquí, e todo o mundo que está a asistir en liña. 5 00:00:17,480 --> 00:00:18,760 6 00:00:18,760 --> 00:00:20,920 Así, como benvido de volta habitual. 7 00:00:20,920 --> 00:00:24,360 Espero que todos tiveron un lindo fin de semana, cheo de descanso, relax. 8 00:00:24,360 --> 00:00:26,026 Foi fermoso onte. 9 00:00:26,026 --> 00:00:27,525 Entón, espero que teñan gusto do aire libre. 10 00:00:27,525 --> 00:00:28,840 11 00:00:28,840 --> 00:00:30,610 >> Entón, primeiro de un par de anuncios. 12 00:00:30,610 --> 00:00:31,920 13 00:00:31,920 --> 00:00:32,700 Grading. 14 00:00:32,700 --> 00:00:37,350 Así, a maioría de vostedes debe ficar un enviar correo-e de min sobre o Pset Scratch 15 00:00:37,350 --> 00:00:39,920 así como clasificación para Pset 1. 16 00:00:39,920 --> 00:00:41,000 17 00:00:41,000 --> 00:00:42,220 Así, só un par de cousas. 18 00:00:42,220 --> 00:00:45,150 Asegúrese de usar check50 en style50. 19 00:00:45,150 --> 00:00:47,250 Estas están destinadas a ser recursos para vós, 20 00:00:47,250 --> 00:00:50,660 para asegurarse de que está a recibir tantos puntos como pode 21 00:00:50,660 --> 00:00:52,390 sen perdelos innecesariamente. 22 00:00:52,390 --> 00:00:54,407 Entón, cousas como estilo é moi importante. 23 00:00:54,407 --> 00:00:55,740 Estamos indo a despegar para el. 24 00:00:55,740 --> 00:00:58,115 Algúns de vós xa poden ter notado que a partir do seu Pset. 25 00:00:58,115 --> 00:00:58,920 26 00:00:58,920 --> 00:01:01,450 E check50 é só un xeito moi doado de asegurarse 27 00:01:01,450 --> 00:01:05,050 que en realidade estamos devolvendo o que necesita ser devolta ao usuario, 28 00:01:05,050 --> 00:01:06,690 e que todo funciona correctamente. 29 00:01:06,690 --> 00:01:08,690 30 00:01:08,690 --> 00:01:12,040 >> Na segunda nota, asegúrese de que o seu subida cousas para o cartafol correcta. 31 00:01:12,040 --> 00:01:14,470 Fai miña vida só un pouco máis difícil 32 00:01:14,470 --> 00:01:18,836 se premer Pset 2 en 1 Pset porque cando baixar cousas, 33 00:01:18,836 --> 00:01:20,085 non baixar correctamente. 34 00:01:20,085 --> 00:01:21,690 35 00:01:21,690 --> 00:01:24,560 E sei que é un pouco inestable, nun sistema para acostumar, 36 00:01:24,560 --> 00:01:26,950 pero só ser super coidado, só para min, 37 00:01:26,950 --> 00:01:30,080 de xeito que cando está a recibir correos electrónicos en como 2:00 e eu son de clasificación. 38 00:01:30,080 --> 00:01:33,710 Se non causar teño que ollar todo en torno a súa Pset. 39 00:01:33,710 --> 00:01:34,440 Legal. 40 00:01:34,440 --> 00:01:37,270 >> Sei que é pronto, pero eu totalmente fun pego de sorpresa 41 00:01:37,270 --> 00:01:40,800 por un ensaio que é debido este venres, que meus profesores foron só como, oh si. 42 00:01:40,800 --> 00:01:42,550 Lembre, ten un ensaio debido o venres. 43 00:01:42,550 --> 00:01:45,780 Entón, sei que ninguén gusta para pensar midterms, 44 00:01:45,780 --> 00:01:50,620 pero a súa primeira proba é o 15 de outubro, que outubro é dende esta semana. 45 00:01:50,620 --> 00:01:53,290 Así, pode ser máis cedo do esperado é todo. 46 00:01:53,290 --> 00:01:57,510 Así que non está xogado por sorpresa cando Menciono sección da semana que oh, 47 00:01:57,510 --> 00:02:00,560 súa proba a próxima semana, eu penso Eu te daría un pouco máis 48 00:02:00,560 --> 00:02:01,500 dun heads-up agora. 49 00:02:01,500 --> 00:02:02,970 50 00:02:02,970 --> 00:02:04,660 >> Así, o seu conxunto de problemas, o número tres. 51 00:02:04,660 --> 00:02:07,070 Como a xente leron o especificación por curiosidade? 52 00:02:07,070 --> 00:02:08,560 53 00:02:08,560 --> 00:02:09,199 Está ben. 54 00:02:09,199 --> 00:02:10,229 Temos unha parella. 55 00:02:10,229 --> 00:02:12,320 Tipo de baixo da última semana, pero iso é OK. 56 00:02:12,320 --> 00:02:13,650 Sei que era fermoso fóra. 57 00:02:13,650 --> 00:02:15,120 58 00:02:15,120 --> 00:02:16,660 Entón Break Out. 59 00:02:16,660 --> 00:02:21,010 Definitivamente despois de ter feito ler hoxe a súa especificación, polo menos, 60 00:02:21,010 --> 00:02:25,240 tente como descargar código de distribución e execución 61 00:02:25,240 --> 00:02:27,430 como a primeira inicial cousa que pedir para ti. 62 00:02:27,430 --> 00:02:28,681 63 00:02:28,681 --> 00:02:32,590 Como estamos usando código de distribución e unha biblioteca 64 00:02:32,590 --> 00:02:36,790 que só teño using-- -É só é a segunda vez que fixen iso Pset, 65 00:02:36,790 --> 00:02:38,650 cousas malucas pode ocorrer co seu dispositivo, 66 00:02:38,650 --> 00:02:41,370 e quere descubrir que a fóra agora contra máis tarde. 67 00:02:41,370 --> 00:02:45,570 >> Porque se é noite de quinta ou é Mércores e, por algún motivo 68 00:02:45,570 --> 00:02:48,912 o aparello simplemente non fai quero correr coa biblioteca 69 00:02:48,912 --> 00:02:50,620 ou coa distribución código, o que significa 70 00:02:50,620 --> 00:02:52,309 non pode sequera comezar a facer a codificación. 71 00:02:52,309 --> 00:02:54,100 Porque non pode comprobar a ver se funciona. 72 00:02:54,100 --> 00:02:55,975 O seu non vai ser capaz para ver se compila. 73 00:02:55,975 --> 00:03:00,500 Quere coidar das persoas no inicio semana, cando aínda pode enviar correo-e me 74 00:03:00,500 --> 00:03:03,100 ou un dos outros FT, e podemos obter os fixados. 75 00:03:03,100 --> 00:03:05,410 Porque esas son cuestións que van para-lo 76 00:03:05,410 --> 00:03:07,120 de facer calquera progreso real. 77 00:03:07,120 --> 00:03:10,055 Non é como un erro, que pode só unha especie de saltar. 78 00:03:10,055 --> 00:03:10,712 79 00:03:10,712 --> 00:03:13,420 Se está a ter problemas co seu aparello ou código de distribución, 80 00:03:13,420 --> 00:03:16,211 realmente quere que toman coidar, máis cedo ou máis tarde. 81 00:03:16,211 --> 00:03:20,410 Así, mesmo se non está indo realmente iniciar a codificación, baixar a distribución 82 00:03:20,410 --> 00:03:24,040 código, lea a especificación, asegúrese de todo funciona alí. 83 00:03:24,040 --> 00:03:25,134 Ok? 84 00:03:25,134 --> 00:03:27,675 Se só pode facelo, eu prometer a súa vida será máis fácil. 85 00:03:27,675 --> 00:03:28,800 86 00:03:28,800 --> 00:03:31,410 E así, probablemente vai para facelo agora non? 87 00:03:31,410 --> 00:03:32,100 Está ben. 88 00:03:32,100 --> 00:03:33,950 Así, todas as preguntas alí? 89 00:03:33,950 --> 00:03:35,850 Calquera cousas de loxística? 90 00:03:35,850 --> 00:03:36,910 Todo o mundo é bo? 91 00:03:36,910 --> 00:03:38,270 Está ben. 92 00:03:38,270 --> 00:03:41,700 >> Disclaimer para aqueles de vostede no cuarto e en liña. 93 00:03:41,700 --> 00:03:45,437 Vou estar tentando cambiar entre PowerPoint no dispositivo 94 00:03:45,437 --> 00:03:47,270 porque nós estamos indo estar facendo algunha codificación 95 00:03:47,270 --> 00:03:53,630 hoxe pola demanda popular do anonymous suxestión enquisa eu enviei a semana pasada. 96 00:03:53,630 --> 00:03:55,480 Entón, imos facer algunha codificación. 97 00:03:55,480 --> 00:03:57,800 Entón, se vostedes queren ao lume ata os seus aparellos, 98 00:03:57,800 --> 00:04:02,910 e ten que conseguir un correo electrónico de min, cun arquivo de exemplo. 99 00:04:02,910 --> 00:04:04,310 Por favor, Sinto-se libre para facelo. 100 00:04:04,310 --> 00:04:07,340 >> Entón, imos falar GDB, que é un depurador. 101 00:04:07,340 --> 00:04:09,970 El vai axudar tipo de descubrir onde 102 00:04:09,970 --> 00:04:11,860 as cousas van mal no seu código. 103 00:04:11,860 --> 00:04:15,370 É realmente só un xeito de ti para a etapa a través do seu código que está pasando, 104 00:04:15,370 --> 00:04:19,100 e ser capaz de imprimir variables ou ver o que está realmente a suceder 105 00:04:19,100 --> 00:04:22,980 baixo o capó versículos seu programa só correr, é como fallo, 106 00:04:22,980 --> 00:04:25,030 e queda tipo, ningunha idea o que pasou aquí. 107 00:04:25,030 --> 00:04:26,730 Non sei o que fallou en liña. 108 00:04:26,730 --> 00:04:29,040 Non sei onde errou. 109 00:04:29,040 --> 00:04:31,280 Entón, GDB vai te axudar con iso. 110 00:04:31,280 --> 00:04:35,240 Ademais, se decide seguir si, e ter 61, 111 00:04:35,240 --> 00:04:38,430 vai realmente ser o seu mellor amigo, porque eu te podo dicir 112 00:04:38,430 --> 00:04:40,840 porque eu estou pasando por esa clase. 113 00:04:40,840 --> 00:04:43,620 >> Nós imos ollar para binario investigación, que se vostedes lembrar 114 00:04:43,620 --> 00:04:47,540 o gran exemplo de catálogo telefónico espectáculo de clase. 115 00:04:47,540 --> 00:04:50,620 Estaremos aplicando iso, e camiñando por iso un pouco máis, 116 00:04:50,620 --> 00:04:54,650 e entón nós estamos pasando por catro distintos tipos, que son burbulla, 117 00:04:54,650 --> 00:04:56,285 Selección, Inserción, e mesturar. 118 00:04:56,285 --> 00:04:57,830 119 00:04:57,830 --> 00:04:58,330 Legal. 120 00:04:58,330 --> 00:05:00,390 Entón, GDB como mencionei, é un depurador. 121 00:05:00,390 --> 00:05:01,400 122 00:05:01,400 --> 00:05:09,370 E estes son unha especie de gran cousas, as grandes funcións ou comandos 123 00:05:09,370 --> 00:05:13,240 que utiliza dentro GDB, e eu andarei vostede a través dunha demostración de que en un segundo. 124 00:05:13,240 --> 00:05:15,360 >> Polo tanto, este non é só se ve abstracto. 125 00:05:15,360 --> 00:05:18,000 Vou tentar facelo como formigón posible para vós. 126 00:05:18,000 --> 00:05:19,870 Entón, romper. 127 00:05:19,870 --> 00:05:22,200 El quere estará pausa como, un número, que 128 00:05:22,200 --> 00:05:26,900 representa unha liña no seu programa, ou pode nomear unha función. 129 00:05:26,900 --> 00:05:30,150 Entón, se di romper principal, vai parar en principal, 130 00:05:30,150 --> 00:05:32,400 e deixalo andar por esa función. 131 00:05:32,400 --> 00:05:36,350 >> Do mesmo xeito, se tes algunha externo funcionan como Cambiar ou Cube, 132 00:05:36,350 --> 00:05:38,450 que mirou para a semana pasada. 133 00:05:38,450 --> 00:05:41,780 Se digo que romper un deses, sempre que o seu programa de chat que, 134 00:05:41,780 --> 00:05:44,290 vai esperar para ti diga a el o que facer. 135 00:05:44,290 --> 00:05:47,860 Antes el só vai realizar para que realmente pode pisar dentro da función 136 00:05:47,860 --> 00:05:49,020 e ver o que está pasando. 137 00:05:49,020 --> 00:05:50,370 138 00:05:50,370 --> 00:05:53,515 Entón, a próxima, só ignora o seguinte liña, vai máis funcións. 139 00:05:53,515 --> 00:05:54,730 140 00:05:54,730 --> 00:05:55,560 Step. 141 00:05:55,560 --> 00:05:56,810 Estas son todas pouco abstracto. 142 00:05:56,810 --> 00:06:00,530 Entón, eu estou indo só para pasar por eles, pero vai velos en uso en un segundo. 143 00:06:00,530 --> 00:06:01,810 >> Entrar nunha función. 144 00:06:01,810 --> 00:06:04,170 Entón, como eu estaba dicindo, como con intercambio, que sería 145 00:06:04,170 --> 00:06:07,110 permiten que, en realidade, se está como entrar fisicamente no interior, 146 00:06:07,110 --> 00:06:10,990 pode xogar con estas variables, impresión o que son, ver o que está pasando. 147 00:06:10,990 --> 00:06:12,140 148 00:06:12,140 --> 00:06:14,830 Lista vai literalmente só imprimir o código circundante. 149 00:06:14,830 --> 00:06:17,570 Entón, se tipo de esquecer onde está o seu programa, 150 00:06:17,570 --> 00:06:19,880 ou está a se pregunta o que está a ocorrer ao seu redor, 151 00:06:19,880 --> 00:06:23,790 iso só vai imprimir un segmento de como cinco ou seis liñas en torno a el. 152 00:06:23,790 --> 00:06:26,080 Así, pode orientarse sobre onde está. 153 00:06:26,080 --> 00:06:27,230 154 00:06:27,230 --> 00:06:28,650 >> Imprimir algunha variable. 155 00:06:28,650 --> 00:06:34,590 Entón, se ten a clave como en César, que imos ollar. 156 00:06:34,590 --> 00:06:36,220 Pode dicir clave impresión en calquera punto. 157 00:06:36,220 --> 00:06:40,070 El vai dicir-lle que o valor é tan que quizais nalgún lugar ao longo do camiño, 158 00:06:40,070 --> 00:06:42,070 vostede substituíu a súa chave. 159 00:06:42,070 --> 00:06:45,495 Pode realmente dicir que, debido realmente pode observar ese valor. 160 00:06:45,495 --> 00:06:46,500 161 00:06:46,500 --> 00:06:48,780 >> Nos locais, só impresións as variables locais. 162 00:06:48,780 --> 00:06:53,120 Entón, cando está dentro dun loop, e só quere ver como, oh. 163 00:06:53,120 --> 00:06:54,270 Cal é o meu eu? 164 00:06:54,270 --> 00:06:57,020 ¿Que é este valor de clave que eu arrincar aquí? 165 00:06:57,020 --> 00:06:58,537 Cal é a mensaxe neste momento? 166 00:06:58,537 --> 00:07:00,370 Ela só vai imprimir todo daqueles, de modo a estar 167 00:07:00,370 --> 00:07:04,330 Non ten que individualmente dicir, I. Imprimir Imprimir mensaxe. 168 00:07:04,330 --> 00:07:04,970 Imprimir Key. 169 00:07:04,970 --> 00:07:06,190 170 00:07:06,190 --> 00:07:07,700 E logo amosar. 171 00:07:07,700 --> 00:07:10,370 O que fai é como paso a través do programa, 172 00:07:10,370 --> 00:07:13,980 el só vai estar seguro de que é mostrando algúns determinada variable 173 00:07:13,980 --> 00:07:14,780 en todos os puntos. 174 00:07:14,780 --> 00:07:17,160 Para que Também-- -É unha especie de acceso directo, onde 175 00:07:17,160 --> 00:07:19,530 non ten que seguir así, oh. 176 00:07:19,530 --> 00:07:23,150 Chave de impresión ou impresión I. El só ha automaticamente facelo por vostede. 177 00:07:23,150 --> 00:07:25,959 >> Entón, con iso, imos para ver como isto vai. 178 00:07:25,959 --> 00:07:28,000 Vou probar e chave para o meu aparato. 179 00:07:28,000 --> 00:07:30,200 180 00:07:30,200 --> 00:07:31,271 Vexa se podo facelo. 181 00:07:31,271 --> 00:07:31,770 All. 182 00:07:31,770 --> 00:07:40,970 183 00:07:40,970 --> 00:07:42,370 Nós só estamos indo a reflictir-lo. 184 00:07:42,370 --> 00:07:44,530 Non hai nada de tolo no meu portátil de calquera maneira. 185 00:07:44,530 --> 00:07:49,600 186 00:07:49,600 --> 00:07:50,100 Está ben. 187 00:07:50,100 --> 00:07:57,030 188 00:07:57,030 --> 00:08:01,054 Isto ten que ser un regalo. 189 00:08:01,054 --> 00:08:01,795 É tan pequena. 190 00:08:01,795 --> 00:08:03,730 191 00:08:03,730 --> 00:08:05,120 A ver se podemos facelo. 192 00:08:05,120 --> 00:08:09,970 193 00:08:09,970 --> 00:08:10,940 >> Está ben. 194 00:08:10,940 --> 00:08:15,305 Alice está obviamente loitando aquí só un pouco, 195 00:08:15,305 --> 00:08:17,995 pero nós imos busca-la en un momento. 196 00:08:17,995 --> 00:08:20,810 197 00:08:20,810 --> 00:08:22,020 Está ben. 198 00:08:22,020 --> 00:08:25,900 Nós só estamos indo a aumentar iso. 199 00:08:25,900 --> 00:08:28,770 200 00:08:28,770 --> 00:08:29,380 Está ben. 201 00:08:29,380 --> 00:08:31,679 Todos poden ver que tipo de? 202 00:08:31,679 --> 00:08:32,470 Quizais un pouco? 203 00:08:32,470 --> 00:08:33,594 Sei que é un pouco pequeno. 204 00:08:33,594 --> 00:08:34,570 205 00:08:34,570 --> 00:08:37,530 Non pode descubrir como facer esta grande. 206 00:08:37,530 --> 00:08:38,350 Se alguén sabe. 207 00:08:38,350 --> 00:08:40,309 Alguén sabe como facelo máis grande? 208 00:08:40,309 --> 00:08:40,932 Está ben. 209 00:08:40,932 --> 00:08:42,140 Nós imos rodar con el. 210 00:08:42,140 --> 00:08:45,801 Non importa de calquera maneira, porque é só ese é o código que vostedes deberían 211 00:08:45,801 --> 00:08:46,300 ter. 212 00:08:46,300 --> 00:08:48,310 >> O que é máis importante é o terminal aquí. 213 00:08:48,310 --> 00:08:52,840 214 00:08:52,840 --> 00:08:58,690 E nós temos aquí Por que é tan pequeno? 215 00:08:58,690 --> 00:09:02,325 216 00:09:02,325 --> 00:09:02,825 Configuración. 217 00:09:02,825 --> 00:09:07,920 218 00:09:07,920 --> 00:09:08,420 Oh. 219 00:09:08,420 --> 00:09:09,500 Certo Ike. 220 00:09:09,500 --> 00:09:10,880 Como é iso? 221 00:09:10,880 --> 00:09:11,770 Fóra de alí. 222 00:09:11,770 --> 00:09:19,370 223 00:09:19,370 --> 00:09:21,810 Isto é mellor para todos? 224 00:09:21,810 --> 00:09:22,525 Está ben,. 225 00:09:22,525 --> 00:09:23,025 Legal. 226 00:09:23,025 --> 00:09:25,830 227 00:09:25,830 --> 00:09:28,220 >> Sabe cando está nun CS clase dificultades técnicas 228 00:09:28,220 --> 00:09:32,971 son unha especie de parte as-- Entón, imos aclarar iso. 229 00:09:32,971 --> 00:09:33,470 Está ben. 230 00:09:33,470 --> 00:09:38,060 Entón, aquí na sección, que tivemos aquí. 231 00:09:38,060 --> 00:09:40,830 César é un ficheiro executábel. 232 00:09:40,830 --> 00:09:41,800 Entón eu fixen iso. 233 00:09:41,800 --> 00:09:46,370 Entón, unha cousa a entender é co GDB que só funciona en ficheiros executábeis. 234 00:09:46,370 --> 00:09:48,040 Entón, non pode executa-lo nun Dotsy. 235 00:09:48,040 --> 00:09:50,532 Ten que realmente facer Asegúrese de que o seu código é compilado, 236 00:09:50,532 --> 00:09:51,865 e que, en realidade, pode ser executado. 237 00:09:51,865 --> 00:09:52,970 238 00:09:52,970 --> 00:09:56,186 >> Entón, asegúrese de que, se iso non acontecer compilar, obtelo para compilar, 239 00:09:56,186 --> 00:09:57,810 de modo que pode tipo de correr con el. 240 00:09:57,810 --> 00:10:04,590 Entón, para comezar GDB, todo o que fai, Gloria tipo GDB, e entón só o 241 00:10:04,590 --> 00:10:06,250 ficheiro que quere. 242 00:10:06,250 --> 00:10:08,240 Sempre cometer erros César. 243 00:10:08,240 --> 00:10:11,730 Pero quere estar seguro xa que é un executable, 244 00:10:11,730 --> 00:10:14,210 Flash punto de ti para que significa que vai 245 00:10:14,210 --> 00:10:19,240 para realizar CSI está indo a executar este ficheiros ou co depurador. 246 00:10:19,240 --> 00:10:19,910 Está ben. 247 00:10:19,910 --> 00:10:22,885 Entón, ten que, comeza este tipo de rabiscos. 248 00:10:22,885 --> 00:10:24,250 249 00:10:24,250 --> 00:10:25,750 É só sobre todas as cousas depurador. 250 00:10:25,750 --> 00:10:28,200 Realmente non ten que hai problema con iso agora. 251 00:10:28,200 --> 00:10:31,460 E como podes ver, temos esta parénteses en aberto, o PIB, parénteses próximos, 252 00:10:31,460 --> 00:10:34,690 e só se parece nosa liña de comandos, non? 253 00:10:34,690 --> 00:10:37,010 >> Entón, o que queremos fazer-- -Só, O primeiro 254 00:10:37,010 --> 00:10:39,570 é que queremos elixir un lugar para rompe-lo. 255 00:10:39,570 --> 00:10:42,332 Entón, hai un erro neste programa Caesar 256 00:10:42,332 --> 00:10:44,290 que presento, que imos descubrir. 257 00:10:44,290 --> 00:10:45,330 258 00:10:45,330 --> 00:10:56,350 É o que fai é que leva a entrada Barfoo en todas as tapas, e por algunha razón 259 00:10:56,350 --> 00:11:01,950 iso non cambia A. El só deixa só, é todo máis correcta, 260 00:11:01,950 --> 00:11:03,980 pero a segunda letra A permanece inalterado. 261 00:11:03,980 --> 00:11:07,120 Entón, nós estamos indo a tentar descubrir por que isto ocorre. 262 00:11:07,120 --> 00:11:10,440 Entón, o primeiro que normalmente quero facer sempre que comezar en GDB 263 00:11:10,440 --> 00:11:12,010 é descubrir onde a rompe-lo. 264 00:11:12,010 --> 00:11:14,956 >> Entón, César é un pequeno programa. 265 00:11:14,956 --> 00:11:16,330 Nós só temos unha función, non? 266 00:11:16,330 --> 00:11:18,520 Cal foi a nosa función no Caesar? 267 00:11:18,520 --> 00:11:19,590 268 00:11:19,590 --> 00:11:24,350 Hai só unha función, non Main? 269 00:11:24,350 --> 00:11:26,490 Home é unha función para todos os seus programas. 270 00:11:26,490 --> 00:11:29,230 Se non ten Main, eu podería ser un pouco preocupado agora, 271 00:11:29,230 --> 00:11:31,000 pero espero que todos tiveran principal alí. 272 00:11:31,000 --> 00:11:34,150 Entón, o que podemos facer é que podemos só romper principal, só como aquel. 273 00:11:34,150 --> 00:11:35,190 Así, el di, Aceptar. 274 00:11:35,190 --> 00:11:37,430 Montar noso único breakpoint alí. 275 00:11:37,430 --> 00:11:42,870 >> Entón, agora a cousa a lembrar de César leva un argumento de liña de comandos para a dereita 276 00:11:42,870 --> 00:11:45,150 e nós non fixemos iso en calquera lugar aínda. 277 00:11:45,150 --> 00:11:47,560 Entón, o que fai é cando realmente ir a correr 278 00:11:47,560 --> 00:11:51,540 o programa, calquera programa que está funcionando en GDB que precisa de liña de comandos 279 00:11:51,540 --> 00:11:55,010 argumentos, está indo a entrada cando comezar a executa-lo. 280 00:11:55,010 --> 00:11:59,280 Entón, neste caso, o que facemos Execute cunha chave de tres. 281 00:11:59,280 --> 00:12:00,770 282 00:12:00,770 --> 00:12:02,040 E que vai realmente comezar. 283 00:12:02,040 --> 00:12:08,480 >> Entón, se ve aquí, temos Se RC non é igual a 2. 284 00:12:08,480 --> 00:12:12,210 Entón, se vostedes todos teñen o ficheiro que eu enviei-se 285 00:12:12,210 --> 00:12:15,100 vai ver que iso é como o primeira liña a nosa función principal, non? 286 00:12:15,100 --> 00:12:17,890 Está comprobando a ver se temos o número correcto de argumentos. 287 00:12:17,890 --> 00:12:20,620 Entón, se está a se pregunta RC se é correcta, 288 00:12:20,620 --> 00:12:23,250 pode facer algo como impresión RC. 289 00:12:23,250 --> 00:12:24,380 290 00:12:24,380 --> 00:12:28,640 RC é de dous, que é o que esperabamos, non? 291 00:12:28,640 --> 00:12:32,010 >> Entón, podemos ir Logo e continúan ata. 292 00:12:32,010 --> 00:12:33,200 Entón, nós temos algunha clave alí. 293 00:12:33,200 --> 00:12:34,260 294 00:12:34,260 --> 00:12:37,090 E podemos imprimir nosa clave para asegurarse de que é correcta. 295 00:12:37,090 --> 00:12:38,380 296 00:12:38,380 --> 00:12:39,500 Interesante. 297 00:12:39,500 --> 00:12:41,210 Non é así o que esperabamos. 298 00:12:41,210 --> 00:12:44,810 Entón, unha cousa a entender co GDB tamén, é 299 00:12:44,810 --> 00:12:49,000 que non é ata que realmente acertar Logo que a liña que acaba de ver 300 00:12:49,000 --> 00:12:50,720 é realmente executada. 301 00:12:50,720 --> 00:12:53,870 Así, neste caso Key non teña aínda foi asignado. 302 00:12:53,870 --> 00:12:57,050 Entón, Key é algún valor de lixo que ve na parte inferior alí. 303 00:12:57,050 --> 00:13:03,680 Negativo $ 120-- -É mil millóns e algo que cousas estrañas non? 304 00:13:03,680 --> 00:13:05,340 Non é a clave que esperabamos. 305 00:13:05,340 --> 00:13:10,720 Pero se se loita en Seguinte e, a continuación, tentar clave de impresión, é tres. 306 00:13:10,720 --> 00:13:11,710 >> Todo o mundo ve isto? 307 00:13:11,710 --> 00:13:13,780 Entón, se conseguir algo que lle gusta, espere. 308 00:13:13,780 --> 00:13:15,540 Isto é completamente mal, e eu non sei 309 00:13:15,540 --> 00:13:20,150 como iso ía acontecer, porque todo o que quero facer é asignar un número, unha variable, 310 00:13:20,150 --> 00:13:22,900 tentar bater continuación, proba imprimir de novo, e ver se funciona. 311 00:13:22,900 --> 00:13:27,830 Porque só vai executar e de feito, asignar algo despois que 312 00:13:27,830 --> 00:13:29,340 prema en Next. 313 00:13:29,340 --> 00:13:30,336 Ter sentido para todos? 314 00:13:30,336 --> 00:13:30,836 Uh huh? 315 00:13:30,836 --> 00:13:33,220 >> COLUMNA 2: Cando chou números o que significa isto? 316 00:13:33,220 --> 00:13:34,790 >> COLUMNA 1: É só aleatoria. 317 00:13:34,790 --> 00:13:35,710 É só lixo. 318 00:13:35,710 --> 00:13:38,320 É só algo que o seu ordenador pode atribuír ao acaso. 319 00:13:38,320 --> 00:13:39,721 320 00:13:39,721 --> 00:13:40,220 Legal. 321 00:13:40,220 --> 00:13:45,760 Entón, agora podemos pasar a través, e así por agora temos este GetString texto simple. 322 00:13:45,760 --> 00:13:48,600 Entón, deixe-me presentar o que ocorrerá cando se loita continuación aquí. 323 00:13:48,600 --> 00:13:51,320 A nosa GDB tipo de desaparece, non? 324 00:13:51,320 --> 00:13:55,720 Isto porque GetString agora está en execución, non? 325 00:13:55,720 --> 00:14:01,460 Entón, cando vimos texto é igual a GetString, parénteses abertos e parénteses, 326 00:14:01,460 --> 00:14:04,380 e prema en Next, que ten realmente executada agora. 327 00:14:04,380 --> 00:14:06,580 Entón, está esperando por nos a entrada de algo. 328 00:14:06,580 --> 00:14:13,560 >> Entón, nós estamos indo a entrada a nosa comida que é o que está fallando, como dixen a vostede 329 00:14:13,560 --> 00:14:18,020 e que só di que é rematar a execución, que o pechou 330 00:14:18,020 --> 00:14:19,980 soporte significa que é sae fóra dese circuíto. 331 00:14:19,980 --> 00:14:21,170 332 00:14:21,170 --> 00:14:25,420 Así, podemos bater continuación, e agora, como eu son seguro de que está familiarizado de César, 333 00:14:25,420 --> 00:14:27,260 é dicir, o que é esta liña vai facer. 334 00:14:27,260 --> 00:14:32,030 É para Int I é igual a 0, N é igual a Strlen, texto simple e, a continuación, 335 00:14:32,030 --> 00:14:33,960 I é menor que n, I, plus, plus. 336 00:14:33,960 --> 00:14:35,210 ¿Que é este lazo vai facer? 337 00:14:35,210 --> 00:14:37,900 338 00:14:37,900 --> 00:14:39,160 Abre a mensaxe. 339 00:14:39,160 --> 00:14:39,770 Legal. 340 00:14:39,770 --> 00:14:41,330 Entón, imos comezar a facelo. 341 00:14:41,330 --> 00:14:47,210 >> Así, se esta condición corresponden, para o noso primeiro? 342 00:14:47,210 --> 00:14:52,250 Se é un B, é texto simple I. Pode obter información sobre os nosos veciños. 343 00:14:52,250 --> 00:14:53,610 344 00:14:53,610 --> 00:14:57,970 Así, I é cero, e se seis, que Esperamos, ea nosa clave é tres. 345 00:14:57,970 --> 00:14:59,227 Todo o que ten sentido, non? 346 00:14:59,227 --> 00:15:01,310 Estes números son todos o que debe ser. 347 00:15:01,310 --> 00:15:02,590 348 00:15:02,590 --> 00:15:03,870 Entón, hum? 349 00:15:03,870 --> 00:15:05,620 COLUMNA 3: Eu teño números aleatorios para min. 350 00:15:05,620 --> 00:15:09,156 351 00:15:09,156 --> 00:15:12,030 COLUMNA 1: Ben, podemos check-- --nós pode falar sobre iso nun segundo. 352 00:15:12,030 --> 00:15:14,110 353 00:15:14,110 --> 00:15:15,750 Pero ten que estar recibindo este. 354 00:15:15,750 --> 00:15:17,700 355 00:15:17,700 --> 00:15:20,130 Entón, se temos un capital B ao noso primeiro, 356 00:15:20,130 --> 00:15:22,080 esta condición debe pegalo, non? 357 00:15:22,080 --> 00:15:27,120 Entón, se se loita Logo vemos que esta Se realmente executa. 358 00:15:27,120 --> 00:15:29,220 Porque se está seguindo ao longo do seu código, 359 00:15:29,220 --> 00:15:33,460 esta liña aquí, onde texto I substitúese con esta aritmética, 360 00:15:33,460 --> 00:15:35,720 só é executado cada caso condición é correcto correcto? 361 00:15:35,720 --> 00:15:36,905 362 00:15:36,905 --> 00:15:40,240 >> GDB só vai amosar-lle as cousas que son realmente execución. 363 00:15:40,240 --> 00:15:45,140 Entón, se esa condición Se non foi cumprida, é só vai saltar á seguinte liña. 364 00:15:45,140 --> 00:15:46,540 Ok? 365 00:15:46,540 --> 00:15:48,510 Entón, nós temos que. 366 00:15:48,510 --> 00:15:51,171 Este soporte significa que é pechado fóra dese ciclo agora. 367 00:15:51,171 --> 00:15:52,420 Entón, que vai comezar de novo. 368 00:15:52,420 --> 00:15:54,760 369 00:15:54,760 --> 00:15:56,280 Só iso. 370 00:15:56,280 --> 00:15:59,120 Entón, que poidamos obter información sobre os nosos veciños aquí, 371 00:15:59,120 --> 00:16:02,575 e vemos que o noso primeiro letra cambiou, non? 372 00:16:02,575 --> 00:16:05,150 É agora un E, como debería ser. 373 00:16:05,150 --> 00:16:07,360 Así, podemos continuar. 374 00:16:07,360 --> 00:16:08,500 >> E nós temos esa comprobación. 375 00:16:08,500 --> 00:16:09,916 E esa comprobación debe funcionar, non? 376 00:16:09,916 --> 00:16:12,570 É A. Debe ser cambiado tres cartas para adiante. 377 00:16:12,570 --> 00:16:14,320 378 00:16:14,320 --> 00:16:16,530 Pero se observar, nos obter algo diferente. 379 00:16:16,530 --> 00:16:17,580 380 00:16:17,580 --> 00:16:22,860 Polo tanto, neste caso aquí enriba, el pegou Lo, e así que esta liña executada, 381 00:16:22,860 --> 00:16:28,620 que modificou a nosa B. Pero, neste caso aquí, 382 00:16:28,620 --> 00:16:32,860 temos que simplemente ignorados, e fun para o [? L Siff. ?] 383 00:16:32,860 --> 00:16:34,660 Entón, algo está a suceder alí. 384 00:16:34,660 --> 00:16:37,780 O que está dicindo é que, sabemos que debe incorporarse aquí, 385 00:16:37,780 --> 00:16:39,200 pero non é. 386 00:16:39,200 --> 00:16:42,210 Calquera pode ver que o noso problema é nesta liña? 387 00:16:42,210 --> 00:16:45,380 388 00:16:45,380 --> 00:16:46,969 É unha cousa moi minuto. 389 00:16:46,969 --> 00:16:48,510 E tamén se pode ollar para o seu código. 390 00:16:48,510 --> 00:16:49,980 391 00:16:49,980 --> 00:16:54,940 Tamén linha-- esquecer que liña é en há-- pero é no [inaudível]. 392 00:16:54,940 --> 00:16:55,480 Si? 393 00:16:55,480 --> 00:16:58,639 >> COLUMNA 4: É o máis grande que páxina, se lelo no libro. 394 00:16:58,639 --> 00:16:59,430 COLUMNA 1: Exactamente. 395 00:16:59,430 --> 00:17:02,620 Así, o depurador non podería dicir iso, pero o depurador 396 00:17:02,620 --> 00:17:05,880 podería facelo para abaixo a unha liña que sabe que non funciona. 397 00:17:05,880 --> 00:17:09,319 E ás veces, cando todo ao final do semestre, cando 398 00:17:09,319 --> 00:17:12,910 está lidando con un centenar, unha cen algunhas liñas de código, e 399 00:17:12,910 --> 00:17:16,190 Non sei onde está fallando, esta é unha boa forma de facelo. 400 00:17:16,190 --> 00:17:17,900 401 00:17:17,900 --> 00:17:18,989 Así, atopamos o noso erro. 402 00:17:18,989 --> 00:17:21,530 Pode resolve-lo no seu arquivo, e logo, pode executa-lo de novo, 403 00:17:21,530 --> 00:17:23,029 e todo funcionaría perfectamente. 404 00:17:23,029 --> 00:17:24,970 405 00:17:24,970 --> 00:17:30,590 E o máis importante é isto pode parecer, Aceptar. 406 00:17:30,590 --> 00:17:31,090 Si. 407 00:17:31,090 --> 00:17:31,370 Legal. 408 00:17:31,370 --> 00:17:32,744 Sabía que está a procurar. 409 00:17:32,744 --> 00:17:34,910 Entón, vostede sabía o que facer. 410 00:17:34,910 --> 00:17:39,021 >> GDB pode ser super útil porque Pode imprimir todas esas cousas que 411 00:17:39,021 --> 00:17:39,520 non o faría. 412 00:17:39,520 --> 00:17:41,160 É moito máis útil do que printf. 413 00:17:41,160 --> 00:17:43,440 Cantos de vostedes usan como declaracións printf 414 00:17:43,440 --> 00:17:46,200 para descubrir onde un erro foi, non? 415 00:17:46,200 --> 00:17:48,450 Entón, con iso, non ten que manter a volver, 416 00:17:48,450 --> 00:17:51,139 e gústalle comentar en Printf, ou comentar, 417 00:17:51,139 --> 00:17:52,930 e descubrir o que ten que ser a impresión. 418 00:17:52,930 --> 00:17:55,670 Este, de feito, só permite que percorrer, imprimir cousas 419 00:17:55,670 --> 00:18:00,000 como está pasando, por iso, pode observar como cambian en tempo real, 420 00:18:00,000 --> 00:18:02,190 como o programa está a ser executado. 421 00:18:02,190 --> 00:18:04,390 >> E iso leva un pouco pouco de tempo para se acostumar. 422 00:18:04,390 --> 00:18:07,850 Recomendo só unha especie de ser un pouco frustrado con iso 423 00:18:07,850 --> 00:18:08,930 para agora. 424 00:18:08,930 --> 00:18:13,450 Se pasar unha hora sobre o semana aprendendo a usar o GDB, 425 00:18:13,450 --> 00:18:16,140 vai gardar tanto tempo despois. 426 00:18:16,140 --> 00:18:18,750 E literalmente. dicimos iso para a xente cada ano, 427 00:18:18,750 --> 00:18:23,890 e eu recordo cando eu tirei o clase, eu era como, eu vou estar ben. 428 00:18:23,890 --> 00:18:24,700 Non. 429 00:18:24,700 --> 00:18:27,030 Pset 6 chegou e eu estaba como, eu vou aprender 430 00:18:27,030 --> 00:18:29,500 como usar o GDB porque eu non saber o que está pasando aquí. 431 00:18:29,500 --> 00:18:32,940 >> Entón, se tomar o tempo para usalo en programas menores 432 00:18:32,940 --> 00:18:35,697 que está indo a ser traballando, como traballar 433 00:18:35,697 --> 00:18:37,530 por algo así como Visionare, como este. 434 00:18:37,530 --> 00:18:38,800 435 00:18:38,800 --> 00:18:42,850 Ou se quere práctica adicional, estou seguro Podería vir enriba con programas de buggy, 436 00:18:42,850 --> 00:18:45,300 para que poida depurar se desexa. 437 00:18:45,300 --> 00:18:49,300 >> Pero se só levar moito tempo para chegar acostumar con iso, só xogar con el, 438 00:18:49,300 --> 00:18:50,550 el realmente vai atender-lo ben. 439 00:18:50,550 --> 00:18:52,591 E é realmente unha das aquelas cousas que só 440 00:18:52,591 --> 00:18:57,340 ten que tentar, e ensuciar as mans con, antes de que realmente entende-la. 441 00:18:57,340 --> 00:19:02,090 Realmente só entendín xa Eu tiña de depuración cousas con el, 442 00:19:02,090 --> 00:19:08,170 e é moito máis agradable para ter unha idea do como depurar, máis cedo ou máis tarde. 443 00:19:08,170 --> 00:19:08,850 Está ben. 444 00:19:08,850 --> 00:19:09,625 Legal. 445 00:19:09,625 --> 00:19:12,960 Sei que é tipo como un curso intensivo de GDB, 446 00:19:12,960 --> 00:19:16,400 e seguramente vou traballar para ter estes para parecer maior a próxima vez. 447 00:19:16,400 --> 00:19:17,590 448 00:19:17,590 --> 00:19:18,280 Legal. 449 00:19:18,280 --> 00:19:20,390 >> Así, se volvemos ao noso PowerPoint. 450 00:19:20,390 --> 00:19:27,194 451 00:19:27,194 --> 00:19:28,110 Será que isto vai funcionar? 452 00:19:28,110 --> 00:19:29,711 453 00:19:29,711 --> 00:19:30,210 AWH. 454 00:19:30,210 --> 00:19:31,101 Si. 455 00:19:31,101 --> 00:19:31,600 Está ben. 456 00:19:31,600 --> 00:19:35,480 Entón, se precisa de calquera dos aqueles de novo, hai a lista. 457 00:19:35,480 --> 00:19:37,160 458 00:19:37,160 --> 00:19:40,830 Busca Entón binario, que todos recorda o gran espectáculo de David 459 00:19:40,830 --> 00:19:42,259 rasgando teléfono libros pola metade. 460 00:19:42,259 --> 00:19:44,050 Realmente non entendo o libros de teléfono máis, 461 00:19:44,050 --> 00:19:46,530 porque, como onde obter libros de teléfono nos días de hoxe? 462 00:19:46,530 --> 00:19:48,220 Realmente non sei. 463 00:19:48,220 --> 00:19:49,840 464 00:19:49,840 --> 00:19:50,590 A procura binaria. 465 00:19:50,590 --> 00:19:52,464 Alguén se lembra Como Binary traballos de investigación? 466 00:19:52,464 --> 00:19:54,380 467 00:19:54,380 --> 00:19:55,220 Calquera en todo? 468 00:19:55,220 --> 00:19:56,325 Si? 469 00:19:56,325 --> 00:19:58,283 COLUMNA 5: Vostede sabe cando ollar para que a metade 470 00:19:58,283 --> 00:20:01,146 sería en, Con base niso, e librar-se da outra metade. 471 00:20:01,146 --> 00:20:01,896 >> COLUMNA 1 Exactamente. 472 00:20:01,896 --> 00:20:06,290 Entón, Busca binaria, é unha especie de a-- --nós gusta de chamalo de dividir e conquistar. 473 00:20:06,290 --> 00:20:09,170 Entón, o que vai facer é vai mirar no medio, 474 00:20:09,170 --> 00:20:11,990 e vai ver se corresponde o que está a procurar. 475 00:20:11,990 --> 00:20:15,420 E se iso non acontecer, entón tenta descubrir, é que será deixado 476 00:20:15,420 --> 00:20:16,450 metade ou a metade dereita. 477 00:20:16,450 --> 00:20:19,325 Entón, iso se pode se está a buscar en algo que está en orde alfabética, 478 00:20:19,325 --> 00:20:20,720 mira ti, oh. 479 00:20:20,720 --> 00:20:22,750 Será que Allison vir antes M? 480 00:20:22,750 --> 00:20:23,250 Si. 481 00:20:23,250 --> 00:20:25,030 Entón, nós estamos indo a mirar para o primeiro semestre. 482 00:20:25,030 --> 00:20:26,450 >> Ou pode ser como cos números. 483 00:20:26,450 --> 00:20:28,830 O que se poida comparar, pode ser resolto. 484 00:20:28,830 --> 00:20:29,920 485 00:20:29,920 --> 00:20:31,260 Podes utilizar a busca binaria en. 486 00:20:31,260 --> 00:20:32,340 487 00:20:32,340 --> 00:20:37,455 Entón, alguén se lembra deste gráfico ou o que é iso? 488 00:20:37,455 --> 00:20:39,520 É Complexidade asintótica. 489 00:20:39,520 --> 00:20:42,830 Así, este gráfico só describe o tempo que 490 00:20:42,830 --> 00:20:46,230 leva a resolver un problema como aumenta o número de cousas 491 00:20:46,230 --> 00:20:47,090 que está a usar. 492 00:20:47,090 --> 00:20:51,260 >> Entón, nós temos N, que é o tempo lineal. 493 00:20:51,260 --> 00:20:54,560 Se N ao longo de dous, o que é lixeiramente mellor, aínda medra super rápido. 494 00:20:54,560 --> 00:20:58,360 E entón debemos sesión, que é o que consideramos Binary Search. 495 00:20:58,360 --> 00:21:03,630 Se se decata que o seu problema queda moito máis e moito máis grande, 496 00:21:03,630 --> 00:21:06,600 o tempo que leva para resolver-lo non vai aumentar moito. 497 00:21:06,600 --> 00:21:09,010 É como comparable aquí no inicio. 498 00:21:09,010 --> 00:21:10,060 Vostede é como, Aceptar. 499 00:21:10,060 --> 00:21:13,000 Calquera cousa aquí realmente non importa que usamos, 500 00:21:13,000 --> 00:21:16,220 pero saír dun millón, mil millóns. 501 00:21:16,220 --> 00:21:20,010 Está intentando atopar some-- --you're intentando atopar unha agulla nun palheiro. 502 00:21:20,010 --> 00:21:21,550 >> Creo que quere este problema. 503 00:21:21,550 --> 00:21:25,850 Quere que esta complexidade, non lineal porque para todo o que 504 00:21:25,850 --> 00:21:30,049 coñecer o seu vai estar buscando por cada agulla individuo, cousa de feno, 505 00:21:30,049 --> 00:21:31,340 tentando ollar para a agulla. 506 00:21:31,340 --> 00:21:34,730 E iso non é moi divertido, na miña opinión. 507 00:21:34,730 --> 00:21:35,500 Gústame rápido. 508 00:21:35,500 --> 00:21:36,620 Gústame eficiente. 509 00:21:36,620 --> 00:21:40,450 E estudantes, traballadoras ti caras son, saben traballar de forma máis intelixente, 510 00:21:40,450 --> 00:21:43,010 non máis difícil tipo de cousas, como pode chegar a ser estes algoritmos. 511 00:21:43,010 --> 00:21:45,110 512 00:21:45,110 --> 00:21:47,910 >> Entón, nós estamos indo a pé a través de só un exemplo rápido. 513 00:21:47,910 --> 00:21:51,090 Creo que vostedes deben ter unha man en Investigación binaria, 514 00:21:51,090 --> 00:21:54,352 pero no caso de alguén é algo difusa, quere reforzalo lo, 515 00:21:54,352 --> 00:21:56,310 imos só ir a través dun exemplo aquí. 516 00:21:56,310 --> 00:21:59,490 Entón, a xente está a buscar se a matriz contén sete. 517 00:21:59,490 --> 00:22:00,540 518 00:22:00,540 --> 00:22:06,010 >> Entón, o primeiro que facemos é mirar no medio, non? 519 00:22:06,010 --> 00:22:09,340 E tamén vai ser a codificación Busca binaria en só un segundo. 520 00:22:09,340 --> 00:22:11,310 Entón, iso vai ser divertido. 521 00:22:11,310 --> 00:22:13,710 Entón, nós miramos no matrices pequenas medianas 3. 522 00:22:13,710 --> 00:22:15,501 Fai tres igualar 7? 523 00:22:15,501 --> 00:22:16,000 Non. 524 00:22:16,000 --> 00:22:18,670 525 00:22:18,670 --> 00:22:19,550 É seis. 526 00:22:19,550 --> 00:22:21,480 Entón, é menor que ou maior que sete? 527 00:22:21,480 --> 00:22:23,080 528 00:22:23,080 --> 00:22:23,960 Menor que. 529 00:22:23,960 --> 00:22:24,570 Si. 530 00:22:24,570 --> 00:22:25,170 Caras bo traballo. 531 00:22:25,170 --> 00:22:25,569 532 00:22:25,569 --> 00:22:27,360 Eu sinto que como eu debería temos doces porque eu 533 00:22:27,360 --> 00:22:29,460 quere xoga-lo fóra para os estaleiros. 534 00:22:29,460 --> 00:22:30,270 É o que eu vou facer a próxima semana. 535 00:22:30,270 --> 00:22:31,436 El vai manter vostedes afiada. 536 00:22:31,436 --> 00:22:32,560 537 00:22:32,560 --> 00:22:34,690 >> Entón, nós xogamos fóra que primeiro semestre, non? 538 00:22:34,690 --> 00:22:35,670 foi menor que. 539 00:22:35,670 --> 00:22:39,325 sabemos que todo en que parte esquerda 540 00:22:39,325 --> 00:22:41,700 será menos que o que estamos realmente a procurar. 541 00:22:41,700 --> 00:22:43,491 Así, non hai necesidade de prestar atención a ela. 542 00:22:43,491 --> 00:22:45,120 Só esqueza sobre iso. 543 00:22:45,120 --> 00:22:48,720 Entón, agora miramos para o noso lado dereito, e miramos para o medio alí, 544 00:22:48,720 --> 00:22:50,510 e agora son nove. 545 00:22:50,510 --> 00:22:55,510 Entón, 9 é-- --Everyone? 546 00:22:55,510 --> 00:22:57,470 Maior que o que somos buscar, non? 547 00:22:57,470 --> 00:22:59,860 Entón, nós estamos indo xogar fóra todo para a dereita. 548 00:22:59,860 --> 00:23:00,970 549 00:23:00,970 --> 00:23:01,940 Como aquel. 550 00:23:01,940 --> 00:23:03,700 Agora, todos nós é deixar con un. 551 00:23:03,700 --> 00:23:07,760 Entón, imos comprobar, é este o que que estamos a buscar? el é. 552 00:23:07,760 --> 00:23:08,970 Atopamos o que queriamos. 553 00:23:08,970 --> 00:23:10,440 554 00:23:10,440 --> 00:23:11,690 Por iso, está feito. 555 00:23:11,690 --> 00:23:12,550 Bilinear Search. 556 00:23:12,550 --> 00:23:15,740 >> E se observar, nos tiña sete entradas de alí. 557 00:23:15,740 --> 00:23:24,320 Levou só nós como tres veces, pero se está facendo como un billón, 558 00:23:24,320 --> 00:23:28,190 vostedes saben cantos pasos que faría ter se tivésemos catro millóns de cousas? 559 00:23:28,190 --> 00:23:29,940 560 00:23:29,940 --> 00:23:30,455 Algún palpite? 561 00:23:30,455 --> 00:23:32,286 562 00:23:32,286 --> 00:23:33,960 É 32. 563 00:23:33,960 --> 00:23:37,110 32 pasos para atopar algo en catro millóns 564 00:23:37,110 --> 00:23:39,650 elemento da matriz por mor potencias de dous. 565 00:23:39,650 --> 00:23:43,550 Entón, dous é o 32, é de catro millóns. 566 00:23:43,550 --> 00:23:50,430 >> Así como moi tolo aínda está dentro como un relativamente pequeno número de pasos 567 00:23:50,430 --> 00:23:52,650 para atopar algo en catro millóns de elementos. 568 00:23:52,650 --> 00:23:55,730 Entón, nesa nota, estamos vai codificar iso 569 00:23:55,730 --> 00:23:58,950 para que vostedes poidan realmente tipo de ver como funciona isto. 570 00:23:58,950 --> 00:24:01,520 Todo ben, entón vostedes poden codificar. 571 00:24:01,520 --> 00:24:04,100 Vou deixar vós falar un pouco. 572 00:24:04,100 --> 00:24:07,970 Coñeza xente ao seu redor, o que é o que alguén quería da última sección. 573 00:24:07,970 --> 00:24:10,280 >> Entón, para coñecer a xente ao seu redor. 574 00:24:10,280 --> 00:24:11,305 Contacte un pouco. 575 00:24:11,305 --> 00:24:12,580 576 00:24:12,580 --> 00:24:15,730 E todo o que quero de ti caras agora é só 577 00:24:15,730 --> 00:24:17,575 intentar crear un esbozo de pseudocódigo. 578 00:24:17,575 --> 00:24:18,075 Ok? 579 00:24:18,075 --> 00:24:20,825 580 00:24:20,825 --> 00:24:21,325 Whoa. 581 00:24:21,325 --> 00:24:23,320 582 00:24:23,320 --> 00:24:29,520 Todo o que quero de vostedes é que está só vai cubrir neste caso agora. 583 00:24:29,520 --> 00:24:32,170 Entón, eu teño definir esas superior e límites inferiores que 584 00:24:32,170 --> 00:24:35,250 representan o inicio e ao final da nosa matriz. 585 00:24:35,250 --> 00:24:40,440 E vai, en realidade, loop través de e descubrir 586 00:24:40,440 --> 00:24:42,470 o que estamos facendo dentro deste loop while. 587 00:24:42,470 --> 00:24:45,810 >> Entón, se pode descubrir out-- teño unha información há-- cales son os casos 588 00:24:45,810 --> 00:24:46,640 que temos aquí? 589 00:24:46,640 --> 00:24:48,100 590 00:24:48,100 --> 00:24:51,560 Entón, se quere descubrir a casos, imos pseudocódigo aqueles 591 00:24:51,560 --> 00:24:53,350 e despois imos realmente codifica-las. 592 00:24:53,350 --> 00:24:55,330 E será, eu creo, espero que vai 593 00:24:55,330 --> 00:24:56,788 ser un pouco máis fácil do que espera. 594 00:24:56,788 --> 00:24:57,554 595 00:24:57,554 --> 00:25:00,220 ¿Por que non é que moito código, en realidade, o que é moi legal. 596 00:25:00,220 --> 00:25:34,110 597 00:25:34,110 --> 00:25:35,018 >> Mm-hm? 598 00:25:35,018 --> 00:25:35,893 >> Estudante: [inaudível]? 599 00:25:35,893 --> 00:25:36,984 600 00:25:36,984 --> 00:25:37,650 Instrutor: Si. 601 00:25:37,650 --> 00:25:38,595 Había algo para atopar no medio. 602 00:25:38,595 --> 00:25:39,552 >> ALUMNO: Así, podemos usar isto. 603 00:25:39,552 --> 00:25:39,770 Está ben. 604 00:25:39,770 --> 00:25:40,603 >> Instrutor: Perfecto. 605 00:25:40,603 --> 00:25:42,950 Entón esta é o primeiro que necesitamos facer. 606 00:25:42,950 --> 00:25:44,330 Entón, atopar o medio. 607 00:25:44,330 --> 00:25:45,415 608 00:25:45,415 --> 00:25:45,915 Grande. 609 00:25:45,915 --> 00:25:47,770 610 00:25:47,770 --> 00:25:55,010 Entón tes unha idea de como poderíamos realmente atopar o medio con código? 611 00:25:55,010 --> 00:25:55,980 >> Estudante: Si. 612 00:25:55,980 --> 00:25:57,000 n máis de 2? 613 00:25:57,000 --> 00:25:58,500 614 00:25:58,500 --> 00:25:59,500 Instrutor: Entón n máis de 2. 615 00:25:59,500 --> 00:26:05,170 Entón, unha cousa a lembrar que seus límites superiores e inferiores cambiar. 616 00:26:05,170 --> 00:26:08,110 Seguimos a constrição da parte da matriz nós estamos mirando para. 617 00:26:08,110 --> 00:26:11,970 Entón n máis de 2 só funcionará para o primeiro que facemos. 618 00:26:11,970 --> 00:26:17,810 Así, tendo superior e inferior en conta, como podemos obter ese elemento do medio? 619 00:26:17,810 --> 00:26:20,640 Porque queremos que a media entre superior e inferior, non? 620 00:26:20,640 --> 00:26:21,730 621 00:26:21,730 --> 00:26:22,494 Mm-hm? 622 00:26:22,494 --> 00:26:23,369 >> Estudante: [inaudível]. 623 00:26:23,369 --> 00:26:26,170 624 00:26:26,170 --> 00:26:28,080 >> Instrutor: Entón temos algún medio. 625 00:26:28,080 --> 00:26:32,730 E será superior máis baixa superior a 2. 626 00:26:32,730 --> 00:26:34,740 627 00:26:34,740 --> 00:26:35,690 Impresionante. 628 00:26:35,690 --> 00:26:36,570 Alí imos nós. 629 00:26:36,570 --> 00:26:37,280 Un abaixo da liña. 630 00:26:37,280 --> 00:26:38,560 Vostedes están no seu camiño. 631 00:26:38,560 --> 00:26:41,400 Polo tanto, agora que temos o noso medio, o que queremos facer? 632 00:26:41,400 --> 00:26:45,050 633 00:26:45,050 --> 00:26:45,900 Só en xeral. 634 00:26:45,900 --> 00:26:47,734 Non ten que codifica-lo. 635 00:26:47,734 --> 00:26:48,335 Si. 636 00:26:48,335 --> 00:26:49,210 Estudante: [inaudível]? 637 00:26:49,210 --> 00:27:00,310 638 00:27:00,310 --> 00:27:10,310 Instrutor: Entón é máis porque é pensando a media entre os dous 639 00:27:10,310 --> 00:27:10,810 deles. 640 00:27:10,810 --> 00:27:11,890 641 00:27:11,890 --> 00:27:17,370 Entón, se pensar neles como tipo de aumentar a partir dos lados, 642 00:27:17,370 --> 00:27:21,640 pensar sobre iso cando se achega no medio, quere así. 643 00:27:21,640 --> 00:27:27,150 Entón, se está en ambos os dous lados da medio, e temos como 5 e 7. 644 00:27:27,150 --> 00:27:31,440 Cando engade-los xuntos ti obter 12, ten divide por 2, é 6. 645 00:27:31,440 --> 00:27:33,726 >> Ás veces é difícil explicar por que funciona, 646 00:27:33,726 --> 00:27:35,600 pero se traballa con un exemplo, ás veces, 647 00:27:35,600 --> 00:27:37,962 vai axudar a descubrir se debe ser máis ou menos. 648 00:27:37,962 --> 00:27:38,846 Si. 649 00:27:38,846 --> 00:27:40,830 >> Estudante: [inaudível] exactamente no medio 650 00:27:40,830 --> 00:27:43,950 se tivesen un caso onde hai unha morea de números menores 651 00:27:43,950 --> 00:27:45,860 e como un número grande? 652 00:27:45,860 --> 00:27:49,750 >> Instrutor: Entón, todo o que precisa é o medio da matriz. 653 00:27:49,750 --> 00:27:53,010 Entón, se tiña unha morea de números pequenos e logo, un número moi grande 654 00:27:53,010 --> 00:27:54,799 ao final, non importa. 655 00:27:54,799 --> 00:27:56,840 Todo o que importa é que están clasificadas, só 656 00:27:56,840 --> 00:27:59,339 quero ollar para o medio do a matriz, porque aínda está 657 00:27:59,339 --> 00:28:00,700 fatiado o problema á metade. 658 00:28:00,700 --> 00:28:03,020 659 00:28:03,020 --> 00:28:03,680 Legal. 660 00:28:03,680 --> 00:28:06,430 Polo tanto, agora que temos a medio, o que imos facer a continuación? 661 00:28:06,430 --> 00:28:07,150 >> ALUMNO: Compare. 662 00:28:07,150 --> 00:28:08,150 Instrutor: The comparar. 663 00:28:08,150 --> 00:28:11,670 Entón, comparar a media value_wanted. 664 00:28:11,670 --> 00:28:14,300 665 00:28:14,300 --> 00:28:15,160 Legal. 666 00:28:15,160 --> 00:28:17,950 Entón ve aquí, temos este valor que queremos aquí. 667 00:28:17,950 --> 00:28:22,012 668 00:28:22,012 --> 00:28:23,095 Teña en conta que esta é unha matriz. 669 00:28:23,095 --> 00:28:24,100 670 00:28:24,100 --> 00:28:26,970 Así, refírese a media do índice. 671 00:28:26,970 --> 00:28:29,785 Por iso, queremos facer valores de media. 672 00:28:29,785 --> 00:28:32,380 673 00:28:32,380 --> 00:28:35,650 Non esqueza, se quere comparar, de dous iguais. 674 00:28:35,650 --> 00:28:38,250 Fai única igual a ti só vai trasladar-lo, 675 00:28:38,250 --> 00:28:41,090 e despois, por suposto, é será o valor que quere. 676 00:28:41,090 --> 00:28:42,300 Polo tanto, non fagas iso. 677 00:28:42,300 --> 00:28:44,350 >> Entón imos ver se os valores no medio 678 00:28:44,350 --> 00:28:46,460 é igual ao valor que queremos. 679 00:28:46,460 --> 00:28:47,749 680 00:28:47,749 --> 00:28:48,790 Non esqueza as súas claves. 681 00:28:48,790 --> 00:28:50,520 682 00:28:50,520 --> 00:28:52,235 Dropbox debe ir. 683 00:28:52,235 --> 00:28:54,140 684 00:28:54,140 --> 00:28:56,200 Entón, o que imos facer neste caso? 685 00:28:56,200 --> 00:28:59,360 Se é o que queremos para volver? 686 00:28:59,360 --> 00:29:01,510 687 00:29:01,510 --> 00:29:02,626 Estamos tentando dicir. 688 00:29:02,626 --> 00:29:03,440 >> ALUMNO: imprimir. 689 00:29:03,440 --> 00:29:05,314 >> Instrutor: Ben, nós Non quere imprimir. 690 00:29:05,314 --> 00:29:08,220 Polo tanto, este é un bool aquí, polo tanto, quere voltar verdadeiro ou falso. 691 00:29:08,220 --> 00:29:12,280 Estamos dicindo, é este número un [? RRA? ?] Entón, se é, 692 00:29:12,280 --> 00:29:13,788 nós simplemente devolve-lo verdadeiro. 693 00:29:13,788 --> 00:29:16,780 694 00:29:16,780 --> 00:29:17,760 Se podo soletrar verdade. 695 00:29:17,760 --> 00:29:18,830 696 00:29:18,830 --> 00:29:20,805 >> ALUMNO: Por que non voltar cero? 697 00:29:20,805 --> 00:29:22,930 Instrutor: Entón vostede podería voltar cero se quixese. 698 00:29:22,930 --> 00:29:26,780 Pero neste caso, porque nosa función devolve un bool, 699 00:29:26,780 --> 00:29:28,962 necesitamos volver verdadeira ou falsa. 700 00:29:28,962 --> 00:29:30,920 ALUMNO: Cando está dicindo expresión booleana, 701 00:29:30,920 --> 00:29:33,450 pode configurar-lo igual a teito? 702 00:29:33,450 --> 00:29:39,860 Como se eu quero dicir, se esta condición non se cumpre, como é superior é igual a falso. 703 00:29:39,860 --> 00:29:42,332 Será que vai entender se só poñer teito do outro lado? 704 00:29:42,332 --> 00:29:43,040 Instrutor: Yeah. 705 00:29:43,040 --> 00:29:44,820 Entón, en realidade, se está sempre facendo algo 706 00:29:44,820 --> 00:29:49,600 como é superior ou é menor, que retorna verdadeiro ou falso 707 00:29:49,600 --> 00:29:53,850 e é realmente un estilo malo para digamos igual a igual a true ou iguais 708 00:29:53,850 --> 00:29:54,840 é igual a falso. 709 00:29:54,840 --> 00:30:00,210 Quere usar este resultado como o propio como o seu cheque. 710 00:30:00,210 --> 00:30:04,720 711 00:30:04,720 --> 00:30:05,860 Non é o que eu quería. 712 00:30:05,860 --> 00:30:08,150 713 00:30:08,150 --> 00:30:09,240 Iso é o que eu quería. 714 00:30:09,240 --> 00:30:13,205 Así, no caso de que vostede está pedindo sobre algo como gardar isto en c. 715 00:30:13,205 --> 00:30:16,320 716 00:30:16,320 --> 00:30:25,150 >> Entón, se temos int main (void) e algo como isto. 717 00:30:25,150 --> 00:30:31,922 E ten, se é superior dalgunha entrada e está 718 00:30:31,922 --> 00:30:33,630 pregunta se pode facer algo coma isto? 719 00:30:33,630 --> 00:30:35,010 720 00:30:35,010 --> 00:30:35,679 Non? 721 00:30:35,679 --> 00:30:37,470 ESTUDANTE: Eu estaba tentando para facelo [inaudível]. 722 00:30:37,470 --> 00:30:38,450 Porque se it's-- 723 00:30:38,450 --> 00:30:39,200 Instrutor: Certo. 724 00:30:39,200 --> 00:30:41,197 Entón quere que isto sexa falso, non? 725 00:30:41,197 --> 00:30:41,780 Estudante: Si. 726 00:30:41,780 --> 00:30:45,960 Instrutor: Entón, nese caso quero que realice, se iso non é verdade. 727 00:30:45,960 --> 00:30:50,510 Entón, a cousa legal facer alí é esta. 728 00:30:50,510 --> 00:30:52,900 729 00:30:52,900 --> 00:30:55,650 Entón lembre de exclamación punto nega cousas? 730 00:30:55,650 --> 00:30:58,270 Di que [inaudível] non significa. 731 00:30:58,270 --> 00:31:03,590 Polo tanto, se miramos só esta parte aquí, 732 00:31:03,590 --> 00:31:05,740 din que avalía a falso como quere que el. 733 00:31:05,740 --> 00:31:06,790 734 00:31:06,790 --> 00:31:09,880 Non falsa é certo que significa que este sería executado. 735 00:31:09,880 --> 00:31:11,037 Será que isto ten sentido? 736 00:31:11,037 --> 00:31:11,620 Estudante: Si. 737 00:31:11,620 --> 00:31:12,453 Instrutor: Awesome. 738 00:31:12,453 --> 00:31:13,800 739 00:31:13,800 --> 00:31:14,300 Está ben. 740 00:31:14,300 --> 00:31:16,330 Entón, poderíamos só volver verdade neste caso. 741 00:31:16,330 --> 00:31:20,357 Polo tanto, agora temos dous outros casos neste caso. 742 00:31:20,357 --> 00:31:21,565 Cales son os nosos outros dous casos? 743 00:31:21,565 --> 00:31:31,610 744 00:31:31,610 --> 00:31:32,900 Nós só facelo deste xeito. 745 00:31:32,900 --> 00:31:40,660 Entón imos comezar con outra cousa se os valores no medio 746 00:31:40,660 --> 00:31:43,230 é menor que o valor que queremos. 747 00:31:43,230 --> 00:31:47,200 748 00:31:47,200 --> 00:31:52,020 Así, o noso valor no medio é menos que o valor que estamos a procurar. 749 00:31:52,020 --> 00:31:53,765 750 00:31:53,765 --> 00:31:56,720 >> Así que conectado ti creo que quere actualizar? 751 00:31:56,720 --> 00:31:57,870 752 00:31:57,870 --> 00:31:58,780 Superior ou inferior? 753 00:31:58,780 --> 00:32:01,440 754 00:32:01,440 --> 00:32:01,940 Superior? 755 00:32:01,940 --> 00:32:03,230 756 00:32:03,230 --> 00:32:06,470 Así que lado da matriz imos estar mirando? 757 00:32:06,470 --> 00:32:07,500 >> ALUMNO: A máis baixa. 758 00:32:07,500 --> 00:32:09,750 >> Instrutor: Estamos indo estar mirando cara á esquerda. 759 00:32:09,750 --> 00:32:11,120 Entón, algo pouco valor é menor. 760 00:32:11,120 --> 00:32:14,730 Polo tanto, o seu valor medio aquí é menor que o que queremos. 761 00:32:14,730 --> 00:32:17,202 Por iso, queremos levar o lado dereito da nosa matriz. 762 00:32:17,202 --> 00:32:18,910 Entón, nós estamos indo a actualizar o noso límite inferior. 763 00:32:18,910 --> 00:32:20,210 764 00:32:20,210 --> 00:32:23,020 Entón, imos transferir nosa inferior. 765 00:32:23,020 --> 00:32:25,221 E o que pensas que debe ser menor? 766 00:32:25,221 --> 00:32:26,304 ESTUDANTE: O valor medio? 767 00:32:26,304 --> 00:32:27,446 768 00:32:27,446 --> 00:32:28,820 Instrutor: Entón o value-- medio 769 00:32:28,820 --> 00:32:30,136 ALUMNO: Plus 1. 770 00:32:30,136 --> 00:32:31,010 Instrutor: --plus 1. 771 00:32:31,010 --> 00:32:32,300 772 00:32:32,300 --> 00:32:34,380 Alguén me pode dicir por que temos que unha? 773 00:32:34,380 --> 00:32:35,730 >> Estudante: [? Ningún valor?] é máis igual a el. 774 00:32:35,730 --> 00:32:36,120 >> Instrutor: Certo. 775 00:32:36,120 --> 00:32:38,661 Porque xa sabemos que noso valor medio non é igual a 776 00:32:38,661 --> 00:32:42,750 iso e queremos borrar-lo desde todas as investigacións posteriores. 777 00:32:42,750 --> 00:32:46,360 Se esquece de que máis 1, esta vai gusta de loop indefinidamente. 778 00:32:46,360 --> 00:32:49,620 E só vai ser pego nunha loop infinito e entón vai segfault 779 00:32:49,620 --> 00:32:50,370 e as cousas van mal. 780 00:32:50,370 --> 00:32:54,780 Entón, asegúrese de sempre que non está incluíndo o valor que acaba de 781 00:32:54,780 --> 00:32:55,380 mirou. 782 00:32:55,380 --> 00:32:58,530 Entón, nós coidamos que cun plus 1. 783 00:32:58,530 --> 00:33:04,840 >> Polo tanto, agora temos a nosa última condición que sempre por razóns de seguridade 784 00:33:04,840 --> 00:33:12,664 podes consultar aquí, máis se o valor en o medio é maior que o valor 785 00:33:12,664 --> 00:33:13,163 queremos. 786 00:33:13,163 --> 00:33:16,260 787 00:33:16,260 --> 00:33:20,230 Isto significa que queremos a metade do lado esquerdo. 788 00:33:20,230 --> 00:33:21,350 789 00:33:21,350 --> 00:33:23,260 Entón, cal deles é que imos actualizar? 790 00:33:23,260 --> 00:33:23,760 Superior. 791 00:33:23,760 --> 00:33:25,470 792 00:33:25,470 --> 00:33:26,970 E o que é este será igual? 793 00:33:26,970 --> 00:33:31,630 794 00:33:31,630 --> 00:33:33,690 Medio menos 1 porque, claro, que queremos 795 00:33:33,690 --> 00:33:38,370 para asegurarse de que non estamos mirando para o valor medio de novo. 796 00:33:38,370 --> 00:33:41,830 797 00:33:41,830 --> 00:33:45,110 E entón temos iso. 798 00:33:45,110 --> 00:33:45,610 É iso aí. 799 00:33:45,610 --> 00:33:46,820 Isto é todo de procura binaria é. 800 00:33:46,820 --> 00:33:48,190 Non é tan malo, non? 801 00:33:48,190 --> 00:33:51,590 É coma se 10 liñas de código con espazo en branco. 802 00:33:51,590 --> 00:33:57,510 Entón, moi poderoso, moi útil, vai estar a usalo nun dos seus Serie de exercicios posteriores. 803 00:33:57,510 --> 00:33:59,360 Quizais non este, pero máis tarde. 804 00:33:59,360 --> 00:34:00,670 Así, aprendela. 805 00:34:00,670 --> 00:34:01,510 Adoro. 806 00:34:01,510 --> 00:34:02,980 El vai te tratar ben. 807 00:34:02,980 --> 00:34:05,370 Entón, alguén ten algunha preguntas sobre procura binaria? 808 00:34:05,370 --> 00:34:06,196 Si. 809 00:34:06,196 --> 00:34:09,840 >> ALUMNO: Será que isto importa se o n é par ou impar? 810 00:34:09,840 --> 00:34:10,750 >> Instrutor: Non. 811 00:34:10,750 --> 00:34:18,150 Porque nós lanzalo ao medio como un int, ela só vai truncar-lo. 812 00:34:18,150 --> 00:34:21,600 Entón, que vai estar un enteiro e el vai finalmente clasificar a través de todo. 813 00:34:21,600 --> 00:34:23,909 Así que non se preocupe con iso. 814 00:34:23,909 --> 00:34:24,580 Todo o mundo bo? 815 00:34:24,580 --> 00:34:25,659 816 00:34:25,659 --> 00:34:26,850 Impresionante. 817 00:34:26,850 --> 00:34:27,919 Legal. 818 00:34:27,919 --> 00:34:30,836 Entón, vós ten iso. 819 00:34:30,836 --> 00:34:33,380 820 00:34:33,380 --> 00:34:33,880 Presentación. 821 00:34:33,880 --> 00:34:35,719 822 00:34:35,719 --> 00:34:43,270 Así como estabamos falando, sei David mencionou tempos de execución de complexidade. 823 00:34:43,270 --> 00:34:44,420 824 00:34:44,420 --> 00:34:50,340 >> Así, no mellor dos casos, é só un, o que chamamos tempo constante. 825 00:34:50,340 --> 00:34:51,909 Alguén me pode dicir por que isto pode ser? 826 00:34:51,909 --> 00:34:52,969 827 00:34:52,969 --> 00:34:55,800 Que tipo de escenario que iso implica? 828 00:34:55,800 --> 00:34:58,260 829 00:34:58,260 --> 00:34:58,760 Mm-hm. 830 00:34:58,760 --> 00:34:59,926 >> Estudante: [inaudível] first-- 831 00:34:59,926 --> 00:35:00,789 832 00:35:00,789 --> 00:35:03,830 Instrutor: Entón no medio sendo o primeiro elemento que vén, non? 833 00:35:03,830 --> 00:35:08,167 Así, é un conxunto dun ou todo o que está a buscar só 834 00:35:08,167 --> 00:35:09,750 pasa a ser ben no medio. 835 00:35:09,750 --> 00:35:11,190 836 00:35:11,190 --> 00:35:13,380 Entón, esa é a nosa mellor caso. 837 00:35:13,380 --> 00:35:17,540 Comeza en problemas reais, probablemente non chegará [inaudível] que moitas veces. 838 00:35:17,540 --> 00:35:18,667 839 00:35:18,667 --> 00:35:19,750 E o noso peor caso? 840 00:35:19,750 --> 00:35:21,270 O noso peor caso é log n. 841 00:35:21,270 --> 00:35:25,360 E isto ten que ver co todo potencias de dous cousa que eu falei. 842 00:35:25,360 --> 00:35:30,930 >> Así, no peor caso, iso significaría que tivemos de cortar a matriz abaixo 843 00:35:30,930 --> 00:35:33,270 ata que era un elemento dun. 844 00:35:33,270 --> 00:35:34,810 845 00:35:34,810 --> 00:35:38,930 Entón tivemos que corte-la pola metade tantas veces como nós podía. 846 00:35:38,930 --> 00:35:41,430 É por iso que é log n porque vostede segue dividindo por dous. 847 00:35:41,430 --> 00:35:42,890 848 00:35:42,890 --> 00:35:45,830 Así presupostos, cousas que Necesito saber se está sempre 849 00:35:45,830 --> 00:35:48,050 vai usar unha busca binaria. 850 00:35:48,050 --> 00:35:50,680 Os seus elementos deben ser ordenados. 851 00:35:50,680 --> 00:35:53,890 Eles teñen que ser resoltas, porque esta é a única forma que 852 00:35:53,890 --> 00:35:57,060 pode saber se é capaz para xogar fóra metade. 853 00:35:57,060 --> 00:36:00,260 >> Se tivese esta bolsa confusa de números e está dicindo, 854 00:36:00,260 --> 00:36:05,380 OK, eu vou comprobar o medio número eo número que eu estou buscando 855 00:36:05,380 --> 00:36:08,510 é menos que iso, eu só vou para lanzar arbitrariamente fóra metade. 856 00:36:08,510 --> 00:36:11,130 Non sabe se o os números en que a outra metade. 857 00:36:11,130 --> 00:36:12,655 A súa lista debe ser resolta. 858 00:36:12,655 --> 00:36:14,030 859 00:36:14,030 --> 00:36:16,560 Así, este pode ser indo adiante un pouco, 860 00:36:16,560 --> 00:36:18,360 pero ten que ter acceso aleatorio. 861 00:36:18,360 --> 00:36:21,940 Debe ser capaz de só ir aquel elemento do medio. 862 00:36:21,940 --> 00:36:25,110 Se ten que atravesar por algo 863 00:36:25,110 --> 00:36:28,630 ou leva etapas extra para chegar a ese elemento do medio, 864 00:36:28,630 --> 00:36:31,750 non se log n máis porque está engadindo máis traballo para el. 865 00:36:31,750 --> 00:36:34,800 E iso vai facer un pouco de máis sentido en dúas semanas, 866 00:36:34,800 --> 00:36:37,950 pero eu medio que quería prefacio, dar a vostedes unha idea do que é 867 00:36:37,950 --> 00:36:38,999 para vir. 868 00:36:38,999 --> 00:36:40,790 Pero estes son os dous premisas importantes 869 00:36:40,790 --> 00:36:44,804 que precisa para unha lista de binario. 870 00:36:44,804 --> 00:36:45,720 Asegúrese de que está clasificado. 871 00:36:45,720 --> 00:36:47,920 Ese é o gran problema para vostedes agora mesmo. 872 00:36:47,920 --> 00:36:52,170 E no que podemos entrar en o resto das nosas sortes. 873 00:36:52,170 --> 00:36:56,444 Entón, catro burbulla sorts--, inserción, selección e merge. 874 00:36:56,444 --> 00:36:57,485 Están todos ben legal. 875 00:36:57,485 --> 00:37:02,860 Se vostedes deciden tomar CS 124, vai aprender sobre todo tipo de tipos. 876 00:37:02,860 --> 00:37:07,575 E se é un fan xkcd, non é un sobre cómics moi legal 877 00:37:07,575 --> 00:37:11,530 como tipo realmente ineficaces, o que eu recomendo que vai mirar. 878 00:37:11,530 --> 00:37:16,170 Un deles é como especie de pánico, que é como, oh non, regresar disposición aleatoria. 879 00:37:16,170 --> 00:37:16,991 Sistema de apagado. 880 00:37:16,991 --> 00:37:17,490 Deixar. 881 00:37:17,490 --> 00:37:19,070 882 00:37:19,070 --> 00:37:21,500 Entón, humor geeky é sempre bo. 883 00:37:21,500 --> 00:37:22,620 884 00:37:22,620 --> 00:37:25,750 >> Entón, alguén recorda tipo de como só unha idea xeral 885 00:37:25,750 --> 00:37:27,810 de como bubble sort funciona. 886 00:37:27,810 --> 00:37:31,130 887 00:37:31,130 --> 00:37:32,155 Vostede recorda? 888 00:37:32,155 --> 00:37:32,755 >> Estudante: Si. 889 00:37:32,755 --> 00:37:33,970 >> Instrutor: Dalle. 890 00:37:33,970 --> 00:37:38,980 >> Estudante: Entón está pasando e se é o máis grande, entón cambiar os dous. 891 00:37:38,980 --> 00:37:39,820 >> Instrutor: Mm-hm. 892 00:37:39,820 --> 00:37:40,564 Exactamente. 893 00:37:40,564 --> 00:37:41,730 Entón só iterado. 894 00:37:41,730 --> 00:37:43,050 Vostede verifica dous números. 895 00:37:43,050 --> 00:37:46,510 Se o anterior é maior despois do que aquel, 896 00:37:46,510 --> 00:37:50,230 só trocalos de forma que en Deste xeito, todos os números máis altos 897 00:37:50,230 --> 00:37:54,990 burbulla-se a fin da lista e todos os números máis baixos burbulla abaixo. 898 00:37:54,990 --> 00:37:59,355 >> Será que amosar a vostedes o frío efecto sonoro selección vídeo? 899 00:37:59,355 --> 00:38:00,480 É ben legal. 900 00:38:00,480 --> 00:38:01,510 901 00:38:01,510 --> 00:38:05,200 Así como Robert dixo, o algoritmo que acaba de percorrer a lista, 902 00:38:05,200 --> 00:38:07,930 cambiando os valores adxacentes se eles non están en orde. 903 00:38:07,930 --> 00:38:10,975 E despois é só ir repetindo ata que non faga ningunha swaps. 904 00:38:10,975 --> 00:38:11,990 905 00:38:11,990 --> 00:38:12,740 Entón, non é malo, non? 906 00:38:12,740 --> 00:38:14,080 907 00:38:14,080 --> 00:38:16,319 Entón, só temos un exemplo rápido aquí. 908 00:38:16,319 --> 00:38:18,360 Entón, iso vai clasificar los en orde crecente. 909 00:38:18,360 --> 00:38:19,470 910 00:38:19,470 --> 00:38:23,470 Entón, cando nós pasamos a primeira tempo, miramos a oito 911 00:38:23,470 --> 00:38:26,880 e seis non son, obviamente, en orde, nós trocalos. 912 00:38:26,880 --> 00:38:27,985 >> Entón mire para a próxima. 913 00:38:27,985 --> 00:38:29,430 Oito e catro non en orde. 914 00:38:29,430 --> 00:38:30,450 Trocalos. 915 00:38:30,450 --> 00:38:32,530 E despois de oito e dous, trocalos. 916 00:38:32,530 --> 00:38:33,470 Alí imos nós. 917 00:38:33,470 --> 00:38:39,519 Entón, despois de súa primeira pasaxe, vostede sabe que o seu maior número 918 00:38:39,519 --> 00:38:41,810 será todo o camiño na parte superior, porque é só 919 00:38:41,810 --> 00:38:44,210 será constantemente maior que o resto 920 00:38:44,210 --> 00:38:46,810 e el só vai para burbulla ata todo o camiño ata a final alí. 921 00:38:46,810 --> 00:38:48,226 Será que isto ten sentido para todos? 922 00:38:48,226 --> 00:38:48,560 923 00:38:48,560 --> 00:38:49,060 Legal. 924 00:38:49,060 --> 00:38:51,310 925 00:38:51,310 --> 00:38:53,920 >> Entón miramos para a nosa segunda pasaxe. 926 00:38:53,920 --> 00:38:54,980 Seis e catro, interruptor. 927 00:38:54,980 --> 00:38:55,920 Seis e dous, switch. 928 00:38:55,920 --> 00:38:58,700 E agora temos algunhas cousas en orde. 929 00:38:58,700 --> 00:39:02,240 Así, para cada paso que facer a través da nosa lista enteira, 930 00:39:02,240 --> 00:39:06,320 sabemos que como que moitos números ao final foi clasificados. 931 00:39:06,320 --> 00:39:07,690 932 00:39:07,690 --> 00:39:09,610 Entón nós facemos unha terceira paso, que é un intercambio. 933 00:39:09,610 --> 00:39:10,860 934 00:39:10,860 --> 00:39:15,910 E, a continuación, na nosa cuarta pasar, temos cero slots. 935 00:39:15,910 --> 00:39:18,570 E así sabemos que a nosa matriz ten sido resolto. 936 00:39:18,570 --> 00:39:20,900 >> E esa é a gran cousa con bubble sort. 937 00:39:20,900 --> 00:39:23,720 Sabemos que cando nós ter cero swaps, que 938 00:39:23,720 --> 00:39:26,497 significa que todo está en orde completa. 939 00:39:26,497 --> 00:39:27,580 É unha especie de como podemos comprobar. 940 00:39:27,580 --> 00:39:28,740 941 00:39:28,740 --> 00:39:36,480 Entón, nós tamén estamos indo a codificar burbulla tipo o que tampouco é tan malo así. 942 00:39:36,480 --> 00:39:38,120 Ningún destes son tan malas. 943 00:39:38,120 --> 00:39:40,210 Sei que pode parecer un pouco asustado. 944 00:39:40,210 --> 00:39:42,124 Sei que cando eu tirei a clase, mesmo cando 945 00:39:42,124 --> 00:39:44,290 estaba ensinando a clase para Por primeira vez o ano pasado, 946 00:39:44,290 --> 00:39:46,165 Estaba tipo, como fago isto? 947 00:39:46,165 --> 00:39:48,540 Ten sentido na teoría, pero como é que imos realmente facer iso? 948 00:39:48,540 --> 00:39:51,420 É por iso que eu tamén quero andar por medio de código convosco aquí. 949 00:39:51,420 --> 00:39:54,915 Entón, eu teño un pseudocódigo para vós neste momento. 950 00:39:54,915 --> 00:39:55,950 951 00:39:55,950 --> 00:39:58,970 Entón, só tes que manter isto presente como estamos a piques de facer a transición máis. 952 00:39:58,970 --> 00:40:04,210 Polo tanto, temos algúns contador que mantén o control dos nosos swaps, 953 00:40:04,210 --> 00:40:08,370 porque necesitamos ter seguro de que estamos comprobando iso. 954 00:40:08,370 --> 00:40:11,830 E iteramos toda a matriz como acabamos de facer con este exemplo. 955 00:40:11,830 --> 00:40:12,900 956 00:40:12,900 --> 00:40:17,325 Se o elemento é maior que antes o elemento despois de onde estamos, 957 00:40:17,325 --> 00:40:20,760 nós trocalos e incrementamos a nosa contador, porque así que cambiar, 958 00:40:20,760 --> 00:40:23,850 queremos deixar o noso contador de saber diso. 959 00:40:23,850 --> 00:40:26,247 Calquera dúbida alí? 960 00:40:26,247 --> 00:40:27,580 Algo parece divertido aquí. 961 00:40:27,580 --> 00:40:29,225 962 00:40:29,225 --> 00:40:32,350 ALUMNO: Vostede poñer o contador a cero cada vez que pasar polo loop? 963 00:40:32,350 --> 00:40:34,339 Non vai manter de volta a cero cada vez? 964 00:40:34,339 --> 00:40:35,505 Instrutor: Non necesariamente. 965 00:40:35,505 --> 00:40:39,710 Entón, o que pasa é que pasamos aquí. 966 00:40:39,710 --> 00:40:43,830 Entón faga agora, lembre, este executarase unha vez, sen falla. 967 00:40:43,830 --> 00:40:46,480 Entón vai establecer o contador igual a cero, 968 00:40:46,480 --> 00:40:48,070 logo vai para percorrer. 969 00:40:48,070 --> 00:40:50,590 Como se repite a través de, ha actualizar balcón. 970 00:40:50,590 --> 00:40:51,870 971 00:40:51,870 --> 00:40:56,900 Como el actualiza balcón cando está feito, cando é acadar o final da matriz, 972 00:40:56,900 --> 00:41:00,830 se a nosa lista non fose resolto, contador foron actualizados. 973 00:41:00,830 --> 00:41:01,840 974 00:41:01,840 --> 00:41:07,150 >> El verifica o estado de conservación e di, OK, é contador maior que cero. 975 00:41:07,150 --> 00:41:09,290 De ser isto, facelo de novo. 976 00:41:09,290 --> 00:41:14,340 Desexa reiniciar para que cando percorrer, contador é igual a cero. 977 00:41:14,340 --> 00:41:18,240 Se pasar por unha ordenada array, nada cambia, 978 00:41:18,240 --> 00:41:21,355 isto falla, e volver á lista ordenada. 979 00:41:21,355 --> 00:41:23,104 980 00:41:23,104 --> 00:41:24,020 Será que isto ten sentido? 981 00:41:24,020 --> 00:41:24,940 982 00:41:24,940 --> 00:41:26,356 Estudante: Podería un pouco. 983 00:41:26,356 --> 00:41:27,147 Instrutor: Aceptar. 984 00:41:27,147 --> 00:41:28,980 Se hai calquera outra cuestión que vén á tona. 985 00:41:28,980 --> 00:41:30,180 986 00:41:30,180 --> 00:41:30,680 Si. 987 00:41:30,680 --> 00:41:33,760 >> Estudante: Cal sería a función ser para cambiar os elementos? 988 00:41:33,760 --> 00:41:36,900 >> Instrutor: Entón podemos realmente escribir que, se nós estamos indo agora. 989 00:41:36,900 --> 00:41:37,801 990 00:41:37,801 --> 00:41:38,300 Legal. 991 00:41:38,300 --> 00:41:42,155 Entón, nesa nota, Alison vai para volver para o aparello. 992 00:41:42,155 --> 00:41:43,080 Vai ser divertido. 993 00:41:43,080 --> 00:41:45,170 994 00:41:45,170 --> 00:41:47,390 E nós temos o noso bo burbulla cousa tipo aquí. 995 00:41:47,390 --> 00:41:50,800 Entón, eu xa fixen ciclismo a través da matriz. 996 00:41:50,800 --> 00:41:53,030 Temos os nosos swaps que son iguais a cero. 997 00:41:53,030 --> 00:41:54,480 998 00:41:54,480 --> 00:41:58,440 Por iso, queremos cambiar adxacente elementos se eles están fóra de orde. 999 00:41:58,440 --> 00:42:03,020 Entón, o primeiro que necesitamos non é iterado nosa matriz. 1000 00:42:03,020 --> 00:42:04,500 1001 00:42:04,500 --> 00:42:08,260 >> Entón, como pensas que pode iterado nosa matriz? 1002 00:42:08,260 --> 00:42:09,720 1003 00:42:09,720 --> 00:42:13,990 Temos para e i é igual a 0. 1004 00:42:13,990 --> 00:42:16,950 1005 00:42:16,950 --> 00:42:22,454 Queremos i a ser menos que n menos 1 menos k. 1006 00:42:22,454 --> 00:42:23,870 E eu vou explicar isto nun segundo. 1007 00:42:23,870 --> 00:42:26,280 1008 00:42:26,280 --> 00:42:32,830 Polo tanto, esta é unha optimización aquí, onde, recordo como dixen despois de cada paso 1009 00:42:32,830 --> 00:42:36,655 a través da matriz de nós sei que todo o que é on-- 1010 00:42:36,655 --> 00:42:43,590 1011 00:42:43,590 --> 00:42:46,295 >> Entón, despois dun pase de nós sabemos que este é clasificado. 1012 00:42:46,295 --> 00:42:47,370 1013 00:42:47,370 --> 00:42:50,060 Tras dous pases sabemos que todo isto está clasificada. 1014 00:42:50,060 --> 00:42:52,750 Despois de tres pasaxes de nós sei que é clasificada. 1015 00:42:52,750 --> 00:42:55,620 Así, a forma que eu estou interactuar a través da matriz aquí, 1016 00:42:55,620 --> 00:43:01,090 se está asegurarse de ir só a través do que se sabe é indiferenciado. 1017 00:43:01,090 --> 00:43:01,644 Ok? 1018 00:43:01,644 --> 00:43:02,810 Isto é só unha optimización. 1019 00:43:02,810 --> 00:43:04,430 1020 00:43:04,430 --> 00:43:08,210 Pode escribir-lo só inxenuamente iteración través de todo, 1021 00:43:08,210 --> 00:43:09,970 sería só levar máis tempo. 1022 00:43:09,970 --> 00:43:12,470 Con este ciclo de catro é só unha boa optimización 1023 00:43:12,470 --> 00:43:18,460 porque sabemos que despois de cada chea iteración través da matriz aquí, 1024 00:43:18,460 --> 00:43:24,050 como cada ciclo completo aquí, sabemos que un máis destes elementos 1025 00:43:24,050 --> 00:43:25,760 serán clasificados ao final. 1026 00:43:25,760 --> 00:43:28,294 >> Polo tanto, non se preocupe con aqueles. 1027 00:43:28,294 --> 00:43:29,710 Será que isto ten sentido para todos? 1028 00:43:29,710 --> 00:43:30,950 Ese truco pouco fría? 1029 00:43:30,950 --> 00:43:32,060 1030 00:43:32,060 --> 00:43:37,270 Entón, nese caso, se estamos interactuar a través, 1031 00:43:37,270 --> 00:43:50,590 sabemos que queremos comprobar se matriz n e n + 1 están en orde. 1032 00:43:50,590 --> 00:43:52,640 1033 00:43:52,640 --> 00:43:53,559 Está ben. 1034 00:43:53,559 --> 00:43:54,600 Entón aquí está o pseudocódigo. 1035 00:43:54,600 --> 00:43:57,540 Queremos comprobar se a matriz n e n máis 1 están en orde. 1036 00:43:57,540 --> 00:43:59,520 Entón, o que podemos ter aí? 1037 00:43:59,520 --> 00:44:01,090 1038 00:44:01,090 --> 00:44:03,120 Vai ser unha condicional. 1039 00:44:03,120 --> 00:44:04,220 Será un caso. 1040 00:44:04,220 --> 00:44:07,066 >> ALUMNO: Se array n é inferior a matriz n máis 1. 1041 00:44:07,066 --> 00:44:07,816 Instrutor: Mm-hm. 1042 00:44:07,816 --> 00:44:09,000 1043 00:44:09,000 --> 00:44:10,699 Ben, máis ou menos. 1044 00:44:10,699 --> 00:44:11,615 ALUMNO: Maior que. 1045 00:44:11,615 --> 00:44:15,850 1046 00:44:15,850 --> 00:44:17,620 Entón eu quero trocalos. 1047 00:44:17,620 --> 00:44:18,570 Exactamente. 1048 00:44:18,570 --> 00:44:23,570 Polo tanto, agora entramos en cal é a mecanismo de intercambio-los? 1049 00:44:23,570 --> 00:44:24,840 1050 00:44:24,840 --> 00:44:28,137 Entón nós pasamos por iso brevemente, un tipo de función de intercambio a semana pasada. 1051 00:44:28,137 --> 00:44:29,595 Alguén recorda como funcionaba? 1052 00:44:29,595 --> 00:44:32,300 1053 00:44:32,300 --> 00:44:34,950 Polo tanto, non podemos só reenvía-los, non? 1054 00:44:34,950 --> 00:44:36,640 Porque un deles vai perder. 1055 00:44:36,640 --> 00:44:41,696 Se dixésemos A é igual a B e despois B é igual a A, toda unha súbita tanto 1056 00:44:41,696 --> 00:44:43,150 son só igual a B. 1057 00:44:43,150 --> 00:44:45,720 >> Entón o que temos que facer é que ten unha variable temporal que é 1058 00:44:45,720 --> 00:44:49,055 vai realizar un dos nosos mentres estamos no proceso de cambio. 1059 00:44:49,055 --> 00:44:50,200 1060 00:44:50,200 --> 00:44:56,464 Entón, o que temos é que imos ter algúns int temperatura é igual a-- pode atribuílo lo 1061 00:44:56,464 --> 00:44:59,130 para calquera que quere, simplemente asegúrese de manter o control de ele-- 1062 00:44:59,130 --> 00:45:01,840 polo tanto, neste caso, eu vou atribuílo la a matriz n + 1. 1063 00:45:01,840 --> 00:45:03,360 1064 00:45:03,360 --> 00:45:07,674 Entón, iso vai soster o que quere valor é ese segundo bloque 1065 00:45:07,674 --> 00:45:08,590 que estamos mirando. 1066 00:45:08,590 --> 00:45:09,700 1067 00:45:09,700 --> 00:45:13,240 >> E entón o que podemos facer é que podemos ir adiante e variedade Reassign n + 1, 1068 00:45:13,240 --> 00:45:14,990 porque sabemos que que teñen valor almacenado. 1069 00:45:14,990 --> 00:45:16,645 1070 00:45:16,645 --> 00:45:19,270 Este é tamén un dos grandes coisas- Non sei se algún de vós 1071 00:45:19,270 --> 00:45:23,780 tivemos problemas onde se alternan dous liñas de código, de súpeto as cousas funcionaban. 1072 00:45:23,780 --> 00:45:25,880 Orde é moi importante no CS. 1073 00:45:25,880 --> 00:45:29,450 Entón, asegúrese de diagrama cousas, se é posible 1074 00:45:29,450 --> 00:45:31,230 sobre o que está realmente a suceder. 1075 00:45:31,230 --> 00:45:34,256 Entón agora nós imos reatribuído array n + 1, 1076 00:45:34,256 --> 00:45:36,005 porque sabemos que que teñen valor almacenado. 1077 00:45:36,005 --> 00:45:37,090 1078 00:45:37,090 --> 00:45:41,560 >> E podemos asignar iso a matriz n ou neste caso variedade i. 1079 00:45:41,560 --> 00:45:50,540 1080 00:45:50,540 --> 00:45:51,465 Moitas variables. 1081 00:45:51,465 --> 00:45:54,230 1082 00:45:54,230 --> 00:45:55,470 Está ben. 1083 00:45:55,470 --> 00:46:01,500 Matriz Entón agora temos trasladado i máis un para igualar o que está na matriz i. 1084 00:46:01,500 --> 00:46:08,240 E agora podemos volver e asignar gama i co que? 1085 00:46:08,240 --> 00:46:10,680 1086 00:46:10,680 --> 00:46:11,180 Calquera? 1087 00:46:11,180 --> 00:46:13,490 1088 00:46:13,490 --> 00:46:14,010 >> Estudante: 10. 1089 00:46:14,010 --> 00:46:14,680 >> Instrutor: 10. 1090 00:46:14,680 --> 00:46:15,180 Exactamente. 1091 00:46:15,180 --> 00:46:16,930 1092 00:46:16,930 --> 00:46:18,640 E unha última cousa. 1093 00:46:18,640 --> 00:46:21,840 Se temos trocado agora, o que necesitamos facer? 1094 00:46:21,840 --> 00:46:23,740 Que é o único que vai dicir 1095 00:46:23,740 --> 00:46:27,542 se algunha vez rematar este programa? 1096 00:46:27,542 --> 00:46:29,250 O que nos di que ten unha lista ordenada? 1097 00:46:29,250 --> 00:46:31,560 1098 00:46:31,560 --> 00:46:33,750 Se non executar calquera swaps, non? 1099 00:46:33,750 --> 00:46:36,900 Se permutas é igual de cero ao final desta. 1100 00:46:36,900 --> 00:46:42,975 Así, sempre que realizar un intercambio, como nós só fixen aquí, queremos actualizar swaps. 1101 00:46:42,975 --> 00:46:45,002 1102 00:46:45,002 --> 00:46:47,210 E sei que houbo unha pregunta anterior sobre se poida 1103 00:46:47,210 --> 00:46:49,689 usar cero ou un, en vez de verdadeiro ou falso. 1104 00:46:49,689 --> 00:46:50,980 E iso é o que iso fai aquí. 1105 00:46:50,980 --> 00:46:52,750 Polo tanto, este di que se non swaps. 1106 00:46:52,750 --> 00:47:01,310 Polo tanto, se permutas é cero, o que eu é-- sempre chegar en miñas verdades e os meus falsos mesturados. 1107 00:47:01,310 --> 00:47:03,960 Queremos nos avaliar a verdade e non é. 1108 00:47:03,960 --> 00:47:07,680 1109 00:47:07,680 --> 00:47:09,630 Entón, se é cero, entón é falsa. 1110 00:47:09,630 --> 00:47:12,560 Negarse o con un [? bater?] convértese en verdade. 1111 00:47:12,560 --> 00:47:13,975 Entón esta liña executa. 1112 00:47:13,975 --> 00:47:15,060 1113 00:47:15,060 --> 00:47:17,370 >> Verdades e falsas e ceros e uns estar tolo. 1114 00:47:17,370 --> 00:47:20,690 Así, se andar a modo por iso que vai ter sentido. 1115 00:47:20,690 --> 00:47:23,320 Pero iso é o que este pequeno pouco de código aquí fai. 1116 00:47:23,320 --> 00:47:26,490 Polo tanto, este verifica fixemos os swaps. 1117 00:47:26,490 --> 00:47:30,054 Entón, se é somente cero, que será falsa 1118 00:47:30,054 --> 00:47:31,970 e toda a cousa é indo para executar de novo. 1119 00:47:31,970 --> 00:47:33,150 1120 00:47:33,150 --> 00:47:33,650 Legal? 1121 00:47:33,650 --> 00:47:34,660 1122 00:47:34,660 --> 00:47:36,000 >> Estudante: Que fai pausa facer? 1123 00:47:36,000 --> 00:47:38,990 >> Instrutor: Rompe só rompe-lo fóra do loop. 1124 00:47:38,990 --> 00:47:41,570 Polo tanto, neste caso, sería así como acabar co programa 1125 00:47:41,570 --> 00:47:43,828 e que tería só ten a súa lista clasificada. 1126 00:47:43,828 --> 00:47:44,536 ESTUDANTE: Amazing. 1127 00:47:44,536 --> 00:47:48,094 1128 00:47:48,094 --> 00:47:49,010 Instrutor: Eu sinto moito? 1129 00:47:49,010 --> 00:47:52,110 ESTUDANTE: Como previamente usado por escrito sobre un escrito de cero 1130 00:47:52,110 --> 00:47:54,170 presentar que si que vai funcionar ou non. 1131 00:47:54,170 --> 00:47:54,878 >> Instrutor: Yeah. 1132 00:47:54,878 --> 00:47:56,410 Así, pode voltar cero ou un. 1133 00:47:56,410 --> 00:47:58,950 Neste caso, por que non estamos realmente facer algo coa función, 1134 00:47:58,950 --> 00:48:00,150 nós só queremos que rompe. 1135 00:48:00,150 --> 00:48:02,680 Nós realmente non se preocupan con iso. 1136 00:48:02,680 --> 00:48:06,960 Brake tamén é bo se se usa para saír 1137 00:48:06,960 --> 00:48:10,710 de catro lacetes ou condicións que non quere manter a execución. 1138 00:48:10,710 --> 00:48:12,110 El só leva a fóra deles. 1139 00:48:12,110 --> 00:48:13,587 1140 00:48:13,587 --> 00:48:14,795 É un pouco dunha cousa matices. 1141 00:48:14,795 --> 00:48:16,737 1142 00:48:16,737 --> 00:48:18,445 Eu sinto que hai unha gran cantidade de man de ondas, 1143 00:48:18,445 --> 00:48:19,740 como vai aprender sobre iso en breve. 1144 00:48:19,740 --> 00:48:20,955 >> Pero vai aprender sobre iso en breve. 1145 00:48:20,955 --> 00:48:21,500 Eu prometer. 1146 00:48:21,500 --> 00:48:22,670 1147 00:48:22,670 --> 00:48:23,170 Está ben. 1148 00:48:23,170 --> 00:48:24,840 Así que todos obter bubble sort? 1149 00:48:24,840 --> 00:48:25,550 Non é tan malo. 1150 00:48:25,550 --> 00:48:31,910 Iterado, cousas de intercambio, utilizando unha variable temp, e que está todo listo alí? 1151 00:48:31,910 --> 00:48:32,960 Legal. 1152 00:48:32,960 --> 00:48:34,080 Impresionante. 1153 00:48:34,080 --> 00:48:34,807 Está ben. 1154 00:48:34,807 --> 00:48:35,765 Volver ao PowerPoint. 1155 00:48:35,765 --> 00:48:38,140 1156 00:48:38,140 --> 00:48:40,130 Calquera dúbida en xeral sobre estes ata agora? 1157 00:48:40,130 --> 00:48:41,200 1158 00:48:41,200 --> 00:48:41,700 Legal. 1159 00:48:41,700 --> 00:48:43,110 1160 00:48:43,110 --> 00:48:43,695 Mm-hm. 1161 00:48:43,695 --> 00:48:45,279 >> Estudante: [inaudível] int main normalmente. 1162 00:48:45,279 --> 00:48:46,695 Ten que ter que para iso? 1163 00:48:46,695 --> 00:48:48,400 1164 00:48:48,400 --> 00:48:53,550 >> Instrutor: Entón, nós só buscar só no algoritmo de ordenación real. 1165 00:48:53,550 --> 00:48:54,559 1166 00:48:54,559 --> 00:48:56,350 Se tivese que dentro como un programa máis grande, 1167 00:48:56,350 --> 00:48:57,891 que tería un lugar principal int. 1168 00:48:57,891 --> 00:49:00,070 1169 00:49:00,070 --> 00:49:02,880 Dependendo de onde vostede usar este algoritmo, 1170 00:49:02,880 --> 00:49:05,860 sería determinar o que é sendo devolto por ela. 1171 00:49:05,860 --> 00:49:09,960 Pero, para o noso caso, estamos estrictamente mirando como fai iso, en realidade, 1172 00:49:09,960 --> 00:49:11,300 iterado través dun array. 1173 00:49:11,300 --> 00:49:12,570 Polo tanto, non se preocupe con iso. 1174 00:49:12,570 --> 00:49:14,150 1175 00:49:14,150 --> 00:49:19,830 >> Entón, nós estabamos falando sobre mellor caso e os peores escenarios de busca binaria. 1176 00:49:19,830 --> 00:49:22,470 Por iso, é tamén importante facer que, para cada un dos nosos tipos. 1177 00:49:22,470 --> 00:49:24,200 1178 00:49:24,200 --> 00:49:27,560 Entón, o que pensas que é o peor caso de execución de bubble sort? 1179 00:49:27,560 --> 00:49:29,560 1180 00:49:29,560 --> 00:49:30,700 Vostedes lembran-se? 1181 00:49:30,700 --> 00:49:31,784 >> ALUMNO: N menos 1. 1182 00:49:31,784 --> 00:49:32,700 Instrutor: N menos 1. 1183 00:49:32,700 --> 00:49:35,070 Entón isto significa que hai n menos 1 comparacións. 1184 00:49:35,070 --> 00:49:40,060 Entón, unha cousa a entender é que na primeira iteración, 1185 00:49:40,060 --> 00:49:43,360 que pasamos, nós comparamos estes dois-- de xeito que é un. 1186 00:49:43,360 --> 00:49:46,685 Estes dous, tres, catro. 1187 00:49:46,685 --> 00:49:48,070 1188 00:49:48,070 --> 00:49:55,050 Entón, despois de unha iteración nós xa ten catro comparacións. 1189 00:49:55,050 --> 00:49:58,230 Cando eu estou falando de tempo de execución e n. 1190 00:49:58,230 --> 00:50:04,680 N representa o número de comparacións como unha función de cantos elementos 1191 00:50:04,680 --> 00:50:05,570 temos. 1192 00:50:05,570 --> 00:50:06,430 Ok? 1193 00:50:06,430 --> 00:50:08,860 >> Así que pasamos, temos catro. 1194 00:50:08,860 --> 00:50:11,780 A próxima vez que vostede sabe que non facer ten que coidar do presente. 1195 00:50:11,780 --> 00:50:15,140 Nós comparamos os dous, estes dous, estes dous, 1196 00:50:15,140 --> 00:50:20,050 e se non tivésemos que a optimización co ciclo de catro que escribín, 1197 00:50:20,050 --> 00:50:22,750 estaría comparando aquí de calquera maneira. 1198 00:50:22,750 --> 00:50:26,170 Entón tería que executado a través da matriz 1199 00:50:26,170 --> 00:50:34,380 e facer comparacións n n veces, porque cada vez que 1200 00:50:34,380 --> 00:50:36,670 realizar, a través del, tipo unha cousa. 1201 00:50:36,670 --> 00:50:38,300 1202 00:50:38,300 --> 00:50:41,475 >> E cada vez que percorren a matriz, facemos n comparacións. 1203 00:50:41,475 --> 00:50:42,920 1204 00:50:42,920 --> 00:50:46,330 Así, o noso tempo de execución para iso é en realidade, n ao cadrado, que 1205 00:50:46,330 --> 00:50:48,400 é moito peor na nosa rexistro final, porque iso 1206 00:50:48,400 --> 00:50:51,965 significa se tivésemos catro mil millóns de elementos, é 1207 00:50:51,965 --> 00:50:55,260 vai levar de catro millóns cadrados no canto de 32. 1208 00:50:55,260 --> 00:51:01,240 Entón, non é o mellor tempo de execución, pero para algunhas cousas, 1209 00:51:01,240 --> 00:51:04,610 vostede sabe, se está dentro un certo rango de elementos 1210 00:51:04,610 --> 00:51:06,540 bubble sort pode ser bo para usar. 1211 00:51:06,540 --> 00:51:07,530 >> Está ben. 1212 00:51:07,530 --> 00:51:12,290 Entón agora o que é o mellor caso de tempo de execución? 1213 00:51:12,290 --> 00:51:14,357 1214 00:51:14,357 --> 00:51:14,940 ALUMNO: Cero? 1215 00:51:14,940 --> 00:51:16,420 Ou 1? 1216 00:51:16,420 --> 00:51:18,140 >> Instrutor: Entón un faría ser unha comparación. 1217 00:51:18,140 --> 00:51:19,114 Right. 1218 00:51:19,114 --> 00:51:20,002 >> ALUMNO: N menos 1? 1219 00:51:20,002 --> 00:51:21,380 1220 00:51:21,380 --> 00:51:22,320 >> Instrutor: Entón, si. 1221 00:51:22,320 --> 00:51:22,990 Entón n menos un. 1222 00:51:22,990 --> 00:51:26,510 Sempre que ten un concepto como n menos 1, temos a tendencia de simplemente deixar a 1223 00:51:26,510 --> 00:51:31,680 e nós só dicir n porque ten comparar cada un dos these-- cada par. 1224 00:51:31,680 --> 00:51:36,470 Polo tanto, sería n menos 1, que nos que acabara de dicir é aproximadamente n. 1225 00:51:36,470 --> 00:51:39,280 Cando está lidando con tempo de execución, todo está achega. 1226 00:51:39,280 --> 00:51:43,860 Sempre que é o expoñente correcto, é moi bo. 1227 00:51:43,860 --> 00:51:45,700 >> Esa é a forma como lidamos con el. 1228 00:51:45,700 --> 00:51:47,410 1229 00:51:47,410 --> 00:51:51,780 Así que o mellor caso é n, que significa que a lista xa está clasificado, 1230 00:51:51,780 --> 00:51:54,320 e todo o que facemos é executado a través de e comproba que está clasificada. 1231 00:51:54,320 --> 00:51:56,110 1232 00:51:56,110 --> 00:51:56,855 Legal. 1233 00:51:56,855 --> 00:51:57,355 Todo correcto. 1234 00:51:57,355 --> 00:51:58,980 1235 00:51:58,980 --> 00:52:01,920 Entón, como ve aquí, nós só ten algúns gráficos. 1236 00:52:01,920 --> 00:52:02,660 Entón n ao cadrado. 1237 00:52:02,660 --> 00:52:03,780 1238 00:52:03,780 --> 00:52:05,120 Fun. 1239 00:52:05,120 --> 00:52:09,730 Moito peor que n, como vemos, e moi, moito peor que 2n rexistro. 1240 00:52:09,730 --> 00:52:12,060 E entón comeza tamén en rexistro rexistros. 1241 00:52:12,060 --> 00:52:18,020 E colle 124, entrar como a estrela de rexistro, que é como un tolo. 1242 00:52:18,020 --> 00:52:20,172 Entón, se vostede está interesado, estrela rexistro de busca. 1243 00:52:20,172 --> 00:52:20,880 É unha especie de diversión. 1244 00:52:20,880 --> 00:52:22,800 1245 00:52:22,800 --> 00:52:24,220 Polo tanto, temos este gran gráfico. 1246 00:52:24,220 --> 00:52:25,360 1247 00:52:25,360 --> 00:52:28,720 Só un heads-up, este un gráfico marabilloso ter 1248 00:52:28,720 --> 00:52:31,350 para a súa termo medio, porque nós tempo para preguntar-lle estas diluír. 1249 00:52:31,350 --> 00:52:36,090 Así, só a cabeza cara arriba, ten este no seu intercalar sobre a súa folla de fraude bo 1250 00:52:36,090 --> 00:52:36,616 alí. 1251 00:52:36,616 --> 00:52:37,990 Entón, nós só mirou para bubble sort. 1252 00:52:37,990 --> 00:52:39,510 1253 00:52:39,510 --> 00:52:42,370 No peor dos casos, n ao cadrado, mellor caso, n. 1254 00:52:42,370 --> 00:52:43,367 1255 00:52:43,367 --> 00:52:44,950 E nós imos ollar para os outros. 1256 00:52:44,950 --> 00:52:47,940 >> E como se pode ver, a única un que realmente fai ben 1257 00:52:47,940 --> 00:52:50,910 é merge sort, que nós imos entrar por que. 1258 00:52:50,910 --> 00:52:52,690 1259 00:52:52,690 --> 00:52:55,215 Entón, nós estamos indo a ir ao xunto un tipo de selección aqui--. 1260 00:52:55,215 --> 00:52:56,360 1261 00:52:56,360 --> 00:52:58,420 Alguén recorda como selección especie traballou? 1262 00:52:58,420 --> 00:53:05,200 1263 00:53:05,200 --> 00:53:05,700 Dalle. 1264 00:53:05,700 --> 00:53:08,210 >> ALUMNO: Basicamente pasar por unha orde e crear unha nova lista. 1265 00:53:08,210 --> 00:53:11,001 E así como está poñendo elementos en, poñelos no lugar seguro 1266 00:53:11,001 --> 00:53:11,750 na nova lista. 1267 00:53:11,750 --> 00:53:14,040 >> Instrutor: Así que os sons máis como ordenación por inserción. 1268 00:53:14,040 --> 00:53:15,040 Pero está realmente preto. 1269 00:53:15,040 --> 00:53:15,915 Son moi semellantes. 1270 00:53:15,915 --> 00:53:17,440 Mesmo eu pegalos mesturados ás veces. 1271 00:53:17,440 --> 00:53:18,981 Antes desta sección eu era como, esperar. 1272 00:53:18,981 --> 00:53:20,130 1273 00:53:20,130 --> 00:53:20,630 Está ben. 1274 00:53:20,630 --> 00:53:24,141 Entón, o que quere facer é a selección de clasificación, 1275 00:53:24,141 --> 00:53:25,890 o xeito que pode pensar sobre o tema ea forma 1276 00:53:25,890 --> 00:53:30,140 Eu me asegurarse de que non tentar obter los mesturados, é que atravesa 1277 00:53:30,140 --> 00:53:33,280 e selecciona o menor número e el 1278 00:53:33,280 --> 00:53:36,070 pon que no inicio da súa lista. 1279 00:53:36,070 --> 00:53:37,730 El cambio lo coa primeira posición. 1280 00:53:37,730 --> 00:53:42,600 1281 00:53:42,600 --> 00:53:45,370 Eles realmente teñen un exemplo para min. 1282 00:53:45,370 --> 00:53:46,540 Impresionante. 1283 00:53:46,540 --> 00:53:50,130 Así, só unha forma de pensar en selección ele-- tipo, seleccione o menor valor. 1284 00:53:50,130 --> 00:53:51,940 E nós estamos indo executado mediante un exemplo 1285 00:53:51,940 --> 00:53:55,320 que eu creo que vai axudar, porque Creo visuais sempre axudar. 1286 00:53:55,320 --> 00:53:58,510 Entón, imos comezar con algo que é totalmente normais. 1287 00:53:58,510 --> 00:54:00,730 Rede será indiferenciados, verde serán clasificados. 1288 00:54:00,730 --> 00:54:02,190 Todo fará sentido en un segundo. 1289 00:54:02,190 --> 00:54:08,950 >> Entón nós pasamos por e iteramos desde o principio ata o final. 1290 00:54:08,950 --> 00:54:12,320 E nós dicimos: OK, 2 é noso menor número. 1291 00:54:12,320 --> 00:54:15,680 Entón, nós imos tomar dous e imos para mover para a fronte da nosa matriz 1292 00:54:15,680 --> 00:54:17,734 porque é a menor número que temos. 1293 00:54:17,734 --> 00:54:19,150 Entón, iso é o que este está facendo aquí. 1294 00:54:19,150 --> 00:54:20,820 El só vai cambiar os dous. 1295 00:54:20,820 --> 00:54:21,850 1296 00:54:21,850 --> 00:54:25,450 Entón agora temos un clasificado parte e unha parte non clasificado. 1297 00:54:25,450 --> 00:54:27,810 E o que é bo lembrar sobre a selección de tipo 1298 00:54:27,810 --> 00:54:30,690 é que estamos seleccionando só da parte non clasificado. 1299 00:54:30,690 --> 00:54:32,220 1300 00:54:32,220 --> 00:54:34,527 >> A parte ordenada acaba de saír só. 1301 00:54:34,527 --> 00:54:35,660 Mm-hm? 1302 00:54:35,660 --> 00:54:38,452 >> ESTUDANTE: Como el sabe o que é menor sen comparalos lo 1303 00:54:38,452 --> 00:54:39,868 para todos os demais valores na matriz. 1304 00:54:39,868 --> 00:54:41,250 Instrutor: El fai comparalos-lo. 1305 00:54:41,250 --> 00:54:42,041 Nós gústanos de ignorados. 1306 00:54:42,041 --> 00:54:43,850 Este é só xeral global. 1307 00:54:43,850 --> 00:54:44,831 Si. 1308 00:54:44,831 --> 00:54:47,205 Cando escribimos o código que eu son seguro que vai estar máis satisfeito. 1309 00:54:47,205 --> 00:54:48,696 1310 00:54:48,696 --> 00:54:53,030 Pero garde este primeiro elemento como a menor. 1311 00:54:53,030 --> 00:54:56,110 Vostede compara e dicir, OK, é menor? 1312 00:54:56,110 --> 00:54:56,660 Si. 1313 00:54:56,660 --> 00:54:57,460 Mantelo. 1314 00:54:57,460 --> 00:54:58,640 Aquí é menor? 1315 00:54:58,640 --> 00:54:59,660 Non? 1316 00:54:59,660 --> 00:55:02,510 >> Esta é a súa pequena, descargar-lo para o seu valor. 1317 00:55:02,510 --> 00:55:06,340 E será moito máis feliz cando imos a través do código. 1318 00:55:06,340 --> 00:55:07,510 1319 00:55:07,510 --> 00:55:13,970 Entón nós pasamos, nos troca-lo, polo que, a continuación, miramos para esta parcela non clasificado. 1320 00:55:13,970 --> 00:55:15,810 Entón, nós estamos indo a seleccionar tres. 1321 00:55:15,810 --> 00:55:18,890 Estamos indo para poñelas polo o fin da nosa parte ordenada. 1322 00:55:18,890 --> 00:55:20,267 1323 00:55:20,267 --> 00:55:23,100 E nós só estamos indo para continuar facendo que, facendo iso, e facendo iso. 1324 00:55:23,100 --> 00:55:24,130 1325 00:55:24,130 --> 00:55:27,420 Polo tanto, este é o noso tipo de pseudocódigo aquí. 1326 00:55:27,420 --> 00:55:29,470 1327 00:55:29,470 --> 00:55:31,380 Imos codificar-lo aquí en un segundo. 1328 00:55:31,380 --> 00:55:34,140 1329 00:55:34,140 --> 00:55:37,270 Pero só unha cousa de andar a través dun alto nivel. 1330 00:55:37,270 --> 00:55:40,275 Está indo a ir de i é igual a 0 para n menos 2. 1331 00:55:40,275 --> 00:55:41,570 1332 00:55:41,570 --> 00:55:43,530 Esa é outra optimización. 1333 00:55:43,530 --> 00:55:45,020 Non te preocupes moito con iso. 1334 00:55:45,020 --> 00:55:46,620 Entón, como estaba dicindo. 1335 00:55:46,620 --> 00:55:49,660 1336 00:55:49,660 --> 00:55:54,406 Como Jacob estaba dicindo, coma nós seguir o que o noso mínimo é? 1337 00:55:54,406 --> 00:55:55,030 Como sabemos? 1338 00:55:55,030 --> 00:55:57,060 Temos que comparar todo na nosa lista. 1339 00:55:57,060 --> 00:55:59,600 >> Entón mínimo é igual a i. 1340 00:55:59,600 --> 00:56:03,870 É só dicir, neste caso, o índice do noso valor mínimo. 1341 00:56:03,870 --> 00:56:07,660 Entón vai para percorrer e que vai de j é igual a i + 1. 1342 00:56:07,660 --> 00:56:11,420 Entón xa sabemos que este é o noso primeiro elemento. 1343 00:56:11,420 --> 00:56:13,240 Non necesitamos comparalos-lo a si mesmo. 1344 00:56:13,240 --> 00:56:16,970 Entón nós comezamos a comparalo con o seguinte o que é por iso que é i + 1 para n 1345 00:56:16,970 --> 00:56:20,110 menos 1, que é a final da matriz alí. 1346 00:56:20,110 --> 00:56:25,090 E nós dixemos, se da matriz en j sexa inferior a matriz min, 1347 00:56:25,090 --> 00:56:29,200 entón nós recolocar onde nosos índices mínimos é. 1348 00:56:29,200 --> 00:56:37,470 >> E se non min é igual a i, como en que estabamos de volta para aquí. 1349 00:56:37,470 --> 00:56:38,950 1350 00:56:38,950 --> 00:56:41,790 Así como cando fixemos primeiro un regalo. 1351 00:56:41,790 --> 00:56:49,310 Neste caso, iria comezar a cero, el acabaría sendo dous. 1352 00:56:49,310 --> 00:56:53,010 Así, non sería igual min i na final. 1353 00:56:53,010 --> 00:56:55,720 Isto nos permite saber que necesitamos trocalos. 1354 00:56:55,720 --> 00:56:57,420 1355 00:56:57,420 --> 00:57:00,470 Eu me sinto como un exemplo concreto axudará moito máis que iso. 1356 00:57:00,470 --> 00:57:04,970 Entón, eu vou codificar iso convosco agora e eu creo que vai ser mellor. 1357 00:57:04,970 --> 00:57:07,380 1358 00:57:07,380 --> 00:57:11,350 >> Tipos adoitan traballar desa forma en que moitas veces é mellor só para velos. 1359 00:57:11,350 --> 00:57:12,780 1360 00:57:12,780 --> 00:57:17,280 Entón, o que queremos facer é queremos primeiro en menor 1361 00:57:17,280 --> 00:57:19,890 elemento na súa posición na matriz. 1362 00:57:19,890 --> 00:57:21,280 O que Jacob estaba dicindo. 1363 00:57:21,280 --> 00:57:23,090 Debe almacenar que dalgunha forma. 1364 00:57:23,090 --> 00:57:25,900 Entón, imos comezar iteración sobre a matriz. 1365 00:57:25,900 --> 00:57:28,970 Nós imos dicir que é noso primeiro só para comezar. 1366 00:57:28,970 --> 00:57:38,308 Entón, nós imos ter int menor é igual ao da matriz en i. 1367 00:57:38,308 --> 00:57:40,500 1368 00:57:40,500 --> 00:57:45,050 >> Entón, unha cousa a notar, cada tempo este bucle execútase, 1369 00:57:45,050 --> 00:57:48,550 estamos comezando un paso máis adiante. 1370 00:57:48,550 --> 00:57:54,780 1371 00:57:54,780 --> 00:57:57,440 Cando comezamos miramos para este. 1372 00:57:57,440 --> 00:58:00,840 A próxima vez que iterado, estamos comezando nun presente 1373 00:58:00,840 --> 00:58:02,680 e atribuíndolle o noso menor valor. 1374 00:58:02,680 --> 00:58:10,450 Polo tanto, é moi semellante ao bubble sort onde sabemos que despois dunha pasaxe, 1375 00:58:10,450 --> 00:58:11,700 este último elemento é clasificado. 1376 00:58:11,700 --> 00:58:12,810 1377 00:58:12,810 --> 00:58:15,120 Coa selección de clasificación, que é todo o contrario. 1378 00:58:15,120 --> 00:58:18,950 >> En cada paso, sabemos que o primeiro é clasificada. 1379 00:58:18,950 --> 00:58:21,360 Tras a segunda pasaxe, o segunda será clasificada. 1380 00:58:21,360 --> 00:58:26,470 E como viu cos exemplos de diapositivas, nosa porción ordenados non para de crecer. 1381 00:58:26,470 --> 00:58:34,020 Así, definindo o noso menor un para matrices i, todo o que está facendo 1382 00:58:34,020 --> 00:58:37,340 constrição é o que nós estamos mirando de forma 1383 00:58:37,340 --> 00:58:40,164 para minimizar o número de comparacións que facemos. 1384 00:58:40,164 --> 00:58:41,770 Isto ten sentido para todos? 1385 00:58:41,770 --> 00:58:42,920 1386 00:58:42,920 --> 00:58:46,380 Debe de min para ser executado a través de que de novo máis lenta ou con palabras diferentes? 1387 00:58:46,380 --> 00:58:47,180 Estou feliz por. 1388 00:58:47,180 --> 00:58:48,095 1389 00:58:48,095 --> 00:58:48,595 Está ben. 1390 00:58:48,595 --> 00:58:50,060 1391 00:58:50,060 --> 00:58:55,540 >> Entón, nós estamos almacenando o valor neste punto, 1392 00:58:55,540 --> 00:58:57,840 pero tamén queremos almacenar o índice. 1393 00:58:57,840 --> 00:59:01,010 Entón, nós estamos indo para almacenar o posición da menor 1394 00:59:01,010 --> 00:59:02,770 un, que só vai ser eu. 1395 00:59:02,770 --> 00:59:04,357 1396 00:59:04,357 --> 00:59:05,440 Entón agora Jacob está satisfeito. 1397 00:59:05,440 --> 00:59:06,870 Temos cousas gardadas. 1398 00:59:06,870 --> 00:59:08,240 1399 00:59:08,240 --> 00:59:11,870 E agora temos que mirar a través de a parte non separados da matriz. 1400 00:59:11,870 --> 00:59:18,170 Polo tanto, neste caso esta sería o noso indiferenciados. 1401 00:59:18,170 --> 00:59:20,980 1402 00:59:20,980 --> 00:59:22,462 Este é i. 1403 00:59:22,462 --> 00:59:25,430 1404 00:59:25,430 --> 00:59:26,210 Está ben. 1405 00:59:26,210 --> 00:59:30,040 >> Entón o que nós imos facer será para un loop. 1406 00:59:30,040 --> 00:59:32,066 Sempre que precisa iterado través dun array, 1407 00:59:32,066 --> 00:59:33,440 a súa mente podería ir a un loop. 1408 00:59:33,440 --> 00:59:34,760 1409 00:59:34,760 --> 00:59:38,090 Así, para algúns int k equals-- o que pensamos 1410 00:59:38,090 --> 00:59:39,700 k será igual a comezar con? 1411 00:59:39,700 --> 00:59:41,580 1412 00:59:41,580 --> 00:59:44,766 Isto é o que definimos como o noso menor valor e queremos comparalo lo. 1413 00:59:44,766 --> 00:59:47,090 O que queremos comparar? 1414 00:59:47,090 --> 00:59:48,730 Será este próximo, non? 1415 00:59:48,730 --> 00:59:53,200 Entón, nós queremos k ser inicializar para i + 1 para comezar. 1416 00:59:53,200 --> 00:59:55,350 1417 00:59:55,350 --> 01:00:02,800 >> E queremos k neste caso, Xa tamaño almacenados aquí, 1418 01:00:02,800 --> 01:00:03,930 para que poidamos usar só tamaño. 1419 01:00:03,930 --> 01:00:06,240 Tamaño sendo o tamaño da matriz. 1420 01:00:06,240 --> 01:00:09,620 E nós só queremos actualizar k por un de cada vez. 1421 01:00:09,620 --> 01:00:17,410 1422 01:00:17,410 --> 01:00:17,910 Legal. 1423 01:00:17,910 --> 01:00:19,650 1424 01:00:19,650 --> 01:00:23,430 Entón, agora necesitamos atopar o elemento máis pequeno aquí. 1425 01:00:23,430 --> 01:00:24,470 1426 01:00:24,470 --> 01:00:31,380 Entón, se nós iterado, nós quere dicir, se a matriz en k 1427 01:00:31,380 --> 01:00:37,080 é menor que a menor value-- este é o lugar onde estamos, en realidade, 1428 01:00:37,080 --> 01:00:42,950 manter o control do que é a menor aquí- 1429 01:00:42,950 --> 01:00:47,740 entón queremos trasladar o noso menor valor é. 1430 01:00:47,740 --> 01:00:50,645 >> Isto significa que, oh, somos iteración por aquí. 1431 01:00:50,645 --> 01:00:51,699 1432 01:00:51,699 --> 01:00:53,740 Calquera valor que está aquí é non a nosa máis pequena cousa. 1433 01:00:53,740 --> 01:00:54,448 Non queremos iso. 1434 01:00:54,448 --> 01:00:56,100 Queremos trasladar-lo. 1435 01:00:56,100 --> 01:01:02,050 Entón, se estamos a reatribuição-lo, o que facer pensas que pode ser neste código aquí? 1436 01:01:02,050 --> 01:01:04,160 Queremos trasladar menor e posición. 1437 01:01:04,160 --> 01:01:05,740 1438 01:01:05,740 --> 01:01:07,010 Entón, o que é menor agora? 1439 01:01:07,010 --> 01:01:08,422 1440 01:01:08,422 --> 01:01:09,130 ESTUDANTE: Array k. 1441 01:01:09,130 --> 01:01:09,963 Instrutor: Array k. 1442 01:01:09,963 --> 01:01:13,480 1443 01:01:13,480 --> 01:01:15,956 E cal é a posición agora? 1444 01:01:15,956 --> 01:01:20,940 1445 01:01:20,940 --> 01:01:23,000 O que hai de os índices de noso menor valor? 1446 01:01:23,000 --> 01:01:24,030 1447 01:01:24,030 --> 01:01:24,530 É só k. 1448 01:01:24,530 --> 01:01:25,690 1449 01:01:25,690 --> 01:01:27,790 Entón matriz k, k, eles combinan. 1450 01:01:27,790 --> 01:01:31,670 1451 01:01:31,670 --> 01:01:33,120 Entón, nós queriamos que recolocar. 1452 01:01:33,120 --> 01:01:34,390 1453 01:01:34,390 --> 01:01:39,950 E entón, despois que atopamos o menor, Así, a finais deste loop 1454 01:01:39,950 --> 01:01:45,100 aquí atopamos o noso menor valor é, polo tanto, só troca-lo. 1455 01:01:45,100 --> 01:01:47,100 1456 01:01:47,100 --> 01:01:50,816 Neste caso, como dicir que a nosa menor valor é aquí fóra. 1457 01:01:50,816 --> 01:01:51,940 Este é o noso menor valor. 1458 01:01:51,940 --> 01:01:57,690 >> Nós só queremos troca-lo aquí, o que é o que este función intercambio na parte inferior 1459 01:01:57,690 --> 01:02:01,270 fixo, que acabamos escribiu-se xunto a algúns minutos. 1460 01:02:01,270 --> 01:02:02,775 Por iso, debe parecer familiar. 1461 01:02:02,775 --> 01:02:04,320 1462 01:02:04,320 --> 01:02:08,030 E entón el só vai iterado por medio ata acadar todo o camiño 1463 01:02:08,030 --> 01:02:13,100 ao final, o que significa que ten cero elementos que son indiferenciados 1464 01:02:13,100 --> 01:02:14,800 e todo o máis foi resolto. 1465 01:02:14,800 --> 01:02:16,216 1466 01:02:16,216 --> 01:02:16,715 Ten sentido? 1467 01:02:16,715 --> 01:02:18,010 1468 01:02:18,010 --> 01:02:19,280 Un pouco máis concretamente? 1469 01:02:19,280 --> 01:02:19,990 O código axuda? 1470 01:02:19,990 --> 01:02:21,720 1471 01:02:21,720 --> 01:02:26,410 >> ALUMNO: Para un tamaño, nunca realmente define-la ou cambia-la, 1472 01:02:26,410 --> 01:02:27,340 como el sabe? 1473 01:02:27,340 --> 01:02:32,380 >> Instrutor: Entón unha cousa a notarse aquí é o tamaño int. 1474 01:02:32,380 --> 01:02:35,680 Entón, nós estamos dicindo neste tipo sort-- é unha función neste case-- é 1475 01:02:35,680 --> 01:02:40,770 selección especie, é pasado na coa función. 1476 01:02:40,770 --> 01:02:43,460 Entón, se non foi aprobada en, faría algo 1477 01:02:43,460 --> 01:02:47,840 como coa lonxitude da matriz ou iterado 1478 01:02:47,840 --> 01:02:49,390 para atopar a lonxitude. 1479 01:02:49,390 --> 01:02:52,680 Pero porque é pasado en, podemos usalo só. 1480 01:02:52,680 --> 01:02:55,720 Simplemente asumir que o usuario deulle un tamaño válido que 1481 01:02:55,720 --> 01:02:57,698 en realidade representa un tamaño da súa matriz. 1482 01:02:57,698 --> 01:02:59,461 1483 01:02:59,461 --> 01:02:59,960 Legal? 1484 01:02:59,960 --> 01:03:01,610 1485 01:03:01,610 --> 01:03:05,870 >> Se vostedes teñen algún problema con estes ou quere máis práctica de codificación tipo 1486 01:03:05,870 --> 01:03:08,050 no seu propio país, ten que ir study.cs50. 1487 01:03:08,050 --> 01:03:11,560 1488 01:03:11,560 --> 01:03:12,670 É unha ferramenta. 1489 01:03:12,670 --> 01:03:15,040 Teñen un verificador que realmente pode escribir. 1490 01:03:15,040 --> 01:03:16,180 Eles fan pseudocódigo. 1491 01:03:16,180 --> 01:03:19,310 Teñen máis vídeos e diapositivas incluíndo os que eu uso aquí. 1492 01:03:19,310 --> 01:03:23,150 Entón, se aínda está sentindo un pouco confuso, proba iso. 1493 01:03:23,150 --> 01:03:25,670 Como sempre, veña falar comigo, tamén. 1494 01:03:25,670 --> 01:03:26,320 Pregunta? 1495 01:03:26,320 --> 01:03:28,611 >> Estudante: Vostede está dicindo que o tamaño é previamente definido? 1496 01:03:28,611 --> 01:03:29,234 1497 01:03:29,234 --> 01:03:29,900 Instrutor: Si. 1498 01:03:29,900 --> 01:03:35,570 Tamaño é previamente definido se aquí na declaración da función. 1499 01:03:35,570 --> 01:03:39,060 Entón asume que el fose aprobada en polo usuario, e para simplificar, 1500 01:03:39,060 --> 01:03:41,896 imos supor que o usuario nos deu o tamaño correcto. 1501 01:03:41,896 --> 01:03:43,240 Legal. 1502 01:03:43,240 --> 01:03:44,390 Entón, iso é a selección de clasificación. 1503 01:03:44,390 --> 01:03:45,590 1504 01:03:45,590 --> 01:03:47,640 Xente, sei que estamos aprendendo moito hoxe. 1505 01:03:47,640 --> 01:03:49,710 É unha densa datos para sección. 1506 01:03:49,710 --> 01:03:51,880 1507 01:03:51,880 --> 01:03:57,340 Entón, con iso, imos ir a ordenación por inserción. 1508 01:03:57,340 --> 01:04:01,550 1509 01:04:01,550 --> 01:04:02,510 >> Está ben. 1510 01:04:02,510 --> 01:04:06,100 Entón, antes de que temos que facer nosa análise runtime aquí. 1511 01:04:06,100 --> 01:04:10,190 Así, no mellor dos casos, concedida sempre que eu mostre 1512 01:04:10,190 --> 01:04:11,960 a mesa que eu xa tipo de xogou fóra. 1513 01:04:11,960 --> 01:04:15,430 Pero o mellor caso de execución, o que pensamos? 1514 01:04:15,430 --> 01:04:17,310 1515 01:04:17,310 --> 01:04:18,130 Todo resolto. 1516 01:04:18,130 --> 01:04:21,040 1517 01:04:21,040 --> 01:04:22,070 N ao cadrado. 1518 01:04:22,070 --> 01:04:24,780 Alguén ten unha explicación por que pensas? 1519 01:04:24,780 --> 01:04:29,060 1520 01:04:29,060 --> 01:04:30,519 >> Estudante: Está comparando through-- 1521 01:04:30,519 --> 01:04:31,268 Instrutor: Certo. 1522 01:04:31,268 --> 01:04:32,540 Está comparando a través. 1523 01:04:32,540 --> 01:04:35,630 En cada iteración, a pesar de estamos diminuíndo este por un, 1524 01:04:35,630 --> 01:04:38,950 aínda está a buscar todo para atopar o menor. 1525 01:04:38,950 --> 01:04:42,390 Así, aínda que o seu menor valor É aquí, en principio, 1526 01:04:42,390 --> 01:04:44,710 aínda está comparando-a contra o resto 1527 01:04:44,710 --> 01:04:46,550 para que seguro que é a máis pequena cousa. 1528 01:04:46,550 --> 01:04:49,820 Entón vai acabar correndo por aproximadamente n veces ao cadrado. 1529 01:04:49,820 --> 01:04:51,090 1530 01:04:51,090 --> 01:04:51,590 Todo correcto. 1531 01:04:51,590 --> 01:04:52,785 E o que é o peor caso? 1532 01:04:52,785 --> 01:04:54,350 1533 01:04:54,350 --> 01:04:57,980 Tamén n ao cadrado, porque está indo estar facendo este mesmo procedemento. 1534 01:04:57,980 --> 01:05:01,670 Polo tanto, neste caso, a selección tipo ten algo 1535 01:05:01,670 --> 01:05:04,010 que tamén chamamos tempo de execución esperado. 1536 01:05:04,010 --> 01:05:07,400 Así, nos outros, só sei os límites superior e inferior. 1537 01:05:07,400 --> 01:05:11,180 Dependendo de como o noso tolo lista é ou como indiferenciados é, 1538 01:05:11,180 --> 01:05:15,350 que varían entre n ou n ao cadrado. 1539 01:05:15,350 --> 01:05:16,550 Non sabemos. 1540 01:05:16,550 --> 01:05:22,820 >> Pero por que a selección especie ten o mesmo peor eo mellor caso, que nos di que 1541 01:05:22,820 --> 01:05:25,880 non importa o tipo de entrada que ter, se é completamente 1542 01:05:25,880 --> 01:05:29,130 clasificadas ou totalmente inversa clasificadas, é 1543 01:05:29,130 --> 01:05:30,740 vai levar a mesma cantidade de tempo. 1544 01:05:30,740 --> 01:05:33,760 Entón, nese caso, se Teña en conta que da nosa mesa, 1545 01:05:33,760 --> 01:05:38,610 realmente tiña un valor que estes dous tipos non teñen, 1546 01:05:38,610 --> 01:05:40,390 tempo de execución que é esperado. 1547 01:05:40,390 --> 01:05:43,350 Entón, nós sabemos que sempre que corremos selección especie, 1548 01:05:43,350 --> 01:05:45,380 se pode garantir que executar un tempo n ao cadrado. 1549 01:05:45,380 --> 01:05:46,630 Non hai variabilidade alí. 1550 01:05:46,630 --> 01:05:47,630 É só esperar. 1551 01:05:47,630 --> 01:05:48,820 1552 01:05:48,820 --> 01:05:52,140 E, de novo, se quere aprender máis, tomar CS 124 na primavera. 1553 01:05:52,140 --> 01:05:55,370 1554 01:05:55,370 --> 01:05:56,712 Todo correcto. 1555 01:05:56,712 --> 01:05:57,545 Xa vimos este. 1556 01:05:57,545 --> 01:05:58,530 1557 01:05:58,530 --> 01:05:59,030 Legal. 1558 01:05:59,030 --> 01:06:00,930 Así, tipo de inserción. 1559 01:06:00,930 --> 01:06:03,330 E eu estou indo probablemente para brillar por iso. 1560 01:06:03,330 --> 01:06:05,440 Non vou ter vostedes codifica-lo. 1561 01:06:05,440 --> 01:06:06,580 Nós imos só pasar por ela. 1562 01:06:06,580 --> 01:06:10,500 Entón ordenación por inserción é unha especie de semellante á selección especie 1563 01:06:10,500 --> 01:06:14,460 en que temos tanto un indiferenciados e ordenados parte da matriz. 1564 01:06:14,460 --> 01:06:20,260 >> Pero o que é diferente é que como pasar por un por un, 1565 01:06:20,260 --> 01:06:24,210 nós só tomar calquera número é o seguinte na nosa indiferenciados, 1566 01:06:24,210 --> 01:06:28,507 e clasificalos lo correctamente na nosa matriz clasificada. 1567 01:06:28,507 --> 01:06:30,090 Vai facer máis sentido cun exemplo. 1568 01:06:30,090 --> 01:06:31,140 1569 01:06:31,140 --> 01:06:35,430 Entón, todo comeza como indiferenciados, Así como coa selección tipo. 1570 01:06:35,430 --> 01:06:38,740 E nós imos resolver iso en orde ascendente como fomos. 1571 01:06:38,740 --> 01:06:40,360 1572 01:06:40,360 --> 01:06:43,340 Entón, na nosa primeira pasaxe tomamos o primeiro valor 1573 01:06:43,340 --> 01:06:46,700 e dicimos: OK, está agora nunha lista por si mesmo. 1574 01:06:46,700 --> 01:06:49,150 >> Porque está nunha lista por si mesmo, está clasificado. 1575 01:06:49,150 --> 01:06:52,460 Parabéns por ser o primeiro elemento desta matriz. 1576 01:06:52,460 --> 01:06:54,800 Xa está resolto todo no seu propio país. 1577 01:06:54,800 --> 01:06:58,900 Entón agora temos un clasificado e un conxunto indiferenciado. 1578 01:06:58,900 --> 01:07:01,760 Entón, agora imos dar o primeiro. 1579 01:07:01,760 --> 01:07:05,600 Que pasa entre aquí e aquí está o que nós dicimos, 1580 01:07:05,600 --> 01:07:08,890 OK, imos ollar para o primeiro valor da nosa matriz indiferenciados 1581 01:07:08,890 --> 01:07:13,270 e nós estamos indo a introducir-lo no seu correcto lugar na matriz de clasificación. 1582 01:07:13,270 --> 01:07:21,460 >> Entón, o que facemos é tomar 5 e podemos dicir, OK, 5 é maior que 3, 1583 01:07:21,460 --> 01:07:24,630 por iso, só inserir-lo dereito á dereita do que iso. 1584 01:07:24,630 --> 01:07:25,130 Somos bos. 1585 01:07:25,130 --> 01:07:26,200 1586 01:07:26,200 --> 01:07:28,420 Entón imos ao noso próximo. 1587 01:07:28,420 --> 01:07:29,720 E tomamos dous. 1588 01:07:29,720 --> 01:07:34,330 Dicimos, OK, 2 é menos de 3, polo que sabemos que 1589 01:07:34,330 --> 01:07:36,220 Debe de estar no cabeza da nosa lista agora. 1590 01:07:36,220 --> 01:07:41,800 Entón, o que facemos é empurrar 3 e 5 para abaixo e pasamos 2 no que o primeiro slot. 1591 01:07:41,800 --> 01:07:42,990 1592 01:07:42,990 --> 01:07:45,870 Entón, nós estamos só inseríndoas o o lugar correcto que debería ser. 1593 01:07:45,870 --> 01:07:46,960 1594 01:07:46,960 --> 01:07:49,470 >> Entón, miramos para o noso seguinte, e nós dicimos seis. 1595 01:07:49,470 --> 01:07:53,620 OK, é maior que 6 todo na nosa matriz clasificada, 1596 01:07:53,620 --> 01:07:56,000 por iso, só marcalo ata o final. 1597 01:07:56,000 --> 01:07:56,960 E entón miramos para catro. 1598 01:07:56,960 --> 01:07:58,130 1599 01:07:58,130 --> 01:08:03,020 4 é inferior a 6, é menos que 5, pero é maior que 3. 1600 01:08:03,020 --> 01:08:06,270 Por iso, só tes que inserir-lo á dereita en a medio entre 3 e 5. 1601 01:08:06,270 --> 01:08:07,380 1602 01:08:07,380 --> 01:08:10,530 Que algo para facer pouco máis concreto, 1603 01:08:10,530 --> 01:08:12,280 aquí é o tipo de idea do que pasou. 1604 01:08:12,280 --> 01:08:16,430 Así, para cada elemento non clasificado, que determinar onde na parcela clasificada 1605 01:08:16,430 --> 01:08:17,090 el é. 1606 01:08:17,090 --> 01:08:20,680 >> Así, tendo en conta a clasificado e non clasificado, 1607 01:08:20,680 --> 01:08:26,080 temos que atravesar e figura para onde el encaixa na matriz de clasificación. 1608 01:08:26,080 --> 01:08:31,460 E nós inserir-lo, desprazando o elementos á dereita do que abaixo. 1609 01:08:31,460 --> 01:08:34,910 E entón nós só manter iterado ata que 1610 01:08:34,910 --> 01:08:39,270 ten unha lista completamente resolto onde indiferenciados agora é cero 1611 01:08:39,270 --> 01:08:41,720 e ordenada recolle o totalidade da nosa lista. 1612 01:08:41,720 --> 01:08:43,146 1613 01:08:43,146 --> 01:08:45,854 Entón, de novo, para facer as cousas aínda máis concreto, temos pseudocódigo. 1614 01:08:45,854 --> 01:08:47,979 1615 01:08:47,979 --> 01:08:52,410 >> Entón, basicamente, para i é igual a 0 a n menos 1, 1616 01:08:52,410 --> 01:08:54,790 iso é só a lonxitude da nosa matriz. 1617 01:08:54,790 --> 01:09:00,979 Temos algún elemento que é igual a a primeira matriz ou os primeiros índices. 1618 01:09:00,979 --> 01:09:03,200 Montar j igual a iso. 1619 01:09:03,200 --> 01:09:04,649 1620 01:09:04,649 --> 01:09:09,210 Así, mentres j é maior que cero e matriz, j menos 1 1621 01:09:09,210 --> 01:09:11,660 é maior que o elemento, polo que todo o que está facendo 1622 01:09:11,660 --> 01:09:17,479 é estar seguro de que seu j representa realmente 1623 01:09:17,479 --> 01:09:20,010 a porción non triados da matriz. 1624 01:09:20,010 --> 01:09:30,745 >> Así, mentres aínda hai cousas para clasificar e j menos un é-- que 1625 01:09:30,745 --> 01:09:31,840 é o elemento a ela? 1626 01:09:31,840 --> 01:09:34,760 J nunca foi definido aquí. 1627 01:09:34,760 --> 01:09:35,677 É unha especie de irritante. 1628 01:09:35,677 --> 01:09:36,176 Está ben. 1629 01:09:36,176 --> 01:09:36,689 De calquera forma. 1630 01:09:36,689 --> 01:09:39,899 Entón j menos 1, está comprobando o elemento antes. 1631 01:09:39,899 --> 01:09:46,460 Está dicindo, OK, é o elemento antes de onde queira que eu am-- imos 1632 01:09:46,460 --> 01:09:47,540 realmente aproveitar iso. 1633 01:09:47,540 --> 01:09:52,580 1634 01:09:52,580 --> 01:09:56,830 Entón, digamos que se trata como na nosa segunda pasaxe. 1635 01:09:56,830 --> 01:09:59,525 Entón eu vai ser igual a 1, que é aquí. 1636 01:09:59,525 --> 01:10:03,310 1637 01:10:03,310 --> 01:10:06,025 >> Entón i será igual a 1. 1638 01:10:06,025 --> 01:10:09,510 1639 01:10:09,510 --> 01:10:13,702 Isto sería de 2, 4, 5, 6, 7. 1640 01:10:13,702 --> 01:10:16,060 1641 01:10:16,060 --> 01:10:16,750 Todo correcto. 1642 01:10:16,750 --> 01:10:20,945 Así, o noso elemento, neste caso, será igual a 4. 1643 01:10:20,945 --> 01:10:22,110 1644 01:10:22,110 --> 01:10:24,946 E nós temos algúns j que é será igual a 1. 1645 01:10:24,946 --> 01:10:29,770 1646 01:10:29,770 --> 01:10:30,971 Oh, j está diminuíndo. 1647 01:10:30,971 --> 01:10:31,720 Isto é o que é. 1648 01:10:31,720 --> 01:10:35,680 Entón, j é igual a i, entón o que é iso dicindo é que a medida que avanzamos, 1649 01:10:35,680 --> 01:10:37,530 estamos só asegurarse de que non estamos máis 1650 01:10:37,530 --> 01:10:43,520 indexación dese xeito cando estamos intentando para introducir as cousas na nosa lista clasificada. 1651 01:10:43,520 --> 01:10:49,850 >> Polo tanto, cando j é igual a 1 e, neste caso matriz j menos um-- tan matriz j menos 1 1652 01:10:49,850 --> 01:10:54,610 é 2 neste case-- se é iso maior que o elemento, 1653 01:10:54,610 --> 01:10:57,700 entón todo isto está facendo está cambiando as cousas. 1654 01:10:57,700 --> 01:11:04,790 Polo tanto, neste caso, unha matriz j menos Sería matriz de cero, o que é 2. 1655 01:11:04,790 --> 01:11:08,430 2 non é maior que 4, de xeito que este non é executado. 1656 01:11:08,430 --> 01:11:11,460 Así, o cambio non se move cara abaixo. 1657 01:11:11,460 --> 01:11:18,790 O que isto fai aquí é só movendo o array ordenado baixo. 1658 01:11:18,790 --> 01:11:22,340 1659 01:11:22,340 --> 01:11:26,400 Neste caso, de feito, nos podería fazer-- imos facelo tres. 1660 01:11:26,400 --> 01:11:28,080 1661 01:11:28,080 --> 01:11:31,970 Entón, se estamos a camiñar a través de Neste exemplo, agora estamos aquí. 1662 01:11:31,970 --> 01:11:32,740 Esta é clasificada. 1663 01:11:32,740 --> 01:11:34,492 1664 01:11:34,492 --> 01:11:35,200 Este é indiferenciado. 1665 01:11:35,200 --> 01:11:39,090 1666 01:11:39,090 --> 01:11:39,860 Legal? 1667 01:11:39,860 --> 01:11:46,620 Entón, i é igual a 2, así noso elemento é igual a 3. 1668 01:11:46,620 --> 01:11:47,920 1669 01:11:47,920 --> 01:11:52,270 E o noso j é igual a 2. 1670 01:11:52,270 --> 01:12:00,620 Entón miramos a través e nós dicir, OK, é matriz j menos un 1671 01:12:00,620 --> 01:12:03,470 maior que o elemento que nós estamos mirando? 1672 01:12:03,470 --> 01:12:05,540 E a resposta é si, non? 1673 01:12:05,540 --> 01:12:11,275 4 é maior que 3 e j é 2, polo tanto, este código é executado. 1674 01:12:11,275 --> 01:12:12,510 1675 01:12:12,510 --> 01:12:18,550 >> Entón, agora o que nós facemos unha serie de 2, polo que aquí, nós trocalos. 1676 01:12:18,550 --> 01:12:25,620 Entón, nós só dicir, OK, array en 2 agora será 3. 1677 01:12:25,620 --> 01:12:28,130 1678 01:12:28,130 --> 01:12:32,340 E j será igual j menos 1, que é 1. 1679 01:12:32,340 --> 01:12:34,590 1680 01:12:34,590 --> 01:12:37,200 Isto é horrible, pero vostedes a idea. 1681 01:12:37,200 --> 01:12:38,360 J é agora igual a 1. 1682 01:12:38,360 --> 01:12:44,360 E matriz j é só vai ser igual ao noso elemento, que foi de 4. 1683 01:12:44,360 --> 01:12:45,950 1684 01:12:45,950 --> 01:12:48,570 Eu apaguei algo que non debía ten ou algo miswrote, 1685 01:12:48,570 --> 01:12:49,910 pero vós comeza a idea. 1686 01:12:49,910 --> 01:12:50,640 >> É moverse en n. 1687 01:12:50,640 --> 01:12:51,920 1688 01:12:51,920 --> 01:12:57,960 E entón, se iso fose, sería lazo de novo e el dicía: OK, j é un momento. 1689 01:12:57,960 --> 01:13:00,665 E matriz j menos 1 é agora 2. 1690 01:13:00,665 --> 01:13:01,750 1691 01:13:01,750 --> 01:13:03,760 É de 2 a menos de noso elemento? 1692 01:13:03,760 --> 01:13:04,540 Non? 1693 01:13:04,540 --> 01:13:07,970 Isto significa que temos este elemento inserido 1694 01:13:07,970 --> 01:13:10,110 no punto correcto na nosa matriz clasificada. 1695 01:13:10,110 --> 01:13:14,400 Entón podemos levar isto e dicimos: OK, a nosa matriz clasificada está aquí. 1696 01:13:14,400 --> 01:13:19,940 E levaría ese número 6 e ser como, OK, é de 6 inferior a ese número? 1697 01:13:19,940 --> 01:13:20,480 Non? 1698 01:13:20,480 --> 01:13:21,080 Legal. 1699 01:13:21,080 --> 01:13:22,680 Estamos ben. 1700 01:13:22,680 --> 01:13:23,530 >> Facelo de novo. 1701 01:13:23,530 --> 01:13:24,740 Dicimos 7. 1702 01:13:24,740 --> 01:13:29,010 É menos que 7 finais da nosa matriz clasificada? 1703 01:13:29,010 --> 01:13:29,520 Non. 1704 01:13:29,520 --> 01:13:30,430 Entón, nós estamos ben. 1705 01:13:30,430 --> 01:13:32,760 Entón, iso sería resolto. 1706 01:13:32,760 --> 01:13:38,610 Basicamente todo isto fai se está dicindo take 1707 01:13:38,610 --> 01:13:42,060 o primeiro elemento súa matriz non clasificado, 1708 01:13:42,060 --> 01:13:46,010 descubrir a onde vai na súa matriz de clasificación. 1709 01:13:46,010 --> 01:13:48,780 E iso só se encarga de swaps de facelo. 1710 01:13:48,780 --> 01:13:51,300 Está basicamente só cambiando ata que estea no punto seguro. 1711 01:13:51,300 --> 01:13:53,600 1712 01:13:53,600 --> 01:13:56,990 A imaxe visual é que é movendo todo para abaixo, facendo iso. 1713 01:13:56,990 --> 01:13:59,420 >> Entón, é como a metade bubble sort-esquí. 1714 01:13:59,420 --> 01:14:02,280 1715 01:14:02,280 --> 01:14:03,420 Consulte estudo 50. 1716 01:14:03,420 --> 01:14:06,000 Recomendo probar codificar iso no seu propio país. 1717 01:14:06,000 --> 01:14:07,220 1718 01:14:07,220 --> 01:14:12,450 Se ten calquera problema ou se quere ver código de exemplo para un tipo de inserción, 1719 01:14:12,450 --> 01:14:13,750 por favor, me aviso. 1720 01:14:13,750 --> 01:14:14,500 Estou sempre por preto. 1721 01:14:14,500 --> 01:14:16,600 1722 01:14:16,600 --> 01:14:20,200 Entón, o peor caso de tempo de execución e mellor caso de execución. 1723 01:14:20,200 --> 01:14:30,700 Como viu cara da mesa eu xa mostre, é tanto n ao cadrado e n. 1724 01:14:30,700 --> 01:14:35,590 >> Así, tipo de ir fóra do que falamos sobre os nosos tipos anteriores, peor 1725 01:14:35,590 --> 01:14:38,760 caso de tempo de execución é que, se é totalmente non separados, 1726 01:14:38,760 --> 01:14:42,530 temos que comparar todos estes n veces. 1727 01:14:42,530 --> 01:14:47,020 Nós facemos unha morea de comparacións porque se está en orde inversa, 1728 01:14:47,020 --> 01:14:50,360 imos dicir, OK, este é o mesmo, isto é boa, 1729 01:14:50,360 --> 01:14:54,650 e este terá que ser comparados contra o primeiro en ser movido cara atrás. 1730 01:14:54,650 --> 01:14:56,710 E a medida que dirección o fin da cola, temos 1731 01:14:56,710 --> 01:14:59,440 comparar, comparar e comparar contra todo. 1732 01:14:59,440 --> 01:15:03,030 >> Entón, el acaba sendo preto de n ao cadrado. 1733 01:15:03,030 --> 01:15:09,510 Se é correcto, entón dicir, OK, 2, vostede é bo. 1734 01:15:09,510 --> 01:15:11,330 3, está en relación a dous. 1735 01:15:11,330 --> 01:15:12,310 Vostede é bo. 1736 01:15:12,310 --> 01:15:14,150 4, basta comparar coa cola. 1737 01:15:14,150 --> 01:15:14,990 Vostede é bo. 1738 01:15:14,990 --> 01:15:17,140 6, comparar coa cola, está ben. 1739 01:15:17,140 --> 01:15:20,870 Así, para cada punto, se xa está clasificadas, está facendo unha comparación. 1740 01:15:20,870 --> 01:15:22,320 Entón é só n. 1741 01:15:22,320 --> 01:15:26,840 E porque temos un mellor caso de execución de n e un caso peor tempo de execución de n 1742 01:15:26,840 --> 01:15:28,680 cadrado, non temos tempo de execución esperado. 1743 01:15:28,680 --> 01:15:31,290 1744 01:15:31,290 --> 01:15:34,020 >> E só depende do caos da nosa lista alí. 1745 01:15:34,020 --> 01:15:35,860 1746 01:15:35,860 --> 01:15:39,530 E, de novo, outra gráfico e outra táboa. 1747 01:15:39,530 --> 01:15:41,170 Así, as diferenzas entre os tipos. 1748 01:15:41,170 --> 01:15:44,180 Eu estou indo só para brisa a través, eu sentir como falamos extensivamente 1749 01:15:44,180 --> 01:15:46,570 sobre como todo tipo de variar e enlace xuntos. 1750 01:15:46,570 --> 01:15:50,564 Entón, merge sort é o último Vou che aborrecer con caras. 1751 01:15:50,564 --> 01:15:52,105 Temos un cadro moi colorido. 1752 01:15:52,105 --> 01:15:53,860 1753 01:15:53,860 --> 01:15:56,040 Entón, merge sort é un algoritmo recursivo. 1754 01:15:56,040 --> 01:15:59,910 Entón, vostedes saben o que unha función recursiva é? 1755 01:15:59,910 --> 01:16:01,550 1756 01:16:01,550 --> 01:16:03,320 >> Alguén quere dicir? 1757 01:16:03,320 --> 01:16:04,739 Quere tentar? 1758 01:16:04,739 --> 01:16:07,280 Así, unha función recursiva é só unha función que chama a si mesmo. 1759 01:16:07,280 --> 01:16:08,570 1760 01:16:08,570 --> 01:16:11,590 Entón, se vostedes están familiarizados coa secuencia de Fibonacci, 1761 01:16:11,590 --> 01:16:15,670 que se considera recursivo porque levar os dous anteriores 1762 01:16:15,670 --> 01:16:17,530 e engadila los xuntos para conseguir o seu próximo. 1763 01:16:17,530 --> 01:16:21,440 Entón recursiva, sempre penso de recursividade como como unha espiral 1764 01:16:21,440 --> 01:16:24,430 entón é como a espiral para abaixo para el. 1765 01:16:24,430 --> 01:16:27,150 Pero é só unha función que chama a si mesmo. 1766 01:16:27,150 --> 01:16:32,660 >> E, de feito, moi rapidamente eu pode amosar-lle o que parece. 1767 01:16:32,660 --> 01:16:34,260 1768 01:16:34,260 --> 01:16:41,840 Entón recursiva aquí, se miramos, este é a recursivamente para resumir nunha matriz. 1769 01:16:41,840 --> 01:16:45,900 1770 01:16:45,900 --> 01:16:47,880 Entón, todo o que facemos é temos a función suma 1771 01:16:47,880 --> 01:16:52,210 suma que leva un tamaño e unha matriz. 1772 01:16:52,210 --> 01:16:55,210 E se observar, o tamaño descensos dun nun. 1773 01:16:55,210 --> 01:17:00,365 E todo o que fai é se x é igual a zero-- tanto, se o tamaño da matriz 1774 01:17:00,365 --> 01:17:02,710 é igual a zero-- el retorna a cero. 1775 01:17:02,710 --> 01:17:10,440 >> Se non, el resume este último elemento da matriz, 1776 01:17:10,440 --> 01:17:14,790 e, a continuación, leva unha suma de resto da matriz. 1777 01:17:14,790 --> 01:17:17,555 Entón, é só rompe-lo para abaixo en problemas cada vez menores. 1778 01:17:17,555 --> 01:17:18,990 1779 01:17:18,990 --> 01:17:21,890 Longa historia curta, recursão, función que chama a si mesmo. 1780 01:17:21,890 --> 01:17:25,740 Se iso é todo o que ten fóra deste, iso é o que unha función recursiva é. 1781 01:17:25,740 --> 01:17:29,870 Se tomar 51, vai estar moi, moi cómodo con recursividade. 1782 01:17:29,870 --> 01:17:31,110 1783 01:17:31,110 --> 01:17:32,370 É moi legal. 1784 01:17:32,370 --> 01:17:34,660 Tiña sentido en como 03:00 unha noite fóra. 1785 01:17:34,660 --> 01:17:37,900 E eu era como, por que eu non uso iso? 1786 01:17:37,900 --> 01:17:39,170 1787 01:17:39,170 --> 01:17:42,430 >> Así, para merge sort, basicamente o que vai facer é que é 1788 01:17:42,430 --> 01:17:45,620 vai rompe-lo e rompe-lo abaixo ata que é só elementos individuais. 1789 01:17:45,620 --> 01:17:47,570 Os elementos individuais son fáciles de clasificar. 1790 01:17:47,570 --> 01:17:48,070 Vemos isto. 1791 01:17:48,070 --> 01:17:50,760 Se tes un elemento, é xa considerada clasificada. 1792 01:17:50,760 --> 01:17:53,800 Entón, nunha entrada de n elementos, se n é inferior a 2, 1793 01:17:53,800 --> 01:17:58,120 basta volver porque iso significa é 0 ou 1, como vimos. 1794 01:17:58,120 --> 01:18:00,050 Aqueles son considerados elementos ordenados. 1795 01:18:00,050 --> 01:18:02,170 >> Se non, rompe-lo ao medio. 1796 01:18:02,170 --> 01:18:06,336 Ordenar a primeira parte, clasificar a segunda metade, logo fundín-las. 1797 01:18:06,336 --> 01:18:07,460 Por que se chama merge sort. 1798 01:18:07,460 --> 01:18:08,700 1799 01:18:08,700 --> 01:18:12,155 Polo tanto, temos aquí nós imos resolver estes. 1800 01:18:12,155 --> 01:18:13,410 1801 01:18:13,410 --> 01:18:17,210 Así, temos telos ata que o tamaño da matriz é 1. 1802 01:18:17,210 --> 01:18:20,790 Entón, cando é un, nós só volver porque este é un array ordenado, 1803 01:18:20,790 --> 01:18:23,940 e este é un array ordenado, e iso é un array ordenado, todos estamos clasificadas. 1804 01:18:23,940 --> 01:18:25,390 1805 01:18:25,390 --> 01:18:29,420 Entón, o que facemos é comezar a fundirse los xuntos. 1806 01:18:29,420 --> 01:18:31,820 >> Así, o xeito que poida pensar en fusión é 1807 01:18:31,820 --> 01:18:36,240 acaba de eliminar a menor número de cada unha das sub-matrices 1808 01:18:36,240 --> 01:18:38,330 e só anexo-lo á matriz emerxeu. 1809 01:18:38,330 --> 01:18:44,290 Entón, se ollar aquí, cando temos estes conxuntos temos 4, 6 e 1. 1810 01:18:44,290 --> 01:18:47,280 Cando queremos mesturar estes, miramos para estes dous primeiros 1811 01:18:47,280 --> 01:18:50,730 e dicimos: OK, un é menor, vai para adiante. 1812 01:18:50,730 --> 01:18:54,330 4 e 6, non hai nada para comparar que el, só marcalo ata o final. 1813 01:18:54,330 --> 01:18:58,020 >> Cando quedamos estas dúas, nós só levar a unha menor destes dous, 1814 01:18:58,020 --> 01:18:59,310 polo que é un. 1815 01:18:59,310 --> 01:19:01,690 E agora nós tomamos a menor destes dous, entón 2. 1816 01:19:01,690 --> 01:19:03,330 Menor destes dous, tres. 1817 01:19:03,330 --> 01:19:06,260 Menor destes dous, 4, 5, 6. 1818 01:19:06,260 --> 01:19:08,630 Entón, está só tirando estes. 1819 01:19:08,630 --> 01:19:11,210 E porque teñen foron clasificadas anteriormente, 1820 01:19:11,210 --> 01:19:14,300 só ten unha Comparación de cada vez que hai. 1821 01:19:14,300 --> 01:19:19,610 Entón, máis código aquí, só representación. 1822 01:19:19,610 --> 01:19:24,410 Entón comeza no medio e clasificar esquerda e á dereita 1823 01:19:24,410 --> 01:19:26,180 e entón só mesturar aqueles. 1824 01:19:26,180 --> 01:19:30,080 >> E non temos código para fundir aquí. 1825 01:19:30,080 --> 01:19:34,110 Pero, de novo, se vai en estudar 50, que vai estar alí. 1826 01:19:34,110 --> 01:19:36,860 Se non, vir falar comigo Se aínda está confuso. 1827 01:19:36,860 --> 01:19:42,340 Entón cousa legal aquí é que mellor caso, peor caso, e tempo de execución espera 1828 01:19:42,340 --> 01:19:46,250 son todos no rexistro n, que é moito mellor que temos 1829 01:19:46,250 --> 01:19:48,000 visto para o resto das nosas sortes. 1830 01:19:48,000 --> 01:19:51,840 Vimos n ao cadrado eo que realmente 1831 01:19:51,840 --> 01:19:54,380 chegar aquí é n log n, o que é óptimo. 1832 01:19:54,380 --> 01:19:55,830 >> Mira como moito mellor que é. 1833 01:19:55,830 --> 01:19:56,780 Tal curva agradable. 1834 01:19:56,780 --> 01:19:58,130 1835 01:19:58,130 --> 01:20:00,120 Polo tanto, moito máis eficiente. 1836 01:20:00,120 --> 01:20:03,510 Se xa se poida, uso merge sort. 1837 01:20:03,510 --> 01:20:04,810 Ela lle vai aforrar tempo. 1838 01:20:04,810 --> 01:20:07,670 Entón, de novo, como dixemos, se está abaixo nesta rexión máis baixa, 1839 01:20:07,670 --> 01:20:09,480 non que facer moita diferenza. 1840 01:20:09,480 --> 01:20:11,360 Vostede levántase a miles e miles de entradas, 1841 01:20:11,360 --> 01:20:13,318 definitivamente quere un algoritmo máis eficiente. 1842 01:20:13,318 --> 01:20:14,730 1843 01:20:14,730 --> 01:20:19,400 E, unha vez máis, a nosa mesa fermoso de todos tipo que vostedes aprenderon hoxe. 1844 01:20:19,400 --> 01:20:21,157 >> Entón, sei que foi un día denso. 1845 01:20:21,157 --> 01:20:23,490 Iso non vai necesariamente para axudar co seu pset. 1846 01:20:23,490 --> 01:20:28,250 Pero eu só quero facer un disclaimer esta sección non é só sobre Serie de exercicios. 1847 01:20:28,250 --> 01:20:31,240 Todo este material é xusto xogo para os seus exames semestrais. 1848 01:20:31,240 --> 01:20:35,430 E tamén se continúa con CS, estes son os fundamentos realmente importantes 1849 01:20:35,430 --> 01:20:37,870 que precisa saber. 1850 01:20:37,870 --> 01:20:41,700 Así, uns días serán un pouco máis pset axuda, 1851 01:20:41,700 --> 01:20:44,600 pero algunhas semanas será contido moito máis efectiva 1852 01:20:44,600 --> 01:20:46,600 que pode non parecer super útil para ti agora, 1853 01:20:46,600 --> 01:20:51,215 pero eu prometer que se continúa no vai ser moi, moi útil. 1854 01:20:51,215 --> 01:20:52,560 1855 01:20:52,560 --> 01:20:54,250 >> Entón é iso por sección. 1856 01:20:54,250 --> 01:20:55,250 Down to the wire. 1857 01:20:55,250 --> 01:20:56,570 Eu fixen iso nun minuto. 1858 01:20:56,570 --> 01:20:58,262 1859 01:20:58,262 --> 01:20:58,970 Pero alí vai. 1860 01:20:58,970 --> 01:21:01,240 E eu vou ter Donuts ou doces. 1861 01:21:01,240 --> 01:21:03,464 Ten alguén alerxias a nada, polo camiño? 1862 01:21:03,464 --> 01:21:05,307 1863 01:21:05,307 --> 01:21:05,890 Ovos e leite. 1864 01:21:05,890 --> 01:21:08,120 Entón, Donuts son un non? 1865 01:21:08,120 --> 01:21:09,400 1866 01:21:09,400 --> 01:21:10,160 Está ben. 1867 01:21:10,160 --> 01:21:10,770 Todo correcto. 1868 01:21:10,770 --> 01:21:12,120 Sen chocolate? 1869 01:21:12,120 --> 01:21:12,620 Starburst. 1870 01:21:12,620 --> 01:21:13,837 1871 01:21:13,837 --> 01:21:14,670 Starbursts son boas. 1872 01:21:14,670 --> 01:21:15,170 Está ben. 1873 01:21:15,170 --> 01:21:17,045 Nós imos ter Starburst semana seguida. 1874 01:21:17,045 --> 01:21:18,240 Iso é o que eu vou chegar. 1875 01:21:18,240 --> 01:21:19,690 Vostedes teñen unha excelente semana. 1876 01:21:19,690 --> 01:21:20,460 Ler o spec. 1877 01:21:20,460 --> 01:21:22,130 >> Deixe-me saber se tes algunha preguntas. 1878 01:21:22,130 --> 01:21:25,300 PSet dúas clases deben ser para ti ata xoves. 1879 01:21:25,300 --> 01:21:28,320 Se ten algunha dúbida sobre como eu graduada algo 1880 01:21:28,320 --> 01:21:32,250 ou por que eu graduada algo do xeito que eu fixo, por favor me escriba, veña falar comigo. 1881 01:21:32,250 --> 01:21:34,210 Estou un pouco ese tolo semana, pero prometo 1882 01:21:34,210 --> 01:21:36,340 Eu aínda vou responder no prazo de 24 horas. 1883 01:21:36,340 --> 01:21:38,240 Entón, ten unha excelente semana a todos. 1884 01:21:38,240 --> 01:21:40,090 Boa sorte na súa pset. 1885 01:21:40,090 --> 01:21:41,248