1 00:00:06,762 --> 00:00:09,980 [Powered by Google Translate] TOMMY: Ligeann a ghlacadh le breathnú ar saghas a roghnú, algartaim 2 00:00:09,980 --> 00:00:12,800 as liosta d'uimhreacha agus sórtáil leo. 3 00:00:12,800 --> 00:00:15,750 Tá algartam, cuimhnigh, ach céim-ar-chéim 4 00:00:15,750 --> 00:00:18,370 nós imeachta maidir le accomplishing tasc. 5 00:00:18,370 --> 00:00:21,470 Is é an smaoineamh bunúsach taobh thiar de chineál roghnaithe a roinnt 6 00:00:21,470 --> 00:00:23,390 ár liosta ina dhá chuid - 7 00:00:23,390 --> 00:00:26,810 cuid curtha in eagar agus cuid neamhshórtáilte. 8 00:00:26,810 --> 00:00:30,200 Ag gach céim den algartam, tá roinnt ar athraíodh a ionad as an 9 00:00:30,200 --> 00:00:33,800 chuid neamhshórtáilte leis an gcuid curtha in eagar go dtí deireadh an 10 00:00:33,800 --> 00:00:35,880 Tá liosta iomlán curtha in eagar. 11 00:00:35,880 --> 00:00:38,510 Mar sin, tá anseo liosta de na sé uimhir - 12 00:00:38,510 --> 00:00:44,010 23, 42, 4, 16, 8, agus 15. 13 00:00:44,010 --> 00:00:47,680 Ceart anois go bhfuil an liosta iomlán a mheas neamhshórtáilte. 14 00:00:47,680 --> 00:00:51,770 Cé go d'fhéadfadh roinnt mhaith 16 cheana féin ina ceart 15 00:00:51,770 --> 00:00:56,040 suíomh, tá ár algartam aon bhealach a fhios agam go dtí go mbeidh an 16 00:00:56,040 --> 00:00:57,980 Tá liosta iomlán curtha in eagar. 17 00:00:57,980 --> 00:01:01,355 Mar sin, beidh muid ag smaoineamh ar gach uimhir a neamhshórtáilte go dtí go againn a shórtáil 18 00:01:01,355 --> 00:01:03,800 é féin. 19 00:01:03,800 --> 00:01:06,890 Tá a fhios againn gur mian linn an liosta a bheith in ord ardaitheach. 20 00:01:06,890 --> 00:01:10,200 Mar sin, beidh muid ag iarraidh a thógáil suas an chuid eagar ar ár liosta 21 00:01:10,200 --> 00:01:13,280 ó chlé go deas, is lú go dtí mó. 22 00:01:13,280 --> 00:01:17,970 Chun é sin a dhéanamh, beidh orainn a fháil ar an ghné íosta neamhshórtáilte 23 00:01:17,970 --> 00:01:21,350 agus é a chur ag deireadh na coda in eagar. 24 00:01:21,350 --> 00:01:25,370 Ós rud é nach bhfuil an liosta seo curtha in eagar, is é an bealach amháin chun é sin a dhéanamh go 25 00:01:25,370 --> 00:01:29,330 breathnú ar gach gné sa chuid neamhshórtáilte, cuimhneamh 26 00:01:29,330 --> 00:01:32,010 a bhfuil gné is ísle agus comparáid a dhéanamh 27 00:01:32,010 --> 00:01:33,770 gach gné leis sin. 28 00:01:33,770 --> 00:01:36,150 Mar sin, beidh muid ag breathnú ar dtús ag an 23. 29 00:01:36,150 --> 00:01:38,650 Is é seo an chéad eilimint againn le feiceáil, mar sin beidh muid ag cuimhneamh 30 00:01:38,650 --> 00:01:40,050 sé mar an t-íosmhéid. 31 00:01:40,050 --> 00:01:42,320 Next beidh muid ag breathnú ar 42. 32 00:01:42,320 --> 00:01:46,720 42 Tá níos mó ná 23, mar sin tá 23 fós ar an íosmhéid. 33 00:01:46,720 --> 00:01:51,210 Ansin, 4 atá níos lú ná 23, mar sin beidh muid ag cuimhneamh 4 34 00:01:51,210 --> 00:01:52,880 mar an t-íosmhéid nua. 35 00:01:52,880 --> 00:01:56,380 Tá Next 16 a bhfuil níos mó ná 4, agus mar sin 4 36 00:01:56,380 --> 00:01:57,980 tá sé fós an t-íosmhéid. 37 00:01:57,980 --> 00:02:03,670 8 Tá níos mó ná 4, agus 15 is mó ná 4, mar sin ní mór 4 a bheith 38 00:02:03,670 --> 00:02:05,980 an ghné is lú neamhshórtáilte. 39 00:02:05,980 --> 00:02:09,350 Mar sin, cé mar dhaoine féidir linn a fheiceáil láithreach go bhfuil 4 40 00:02:09,350 --> 00:02:12,300 an eilimint is lú, is gá ár n-algartam chun breathnú ar 41 00:02:12,300 --> 00:02:15,710 gach gné neamhshórtáilte, fiú tar éis againn fuair an 4 - an 42 00:02:15,710 --> 00:02:16,860 eilimint íosta. 43 00:02:16,860 --> 00:02:19,900 Mar sin anois go atá againn fuair an ghné íosta, 4, beidh muid ag iarraidh 44 00:02:19,900 --> 00:02:23,410 a bhogadh isteach sa chuid curtha in eagar ar an liosta. 45 00:02:23,410 --> 00:02:27,320 Ós rud é seo an chéad chéim, ciallaíonn sé seo ba mhaith linn a chur ar 4 ag 46 00:02:27,320 --> 00:02:29,680 tús an liosta. 47 00:02:29,680 --> 00:02:33,040 Ceart anois tá 23 ag tús an liosta, agus mar sin 48 00:02:33,040 --> 00:02:36,080 a ligean ar mhalartú an 4 agus an 23. 49 00:02:36,080 --> 00:02:38,870 Mar sin, anois tá ár liosta mar seo. 50 00:02:38,870 --> 00:02:42,710 Tá a fhios againn nach mór 4 a bheith ina suíomh deiridh, toisc go bhfuil sé 51 00:02:42,710 --> 00:02:45,890 an eilimint is lú agus an ghné ag an tús 52 00:02:45,890 --> 00:02:46,960 an liosta. 53 00:02:46,960 --> 00:02:50,650 Mar sin, ciallaíonn sé seo go ní mór dúinn riamh a bhogadh arís. 54 00:02:50,650 --> 00:02:53,910 Mar sin a ligean arís an próiseas seo go dtí ceann eile eilimint a chur leis an 55 00:02:53,910 --> 00:02:55,910 chuid curtha in eagar ar an liosta. 56 00:02:55,910 --> 00:02:58,950 Tá a fhios againn nach mór dúinn chun breathnú ar an 4, mar tá sé 57 00:02:58,950 --> 00:03:00,000 atá sórtáilte cheana. 58 00:03:00,000 --> 00:03:03,540 Mar sin, is féidir linn tús a chur ag 42, a beidh orainn a mheabhrú mar an 59 00:03:03,540 --> 00:03:05,290 eilimint íosta. 60 00:03:05,290 --> 00:03:08,700 Mar sin, seo chugainn beidh muid ag breathnú ar na 23 atá níos lú ná 42, mar sin againn 61 00:03:08,700 --> 00:03:11,620 cuimhneamh 23 Is é an t-íosmhéid nua. 62 00:03:11,620 --> 00:03:14,870 Next feicimid an 16 atá níos lú ná 23, agus mar sin 63 00:03:14,870 --> 00:03:16,800 Is é 16 an t-íosmhéid nua. 64 00:03:16,800 --> 00:03:19,720 Anois táimid ag breathnú ar na 8 atá níos lú ná 16, agus mar sin 65 00:03:19,720 --> 00:03:21,130 Is é 8 an t-íosmhéid nua. 66 00:03:21,130 --> 00:03:25,900 Agus is é ar deireadh 8 níos lú ná 15, agus mar sin tá a fhios againn go bhfuil 8 ar a laghad 67 00:03:25,900 --> 00:03:27,780 eilimint neamhshórtáilte. 68 00:03:27,780 --> 00:03:30,660 Mar sin, Ciallaíonn sé sin go mba cheart dúinn 8 fhoscríbhinn leis an eagar 69 00:03:30,660 --> 00:03:32,450 chuid den liosta. 70 00:03:32,450 --> 00:03:35,990 Ceart anois tá 4 an eilimint amháin a shórtáil, mar sin ba mhaith linn a chur 71 00:03:35,990 --> 00:03:38,410 an chéad cheann eile 8 ar an 4. 72 00:03:38,410 --> 00:03:41,920 Ós rud é 42 an chéad eilimint sa chuid neamhshórtáilte an 73 00:03:41,920 --> 00:03:47,260 liosta, beidh muid ag iarraidh a mhalartú ar an 42 agus an 8. 74 00:03:47,260 --> 00:03:49,680 Mar sin, anois tá ár liosta mar seo. 75 00:03:49,680 --> 00:03:53,830 4 agus 8 ionadaíocht a dhéanamh ar an chuid curtha in eagar ar an liosta, agus an 76 00:03:53,830 --> 00:03:56,440 ionadaíocht a dhéanamh ar líon na fágtha ar an neamhshórtáilte 77 00:03:56,440 --> 00:03:58,260 chuid den liosta. 78 00:03:58,260 --> 00:04:00,630 Mar sin a ligean ar aghaidh le chéile leagan. 79 00:04:00,630 --> 00:04:03,850 Tús a chur againn le 23 an am seo, ós rud é nach mór dúinn chun breathnú ar 80 00:04:03,850 --> 00:04:05,770 an 4 agus an 8 níos mó mar tá siad 81 00:04:05,770 --> 00:04:07,660 curtha in eagar cheana féin. 82 00:04:07,660 --> 00:04:10,270 Is é 16 níos lú ná 23, mar sin beidh muid ag cuimhneamh 83 00:04:10,270 --> 00:04:12,070 16 mar an t-íosmhéid nua. 84 00:04:12,070 --> 00:04:18,149 Is é 16 níos lú ná 42, ach 15 níos lú ná 16, mar sin ní mór 15 a bheith 85 00:04:18,149 --> 00:04:20,480 an ghné íosta neamhshórtáilte. 86 00:04:20,480 --> 00:04:24,580 Mar sin, anois ba mhaith linn a mhalartú ar an 15 agus an 23 go 87 00:04:24,580 --> 00:04:26,310 a thabhairt dúinn an liosta seo. 88 00:04:26,310 --> 00:04:30,500 Is éard atá sa chuid curtha in eagar ar an liosta de 4, 8 agus 15, agus 89 00:04:30,500 --> 00:04:33,210 na heilimintí neamhshórtáilte go fóill. 90 00:04:33,210 --> 00:04:36,900 Ach a tharlaíonn sé ach ionas go mbeidh an ghné seo chugainn neamhshórtáilte, 16, 91 00:04:36,900 --> 00:04:38,480 Tá curtha in eagar cheana féin. 92 00:04:38,480 --> 00:04:42,060 Mar sin féin, níl aon bhealach le haghaidh ár algartam a fhios go 16 93 00:04:42,060 --> 00:04:45,230 cheana féin a shuíomh i gceart, mar sin ní mór dúinn fós 94 00:04:45,230 --> 00:04:47,870 arís go díreach leis an bpróiseas céanna. 95 00:04:47,870 --> 00:04:53,750 Mar sin, linn a fheiceáil go bhfuil 16 níos lú ná 42, agus 16 níos lú ná 23, agus mar sin 96 00:04:53,750 --> 00:04:56,230 Ní mór a bheith 16 an eilimint is lú. 97 00:04:56,230 --> 00:04:59,010 Tá sé dodhéanta a mhalartú ngné seo leis féin, ionas gur féidir linn 98 00:04:59,010 --> 00:05:01,780 ach é a fhágáil san áit seo. 99 00:05:01,780 --> 00:05:04,660 Mar sin, ní mór dúinn pas amháin níos mó ar ár algartam. 100 00:05:04,660 --> 00:05:09,370 42 níos mó ná 23, mar sin ní mór a bheith 23 ar an 101 00:05:09,370 --> 00:05:10,970 eilimint neamhshórtáilte íosta. 102 00:05:10,970 --> 00:05:17,410 Chomh luath agus táimid ag mhalartú an 23 agus an 42, ní mór dúinn deireadh suas le lenár deiridh 103 00:05:17,410 --> 00:05:18,530 liosta in eagar - 104 00:05:18,530 --> 00:05:23,390 4, 8, 15, 16, 23, 42. 105 00:05:23,390 --> 00:05:26,830 Tá a fhios againn ní mór a bheith 42 san áit cheart ó tá sé an 106 00:05:26,830 --> 00:05:30,210 eilimint amháin ar chlé, agus sin an saghas roghnaithe. 107 00:05:30,210 --> 00:05:32,100 A ligean ar bhonn foirmiúil anois ar ár algartam le roinnt 108 00:05:32,100 --> 00:05:34,540 pseudocode. 109 00:05:34,540 --> 00:05:37,760 Ar líne amháin, is féidir linn a fheiceáil go bhfuil gá le comhtháthú níos mó 110 00:05:37,760 --> 00:05:39,530 gach gné den liosta. 111 00:05:39,530 --> 00:05:42,150 Ach amháin an ghné dheireanach, ós rud é an eilimint 1 112 00:05:42,150 --> 00:05:44,230 liosta in eagar cheana féin. 113 00:05:44,230 --> 00:05:48,100 Ar líne beirt, ní mór dúinn a mheas an chéad ghné den neamhshórtáilte 114 00:05:48,100 --> 00:05:51,080 an chuid sin den liosta go dtí an íosmhéid, mar a rinne muid lenár 115 00:05:51,080 --> 00:05:53,750 Mar shampla, ionas go mbeidh muid rud éigin a chur i gcomparáid le. 116 00:05:53,750 --> 00:05:57,260 Tosaíonn Líne trí lúb dara ina ndéanaimid iterate thar 117 00:05:57,260 --> 00:05:59,170 gach gné neamhshórtáilte. 118 00:05:59,170 --> 00:06:02,150 Tá a fhios againn gur tar éis i atriallta, an chuid in eagar 119 00:06:02,150 --> 00:06:05,330 Ní mór ar ár liosta ag dúile i ann ó gach céim 120 00:06:05,330 --> 00:06:06,890 cineál gné amháin. 121 00:06:06,890 --> 00:06:11,770 Mar sin, ní mór an chéad eilimint neamhshórtáilte a bheith i riocht i móide 1. 122 00:06:11,770 --> 00:06:15,440 Ar líne ceithre, comparáid idir an eilimint atá ann faoi láthair leis an íosmhéid 123 00:06:15,440 --> 00:06:17,750 eilimint go atá feicthe againn go dtí seo. 124 00:06:17,750 --> 00:06:20,560 Má tá an eilimint atá ann faoi láthair níos lú ná an íosmhéid 125 00:06:20,560 --> 00:06:23,870 eilimint, ansin cuimhin linn an eilimint atá ann faoi láthair mar an nua 126 00:06:23,870 --> 00:06:26,250 laghad ar líne a cúig. 127 00:06:26,250 --> 00:06:29,900 Mar fhocal scoir, ar línte sé agus seacht, babhtála muid an t-íosmhéid 128 00:06:29,900 --> 00:06:33,080 eilimint leis an chéad eilimint neamhshórtáilte, rud a 129 00:06:33,080 --> 00:06:36,990 ag cur sé leis an bpáirt curtha in eagar ar an liosta. 130 00:06:36,990 --> 00:06:40,030 Nuair a bheidh againn algartaim, ar cheist thábhachtach a iarraidh 131 00:06:40,030 --> 00:06:43,370 féin is a ríomhchláraitheoirí cé chomh fada raibh a ghlacadh? 132 00:06:43,370 --> 00:06:46,970 Beidh muid a iarraidh ar dtús leis an cheist cé chomh fada a thógfaidh sé ar an 133 00:06:46,970 --> 00:06:50,070 algartam a reáchtáil i gcás is measa? 134 00:06:50,070 --> 00:06:51,640 Cuimhin ionadaíocht againn seo a rith 135 00:06:51,640 --> 00:06:55,060 am le nodaireacht O mór. 136 00:06:55,060 --> 00:06:58,650 D'fhonn a chinneadh an ghné íosta neamhshórtáilte, ní mór dúinn 137 00:06:58,650 --> 00:07:01,880 go bunúsach go raibh a chur i gcomparáid gach eilimint sa liosta a 138 00:07:01,880 --> 00:07:04,040 gach gné eile ar an liosta. 139 00:07:04,040 --> 00:07:08,430 Intuitively, fuaimeanna seo cosúil le O oibríochta n cearnógach. 140 00:07:08,430 --> 00:07:12,050 Ag Breathnú ar an pseudocode, ní mór dúinn freisin lúb neadaithe taobh istigh 141 00:07:12,050 --> 00:07:14,420 eile lúb, a fuaimeanna go deimhin, cosúil le O 142 00:07:14,420 --> 00:07:16,480 n oibríocht cearnógach. 143 00:07:16,480 --> 00:07:19,250 Mar sin féin, cuimhnigh nach raibh muid gá chun breathnú ar an 144 00:07:19,250 --> 00:07:23,460 liosta iomlán nuair a chinneadh an ghné íosta neamhshórtáilte? 145 00:07:23,460 --> 00:07:26,600 Chomh luath agus a fhios againn go raibh curtha in eagar an 4, mar shampla, ní raibh muid 146 00:07:26,600 --> 00:07:28,170 Ní mór chun breathnú ar sé arís. 147 00:07:28,170 --> 00:07:31,020 Mar sin, a dhéanann an níos ísle ar an t-am ag rith? 148 00:07:31,020 --> 00:07:34,510 Chun ár liosta de fhad 6, is gá dúinn a dhéanamh ar chúig 149 00:07:34,510 --> 00:07:37,990 comparáidí le haghaidh an chéad eilimint, ceithre comparáidí le haghaidh 150 00:07:37,990 --> 00:07:40,750 an dara gné, agus mar sin de. 151 00:07:40,750 --> 00:07:44,690 Ciallaíonn sé sin go bhfuil líon iomlán na céimeanna agus suim 152 00:07:44,690 --> 00:07:49,160 na slánuimhreacha ó 1 go dtí fad an liosta lúide 1. 153 00:07:49,160 --> 00:07:51,005 Is féidir linn seo a léiriú le go léir a shuimiú. 154 00:07:57,980 --> 00:07:59,910 Ní féidir linn dul i summations anseo. 155 00:07:59,910 --> 00:08:04,900 Ach casadh sé amach go bhfuil an tsuimithe cothrom le hamanna n 156 00:08:04,900 --> 00:08:07,540 n lúide 1 níos mó ná 2. 157 00:08:07,540 --> 00:08:14,220 Nó equivalently, n cearnaithe níos mó ná 2 lúide n níos mó ná 2. 158 00:08:14,220 --> 00:08:18,860 Nuair a labhairt faoi runtime asymptotic, an téarma n cearnógach 159 00:08:18,860 --> 00:08:22,070 ag dul a tionchar an-mhór an téarma n. 160 00:08:22,070 --> 00:08:27,850 Dá bhrí sin tá saghas roghnú O n cearnógach. 161 00:08:27,850 --> 00:08:31,460 Glaoch ar ais go in ár mar shampla, is gá saghas rogha fós 162 00:08:31,460 --> 00:08:33,850 seiceáil má uimhir a bhí curtha in eagar cheana 163 00:08:33,850 --> 00:08:35,450 is gá chun a bhogadh. 164 00:08:35,450 --> 00:08:38,929 Mar sin, go Ciallaíonn sé sin má bhí ar siúl againn saghas roghnú thar cheana 165 00:08:38,929 --> 00:08:43,070 in eagar liosta, bheadh ​​sé a cheangal ar an líon céanna céimeanna mar a 166 00:08:43,070 --> 00:08:46,340 a bheadh ​​á reáchtáil thar liosta go hiomlán neamhshórtáilte. 167 00:08:46,340 --> 00:08:51,470 Mar sin, tá saghas roghnú ar fheidhmíocht gcás is fearr de n cearnógach, 168 00:08:51,470 --> 00:08:56,820 a dhéanann ionadaíocht againn le óimige n cearnógach. 169 00:08:56,820 --> 00:08:58,600 Agus sin é do saghas roghnaithe. 170 00:08:58,600 --> 00:09:00,630 Ach ceann amháin de na halgartaim a lán is féidir linn 171 00:09:00,630 --> 00:09:02,390 úsáid a shórtáil liosta. 172 00:09:02,390 --> 00:09:05,910 Is é mo ainm Tommy, agus tá sé seo cs50.