1 00:00:06,762 --> 00:00:09,980 [Powered by Google Translate] TOMMY: Pieņemsim to apskatīt atlases veida, algoritmu 2 00:00:09,980 --> 00:00:12,800 par tādu sarakstu numurus un šķirošanu. 3 00:00:12,800 --> 00:00:15,750 Algoritms, atcerieties, ir vienkārši soli pa solim 4 00:00:15,750 --> 00:00:18,370 procedūra Veicot uzdevumu. 5 00:00:18,370 --> 00:00:21,470 Pamatideja atlases veida ir sadalīt 6 00:00:21,470 --> 00:00:23,390 Mūsu sarakstā divās daļās - 7 00:00:23,390 --> 00:00:26,810 sakārtoti daļu un nešķirotiem porciju. 8 00:00:26,810 --> 00:00:30,200 Katrā posmā no algoritma, numurs tiek pārvietots no 9 00:00:30,200 --> 00:00:33,800 nešķiroti daļa uz sakārtotās daļu līdz beidzot 10 00:00:33,800 --> 00:00:35,880 viss saraksts ir sakārtots. 11 00:00:35,880 --> 00:00:38,510 Tātad, šeit ir seši numuru saraksts - 12 00:00:38,510 --> 00:00:44,010 23, 42, 4, 16, 8, 15 un. 13 00:00:44,010 --> 00:00:47,680 Tieši tagad viss saraksts tiek uzskatīts nešķirotu. 14 00:00:47,680 --> 00:00:51,770 Kaut gan, piemēram, 16 numuru var jau būt tā pareizs 15 00:00:51,770 --> 00:00:56,040 vieta, mūsu algoritms ir nekādi nevar zināt, ka līdz 16 00:00:56,040 --> 00:00:57,980 viss saraksts ir sakārtots. 17 00:00:57,980 --> 00:01:01,355 Tātad mēs izskatīsim katru numurs ir nešķiroti līdz mēs sakārtot 18 00:01:01,355 --> 00:01:03,800 tā sevi. 19 00:01:03,800 --> 00:01:06,890 Mēs zinām, ka mēs vēlamies saraksts būtu augošā secībā. 20 00:01:06,890 --> 00:01:10,200 Tāpēc mēs vēlamies veidot kārtotas daļu no mūsu saraksta 21 00:01:10,200 --> 00:01:13,280 no kreisās uz labo, mazākā uz lielāko. 22 00:01:13,280 --> 00:01:17,970 Lai to izdarītu, mums ir nepieciešams, lai atrastu minimālo nešķirotu elements 23 00:01:17,970 --> 00:01:21,350 un nodot to beigās no sakārtotās daļu. 24 00:01:21,350 --> 00:01:25,370 Tā kā šis saraksts nav sakārtots, tad vienīgais veids, kā to darīt, ir 25 00:01:25,370 --> 00:01:29,330 apskatīt katru elementu ar nešķirotiem daļu, atceroties 26 00:01:29,330 --> 00:01:32,010 kas elements ir zemākais un salīdzinot 27 00:01:32,010 --> 00:01:33,770 katrs elements tam. 28 00:01:33,770 --> 00:01:36,150 Tāpēc mēs vispirms apskatīt 23. 29 00:01:36,150 --> 00:01:38,650 Šis ir pirmais elements, mēs esam redzējuši, tāpēc mēs atcerēties 30 00:01:38,650 --> 00:01:40,050 tā kā minimums. 31 00:01:40,050 --> 00:01:42,320 Nākamais mēs apskatīt 42. 32 00:01:42,320 --> 00:01:46,720 42 ir lielāks par 23, tāpēc 23 ir vēl minimums. 33 00:01:46,720 --> 00:01:51,210 Nākamais ir 4, kas ir mazāk nekā 23, tāpēc mēs atcerēties 4 34 00:01:51,210 --> 00:01:52,880 kā jaunu minimumu. 35 00:01:52,880 --> 00:01:56,380 Nākamais ir 16, kas ir lielāks par 4, SO 4 36 00:01:56,380 --> 00:01:57,980 joprojām ir minimums. 37 00:01:57,980 --> 00:02:03,670 8 ir lielāks par 4, un 15 ir lielāks par 4, SO 4 jābūt 38 00:02:03,670 --> 00:02:05,980 mazākais nešķiroti elements. 39 00:02:05,980 --> 00:02:09,350 Tātad, pat ja kā cilvēkiem mēs varam uzreiz redzēt, ka 4 ir 40 00:02:09,350 --> 00:02:12,300 minimālais elements, mūsu algoritms ir apskatīt 41 00:02:12,300 --> 00:02:15,710 Katru nešķirotiem elements, pat pēc mēs esam atraduši 4 - 42 00:02:15,710 --> 00:02:16,860 minimālās elements. 43 00:02:16,860 --> 00:02:19,900 Tāpēc tagad, ka mēs esam atraduši minimālo elementu, 4, mēs vēlamies 44 00:02:19,900 --> 00:02:23,410 lai to pārvietotu uz sakārtoti daļu sarakstu. 45 00:02:23,410 --> 00:02:27,320 Tā kā šis ir pirmais solis, tas nozīmē, ka mēs vēlamies likt 4 pie 46 00:02:27,320 --> 00:02:29,680 sākums saraksta. 47 00:02:29,680 --> 00:02:33,040 Šobrīd 23 ir sākumā sarakstu, lai 48 00:02:33,040 --> 00:02:36,080 pieņemsim mijmaiņas 4 un 23. 49 00:02:36,080 --> 00:02:38,870 Tātad tagad mūsu saraksts izskatās šādi. 50 00:02:38,870 --> 00:02:42,710 Mēs zinām, ka 4 ir jābūt tās galīgajā vietā, jo tas ir 51 00:02:42,710 --> 00:02:45,890 gan mazākais elements un elements sākumā 52 00:02:45,890 --> 00:02:46,960 no saraksta. 53 00:02:46,960 --> 00:02:50,650 Tātad tas nozīmē, ka mums nav kādreiz nepieciešams, lai pārvietotu to vēlreiz. 54 00:02:50,650 --> 00:02:53,910 Tāpēc pieņemsim atkārtot šo procesu, lai pievienotu citu elementu 55 00:02:53,910 --> 00:02:55,910 sakārtoti daļu saraksta. 56 00:02:55,910 --> 00:02:58,950 Mēs zinām, ka mums nav nepieciešams apskatīt 4, jo tas ir 57 00:02:58,950 --> 00:03:00,000 jau ir sakārtoti. 58 00:03:00,000 --> 00:03:03,540 Lai mēs varētu sākt 42, ko mēs atcerēties kā 59 00:03:03,540 --> 00:03:05,290 minimālās elements. 60 00:03:05,290 --> 00:03:08,700 Tātad nākamais mēs apskatīt no 23, kas ir mazāk nekā 42, tāpēc mums 61 00:03:08,700 --> 00:03:11,620 atcerieties 23 ir jauns minimums. 62 00:03:11,620 --> 00:03:14,870 Tālāk mēs redzēt 16, kas ir mazāk nekā 23, tāpēc 63 00:03:14,870 --> 00:03:16,800 16 ir jauns minimums. 64 00:03:16,800 --> 00:03:19,720 Tagad mēs skatāmies 8, kas ir mazāk nekā 16, tāpēc 65 00:03:19,720 --> 00:03:21,130 8 ir jauns minimums. 66 00:03:21,130 --> 00:03:25,900 Un visbeidzot 8 ir mazāk nekā 15, lai mēs zinām, ka 8 ir minimālā 67 00:03:25,900 --> 00:03:27,780 nešķiroti elements. 68 00:03:27,780 --> 00:03:30,660 Tātad tas nozīmē, ka mums vajadzētu pievienot 8 līdz sakārtoti 69 00:03:30,660 --> 00:03:32,450 daļa no saraksta. 70 00:03:32,450 --> 00:03:35,990 Tieši tagad 4 ir vienīgais sakārtoti elements, tāpēc mēs vēlamies ievietot 71 00:03:35,990 --> 00:03:38,410 8 blakus 4. 72 00:03:38,410 --> 00:03:41,920 Tā 42 ir pirmais elements nešķirotu daļu no 73 00:03:41,920 --> 00:03:47,260 sarakstu, mēs vēlamies, lai apmainītu 42 un 8. 74 00:03:47,260 --> 00:03:49,680 Tātad tagad mūsu saraksts izskatās šādi. 75 00:03:49,680 --> 00:03:53,830 4 un 8 pārstāv kārtotas daļu sarakstu, un 76 00:03:53,830 --> 00:03:56,440 pārējie skaitļi atspoguļo nešķirotiem 77 00:03:56,440 --> 00:03:58,260 daļa no saraksta. 78 00:03:58,260 --> 00:04:00,630 Tāpēc pieņemsim turpināt ar citu atkārtojuma. 79 00:04:00,630 --> 00:04:03,850 Mēs sākam ar 23 šoreiz, jo mums nav nepieciešams apskatīt 80 00:04:03,850 --> 00:04:05,770 4 un 8 vairs jo tie esam 81 00:04:05,770 --> 00:04:07,660 jau sakārtots. 82 00:04:07,660 --> 00:04:10,270 16 ir mazāk nekā 23, tāpēc mēs atcerēties 83 00:04:10,270 --> 00:04:12,070 16 kā jaunu minimumu. 84 00:04:12,070 --> 00:04:18,149 16 ir mazāk nekā 42, bet 15 ir mazāk nekā 16, tāpēc 15 ir jābūt 85 00:04:18,149 --> 00:04:20,480 minimālo nešķiroti elements. 86 00:04:20,480 --> 00:04:24,580 Tāpēc tagad mēs vēlamies, lai apmainītu 15 un no 23 līdz 87 00:04:24,580 --> 00:04:26,310 dod mums šo sarakstu. 88 00:04:26,310 --> 00:04:30,500 Sakārtošanas daļa saraksts sastāv no 4, 8 un 15, un 89 00:04:30,500 --> 00:04:33,210 šie elementi joprojām nešķirotu. 90 00:04:33,210 --> 00:04:36,900 Bet tas tikai tā notiek, ka nākamais nešķirotu elements, 16, 91 00:04:36,900 --> 00:04:38,480 jau sakārtots. 92 00:04:38,480 --> 00:04:42,060 Tomēr, tur nav veids, kā mūsu algoritms zināt, ka 16 93 00:04:42,060 --> 00:04:45,230 jau to pareizajā vietā, tāpēc mums vēl ir nepieciešams, lai 94 00:04:45,230 --> 00:04:47,870 atkārtot tieši to pašu procesu. 95 00:04:47,870 --> 00:04:53,750 Tātad mēs redzam, ka 16 ir mazāk nekā 42, un 16 ir mazāk nekā 23, tāpēc 96 00:04:53,750 --> 00:04:56,230 16 jābūt vismaz elements. 97 00:04:56,230 --> 00:04:59,010 Tas ir neiespējami apmainīt šo elementu ar sevi, lai mēs varam 98 00:04:59,010 --> 00:05:01,780 vienkārši atstāt to šajā vietā. 99 00:05:01,780 --> 00:05:04,660 Tāpēc mums ir nepieciešams vēl vienu piespēli no mūsu algoritms. 100 00:05:04,660 --> 00:05:09,370 42 ir lielāks par 23, tāpēc 23 ir jābūt 101 00:05:09,370 --> 00:05:10,970 Minimālā nešķiroti elements. 102 00:05:10,970 --> 00:05:17,410 Kad mēs mijmaiņas 23 un 42, mēs galu galā ar mūsu gala 103 00:05:17,410 --> 00:05:18,530 sakārtoti sarakstā - 104 00:05:18,530 --> 00:05:23,390 4, 8, 15, 16, 23, 42. 105 00:05:23,390 --> 00:05:26,830 Mēs zinām, 42 ir jābūt pareizajā vietā, jo tas ir 106 00:05:26,830 --> 00:05:30,210 Vienīgais elements kreisi, un tas ir izvēle veida. 107 00:05:30,210 --> 00:05:32,100 Pieņemsim tagad formalizēt mūsu algoritms ar dažām 108 00:05:32,100 --> 00:05:34,540 pseudocode. 109 00:05:34,540 --> 00:05:37,760 Vienā rindā, mēs varam redzēt, ka mums ir nepieciešams integrēt pār 110 00:05:37,760 --> 00:05:39,530 katrs elements sarakstā. 111 00:05:39,530 --> 00:05:42,150 Izņemot pēdējo elementu, jo 1 elements 112 00:05:42,150 --> 00:05:44,230 Saraksts ir jau sakārtots. 113 00:05:44,230 --> 00:05:48,100 Uz diviem līnijas, mēs uzskatām pirmo elementu nešķirotiem 114 00:05:48,100 --> 00:05:51,080 daļa sarakstā ir minimālais, kā mēs to darījām ar mūsu 115 00:05:51,080 --> 00:05:53,750 Piemēram, lai mēs kaut ko salīdzināt ar. 116 00:05:53,750 --> 00:05:57,260 Līnija 3 sāk otru cilpu, kurā mēs atkārtot pāri 117 00:05:57,260 --> 00:05:59,170 Katru nešķiroti elements. 118 00:05:59,170 --> 00:06:02,150 Mēs zinām, ka pēc tam es iterācijās, sakārtoti daļa 119 00:06:02,150 --> 00:06:05,330 Mūsu sarakstā ir jābūt i elementi tajā kopš katra soļa 120 00:06:05,330 --> 00:06:06,890 sakārto viens elements. 121 00:06:06,890 --> 00:06:11,770 Tātad pirmais nešķiroti elementam jābūt tādā stāvoklī, es plus 1. 122 00:06:11,770 --> 00:06:15,440 Uz četriem līniju, mēs salīdzināt pašreizējo elementu līdz minimumam 123 00:06:15,440 --> 00:06:17,750 elements, ka mēs esam redzējuši līdz šim. 124 00:06:17,750 --> 00:06:20,560 Ja pašreizējais elements ir mazāks par minimālo 125 00:06:20,560 --> 00:06:23,870 elements, tad mēs atcerēties esošo elements, jo jaunais 126 00:06:23,870 --> 00:06:26,250 Minimālā uz pieciem rindā. 127 00:06:26,250 --> 00:06:29,900 Visbeidzot, uz līnijām seši un septiņi, mēs swap minimālo 128 00:06:29,900 --> 00:06:33,080 elements ar pirmo nešķirotu elementa, tādējādi 129 00:06:33,080 --> 00:06:36,990 pievienojot to sakārtoti daļu sarakstu. 130 00:06:36,990 --> 00:06:40,030 Kad mums ir algoritms, svarīgs jautājums, ko uzdot 131 00:06:40,030 --> 00:06:43,370 sevi par programmētāju, cik ilgi tas veic? 132 00:06:43,370 --> 00:06:46,970 Mēs vispirms uzdot jautājumu, cik ilgi tas veic, lai šis 133 00:06:46,970 --> 00:06:50,070 algoritms, lai palaistu sliktākajā gadījumā? 134 00:06:50,070 --> 00:06:51,640 Atceros mēs pārstāvam šo darbību 135 00:06:51,640 --> 00:06:55,060 laiks ar Big O notācija. 136 00:06:55,060 --> 00:06:58,650 Lai noteiktu minimālo nešķirotu elementu, mēs 137 00:06:58,650 --> 00:07:01,880 būtībā bija salīdzināt katru elementu sarakstā uz 138 00:07:01,880 --> 00:07:04,040 katru otro elementu sarakstā. 139 00:07:04,040 --> 00:07:08,430 Intuitīvi, tas izklausās n brusas darbības O. 140 00:07:08,430 --> 00:07:12,050 Skatoties uz mūsu pseudocode, mums ir arī cilpa ligzdotas 141 00:07:12,050 --> 00:07:14,420 cits cilpa, kas tiešām izklausās O 142 00:07:14,420 --> 00:07:16,480 gada n brusas darbību. 143 00:07:16,480 --> 00:07:19,250 Tomēr atcerieties, ka mums nav nepieciešams apskatīt 144 00:07:19,250 --> 00:07:23,460 viss saraksts, nosakot minimālo nešķirotu elements? 145 00:07:23,460 --> 00:07:26,600 Kad mēs zinājām, ka 4 tika sakārtoti, piemēram, mums nav 146 00:07:26,600 --> 00:07:28,170 vajag paskatīties uz to vēlreiz. 147 00:07:28,170 --> 00:07:31,020 Tātad dara zemākas darbības laiku? 148 00:07:31,020 --> 00:07:34,510 Mūsu sarakstu 6 garums, mums vajadzēja padarīt piecas 149 00:07:34,510 --> 00:07:37,990 salīdzinājumi par pirmo elementu, četras salīdzinājumus 150 00:07:37,990 --> 00:07:40,750 Otrais elements, un tā tālāk. 151 00:07:40,750 --> 00:07:44,690 Tas nozīmē, ka kopējais skaits soļiem ir summa 152 00:07:44,690 --> 00:07:49,160 integers no 1 līdz garumā saraksta mīnus 1. 153 00:07:49,160 --> 00:07:51,005 Mēs varam pārstāvēt šo ar summēšanā. 154 00:07:57,980 --> 00:07:59,910 Mēs ne iedziļināties summations šeit. 155 00:07:59,910 --> 00:08:04,900 Bet izrādās, ka tas sasummēt ir vienāds ar n reizes 156 00:08:04,900 --> 00:08:07,540 n mīnus nekā 2 1. 157 00:08:07,540 --> 00:08:14,220 Vai līdzvērtīgi, n rūtiņām vairāk nekā 2 mīnus n nekā 2. 158 00:08:14,220 --> 00:08:18,860 Ja runājam par asimptotiskās runtime, šis n brusas termins 159 00:08:18,860 --> 00:08:22,070 gatavojas dominēt šo n terminu. 160 00:08:22,070 --> 00:08:27,850 Tātad izvēle veida ir O no n rūtiņām. 161 00:08:27,850 --> 00:08:31,460 Atgādināt, ka mūsu piemēram, atlase kārtot vēl vajag 162 00:08:31,460 --> 00:08:33,850 pārbaudiet, vai numurs, kas bija jau sakārtoti 163 00:08:33,850 --> 00:08:35,450 nepieciešams pārvietot. 164 00:08:35,450 --> 00:08:38,929 Tātad tas nozīmē, ka, ja mēs ilga atlases veida pār jau 165 00:08:38,929 --> 00:08:43,070 sakārtoti sarakstā, tas būs nepieciešams tas pats vairākus pasākumus, kā to 166 00:08:43,070 --> 00:08:46,340 būtu braucot pa pilnīgi nešķirotiem sarakstā. 167 00:08:46,340 --> 00:08:51,470 Tātad izvēle šķirot ir labākajā gadījumā sniegumu n brusas, 168 00:08:51,470 --> 00:08:56,820 kas mēs pārstāvam ar omega n brusas. 169 00:08:56,820 --> 00:08:58,600 Un tas ir tas, lai atlases veida. 170 00:08:58,600 --> 00:09:00,630 Tikai viens no daudziem algoritmu mēs varam 171 00:09:00,630 --> 00:09:02,390 izmantot, lai kārtotu sarakstu. 172 00:09:02,390 --> 00:09:05,910 Mans vārds ir Tommy, un tas ir CS50.