1
00:00:06,762 --> 00:00:09,980
[Powered by Google Translate] TOMMY: Mari kita lihat pada pemilihan apapun, algoritma

2
00:00:09,980 --> 00:00:12,800
untuk mengambil senarai nombor dan menyusun mereka.

3
00:00:12,800 --> 00:00:15,750
Algoritma, ingat, adalah hanya langkah-demi-langkah

4
00:00:15,750 --> 00:00:18,370
prosedur untuk mencapai tugas.

5
00:00:18,370 --> 00:00:21,470
Idea asas di sebalik apapun pemilihan adalah untuk membahagi

6
00:00:21,470 --> 00:00:23,390
kami senarai kepada dua bahagian -

7
00:00:23,390 --> 00:00:26,810
sebahagian disusun dan bahagian Unsorted.

8
00:00:26,810 --> 00:00:30,200
Pada setiap langkah algoritma, nombor dipindahkan dari

9
00:00:30,200 --> 00:00:33,800
bahagian Unsorted bahagian disusun sehingga akhirnya

10
00:00:33,800 --> 00:00:35,880
senarai keseluruhan disusun.

11
00:00:35,880 --> 00:00:38,510
Jadi di sini adalah senarai enam nombor -

12
00:00:38,510 --> 00:00:44,010
23, 42, 4, 16, 8, dan 15.

13
00:00:44,010 --> 00:00:47,680
Sekarang seluruh senarai dianggap Unsorted.

14
00:00:47,680 --> 00:00:51,770
Walaupun beberapa seperti 16 mungkin sudah betul

15
00:00:51,770 --> 00:00:56,040
lokasi, algoritma kami tidak mempunyai cara untuk mengetahui bahawa sehingga

16
00:00:56,040 --> 00:00:57,980
senarai keseluruhan disusun.

17
00:00:57,980 --> 00:01:01,355
Jadi kita akan mempertimbangkan setiap nombor untuk Unsorted sehingga kita menyelesaikan

18
00:01:01,355 --> 00:01:03,800
sendiri.

19
00:01:03,800 --> 00:01:06,890
Kita tahu bahawa kita mahu senarai itu berada dalam susunan menaik.

20
00:01:06,890 --> 00:01:10,200
Jadi kita akan mahu untuk membina bahagian disusun senarai kami

21
00:01:10,200 --> 00:01:13,280
dari kiri ke kanan, terkecil hingga terbesar.

22
00:01:13,280 --> 00:01:17,970
Untuk berbuat demikian, kita perlu mencari elemen Unsorted minimum

23
00:01:17,970 --> 00:01:21,350
dan meletakkan ia pada akhir bahagian disusun.

24
00:01:21,350 --> 00:01:25,370
Sejak senarai ini tidak diselesaikan, satu-satunya cara untuk berbuat demikian adalah untuk

25
00:01:25,370 --> 00:01:29,330
melihat setiap elemen di bahagian Unsorted, mengingat

26
00:01:29,330 --> 00:01:32,010
mana unsur yang terendah dan membandingkan

27
00:01:32,010 --> 00:01:33,770
setiap elemen itu.

28
00:01:33,770 --> 00:01:36,150
Jadi kita mula-mula akan melihat pada 23.

29
00:01:36,150 --> 00:01:38,650
Ini adalah elemen pertama yang kita telah melihat, jadi kita akan ingat

30
00:01:38,650 --> 00:01:40,050
sebagai minimum.

31
00:01:40,050 --> 00:01:42,320
Seterusnya kita akan melihat pada 42.

32
00:01:42,320 --> 00:01:46,720
42 adalah lebih besar daripada 23, jadi 23 masih minimum.

33
00:01:46,720 --> 00:01:51,210
Berikut adalah 4 yang kurang dari 23, jadi kita akan ingat 4

34
00:01:51,210 --> 00:01:52,880
sebagai minimum baru.

35
00:01:52,880 --> 00:01:56,380
Berikut adalah 16 yang lebih besar daripada 4, jadi 4

36
00:01:56,380 --> 00:01:57,980
masih minimum.

37
00:01:57,980 --> 00:02:03,670
8 adalah lebih besar daripada 4, dan 15 adalah lebih besar daripada 4, jadi 4 mestilah

38
00:02:03,670 --> 00:02:05,980
elemen Unsorted terkecil.

39
00:02:05,980 --> 00:02:09,350
Jadi walaupun sebagai manusia kita segera boleh melihat bahawa 4 adalah

40
00:02:09,350 --> 00:02:12,300
elemen minimum, algoritma kami perlu melihat

41
00:02:12,300 --> 00:02:15,710
setiap elemen Unsorted, walaupun selepas kita dapati 4 -

42
00:02:15,710 --> 00:02:16,860
elemen minimum.

43
00:02:16,860 --> 00:02:19,900
Jadi sekarang kita dapati unsur minimum, 4, kita akan mahu

44
00:02:19,900 --> 00:02:23,410
untuk bergerak ke bahagian disusun senarai.

45
00:02:23,410 --> 00:02:27,320
Sejak ini adalah langkah pertama, ini bermakna kita mahu meletakkan 4 pada

46
00:02:27,320 --> 00:02:29,680
permulaan senarai.

47
00:02:29,680 --> 00:02:33,040
Sekarang 23 adalah pada awal senarai, jadi

48
00:02:33,040 --> 00:02:36,080
mari kita swap 4 dan 23.

49
00:02:36,080 --> 00:02:38,870
Jadi sekarang senarai kami kelihatan seperti ini.

50
00:02:38,870 --> 00:02:42,710
Kita tahu bahawa 4 mesti berada di lokasi terakhir, kerana ia adalah

51
00:02:42,710 --> 00:02:45,890
kedua-dua elemen terkecil dan elemen pada permulaan

52
00:02:45,890 --> 00:02:46,960
senarai.

53
00:02:46,960 --> 00:02:50,650
Jadi ini bermakna bahawa kita tidak pernah perlu untuk bergerak lagi.

54
00:02:50,650 --> 00:02:53,910
Jadi mari kita mengulangi proses ini untuk menambah elemen lain untuk

55
00:02:53,910 --> 00:02:55,910
bahagian yang disusun senarai.

56
00:02:55,910 --> 00:02:58,950
Kita tahu bahawa kita tidak perlu melihat pada 4, kerana ia

57
00:02:58,950 --> 00:03:00,000
sudah disusun.

58
00:03:00,000 --> 00:03:03,540
Jadi, kita boleh mula pada 42, yang kita akan ingat sebagai

59
00:03:03,540 --> 00:03:05,290
elemen minimum.

60
00:03:05,290 --> 00:03:08,700
Jadi seterusnya kita akan melihat 23 yang mana adalah kurang dari 42, jadi kita

61
00:03:08,700 --> 00:03:11,620
ingat 23 adalah minimum yang baru.

62
00:03:11,620 --> 00:03:14,870
Seterusnya kita lihat 16 yang kurang daripada 23, jadi

63
00:03:14,870 --> 00:03:16,800
16 adalah minimum yang baru.

64
00:03:16,800 --> 00:03:19,720
Sekarang kita lihat pada 8 yang adalah kurang daripada 16, jadi

65
00:03:19,720 --> 00:03:21,130
8 adalah minimum yang baru.

66
00:03:21,130 --> 00:03:25,900
Dan akhirnya 8 adalah kurang dari 15, jadi kita tahu bahawa 8 adalah minimum

67
00:03:25,900 --> 00:03:27,780
elemen Unsorted.

68
00:03:27,780 --> 00:03:30,660
Jadi itu bermakna kita harus melampirkan 8 yang diisih

69
00:03:30,660 --> 00:03:32,450
sebahagian daripada senarai.

70
00:03:32,450 --> 00:03:35,990
Sekarang 4 adalah elemen hanya disusun, jadi kita mahu ke tempat

71
00:03:35,990 --> 00:03:38,410
seterusnya 8 ke 4,.

72
00:03:38,410 --> 00:03:41,920
Sejak 42 adalah elemen pertama dalam bahagian Unsorted daripada

73
00:03:41,920 --> 00:03:47,260
senarai, kita akan mahu menukar 42 dan 8.

74
00:03:47,260 --> 00:03:49,680
Jadi sekarang senarai kami kelihatan seperti ini.

75
00:03:49,680 --> 00:03:53,830
4 dan 8 mewakili bahagian disusun senarai, dan

76
00:03:53,830 --> 00:03:56,440
baki nombor mewakili Unsorted

77
00:03:56,440 --> 00:03:58,260
sebahagian daripada senarai.

78
00:03:58,260 --> 00:04:00,630
Jadi mari kita terus dengan lelaran lain.

79
00:04:00,630 --> 00:04:03,850
Kita mulakan dengan 23 kali ini, kerana kita tidak perlu untuk melihat

80
00:04:03,850 --> 00:04:05,770
4 dan 8 yang lagi kerana mereka telah

81
00:04:05,770 --> 00:04:07,660
sudah disusun.

82
00:04:07,660 --> 00:04:10,270
16 adalah kurang daripada 23, jadi kita akan ingat

83
00:04:10,270 --> 00:04:12,070
16 sebagai minimum baru.

84
00:04:12,070 --> 00:04:18,149
16 adalah kurang daripada 42, tetapi 15 adalah kurang daripada 16, jadi 15 mesti

85
00:04:18,149 --> 00:04:20,480
elemen Unsorted minimum.

86
00:04:20,480 --> 00:04:24,580
Jadi sekarang kita mahu untuk menukar 15 dan 23 hingga

87
00:04:24,580 --> 00:04:26,310
memberikan kita senarai ini.

88
00:04:26,310 --> 00:04:30,500
Bahagian disusun senarai terdiri daripada 4, 8 dan 15, dan

89
00:04:30,500 --> 00:04:33,210
elemen-elemen ini masih Unsorted.

90
00:04:33,210 --> 00:04:36,900
Tetapi ia hanya kebetulan bahawa seterusnya elemen Unsorted, 16,

91
00:04:36,900 --> 00:04:38,480
sudah disusun.

92
00:04:38,480 --> 00:04:42,060
Walau bagaimanapun, ada cara untuk algoritma kami tahu bahawa 16

93
00:04:42,060 --> 00:04:45,230
sudah di lokasi yang betul, jadi kita masih perlu

94
00:04:45,230 --> 00:04:47,870
mengulangi tepat proses yang sama.

95
00:04:47,870 --> 00:04:53,750
Jadi kita lihat bahawa 16 adalah kurang daripada 42, dan 16 adalah kurang daripada 23, jadi

96
00:04:53,750 --> 00:04:56,230
16 mesti elemen minimum.

97
00:04:56,230 --> 00:04:59,010
Ia adalah mustahil untuk menukar elemen ini dengan sendiri, supaya kita boleh

98
00:04:59,010 --> 00:05:01,780
hanya tinggalkan ia di lokasi ini.

99
00:05:01,780 --> 00:05:04,660
Jadi kita perlu pas satu lagi algoritma kami.

100
00:05:04,660 --> 00:05:09,370
42 adalah lebih besar daripada 23, jadi 23 mestilah

101
00:05:09,370 --> 00:05:10,970
elemen Unsorted minimum.

102
00:05:10,970 --> 00:05:17,410
Apabila kita menukar 23 dan 42, kita berakhir dengan akhir kami

103
00:05:17,410 --> 00:05:18,530
senarai diisih -

104
00:05:18,530 --> 00:05:23,390
4, 8, 15, 16, 23, 42.

105
00:05:23,390 --> 00:05:26,830
Kita tahu 42 mesti berada di tempat yang betul kerana ia adalah

106
00:05:26,830 --> 00:05:30,210
elemen-satunya kiri, dan itulah apapun pemilihan.

107
00:05:30,210 --> 00:05:32,100
Mari kita sekarang merasmikan algoritma kami dengan beberapa

108
00:05:32,100 --> 00:05:34,540
kod pseudo.

109
00:05:34,540 --> 00:05:37,760
On line satu, kita boleh melihat bahawa kita perlu untuk mengintegrasikan lebih

110
00:05:37,760 --> 00:05:39,530
setiap elemen senarai.

111
00:05:39,530 --> 00:05:42,150
Kecuali elemen terakhir, kerana elemen 1

112
00:05:42,150 --> 00:05:44,230
senarai sudah disusun.

113
00:05:44,230 --> 00:05:48,100
On line dua, kita mempertimbangkan elemen pertama daripada Unsorted

114
00:05:48,100 --> 00:05:51,080
sebahagian daripada senarai untuk menjadi minimum, seperti yang kita lakukan dengan kita

115
00:05:51,080 --> 00:05:53,750
contoh, jadi kami mempunyai sesuatu untuk membandingkan.

116
00:05:53,750 --> 00:05:57,260
Talian ketiga bermula gelung kedua di mana kita melelar lebih

117
00:05:57,260 --> 00:05:59,170
setiap elemen Unsorted.

118
00:05:59,170 --> 00:06:02,150
Kita tahu bahawa selepas i lelaran, bahagian yang disusun

119
00:06:02,150 --> 00:06:05,330
senarai kami mesti mempunyai i elemen di dalamnya sejak setiap langkah

120
00:06:05,330 --> 00:06:06,890
macam satu elemen.

121
00:06:06,890 --> 00:06:11,770
Jadi elemen Unsorted pertama mestilah dalam kedudukan i campur 1.

122
00:06:11,770 --> 00:06:15,440
On line empat, kita bandingkan elemen semasa minimum

123
00:06:15,440 --> 00:06:17,750
elemen yang kita telah melihat setakat ini.

124
00:06:17,750 --> 00:06:20,560
Jika elemen semasa adalah lebih kecil daripada minimum

125
00:06:20,560 --> 00:06:23,870
unsur, maka kita ingat elemen semasa sebagai baru

126
00:06:23,870 --> 00:06:26,250
minimum kepada lima baris.

127
00:06:26,250 --> 00:06:29,900
Akhirnya, pada baris enam dan tujuh, kita swap minimum

128
00:06:29,900 --> 00:06:33,080
elemen dengan elemen Unsorted pertama, sekali gus

129
00:06:33,080 --> 00:06:36,990
menambah kepada bahagian disusun senarai.

130
00:06:36,990 --> 00:06:40,030
Apabila kita mempunyai algoritma, satu persoalan yang penting untuk bertanya

131
00:06:40,030 --> 00:06:43,370
diri kita sebagai pengaturcara berapa lama masa yang diambil?

132
00:06:43,370 --> 00:06:46,970
Kita mula-mula akan bertanya soalan berapa lama ia mengambil masa untuk ini

133
00:06:46,970 --> 00:06:50,070
algoritma untuk menjalankan dalam kes terburuk?

134
00:06:50,070 --> 00:06:51,640
Recall kita mewakili berjalan ini

135
00:06:51,640 --> 00:06:55,060
masa dengan notasi O besar.

136
00:06:55,060 --> 00:06:58,650
Dalam usaha untuk menentukan elemen Unsorted minimum, kita

137
00:06:58,650 --> 00:07:01,880
dasarnya terpaksa membandingkan setiap elemen dalam senarai untuk

138
00:07:01,880 --> 00:07:04,040
setiap elemen lain dalam senarai.

139
00:07:04,040 --> 00:07:08,430
Intuitif, ini bunyi seperti O operasi n kuasa dua.

140
00:07:08,430 --> 00:07:12,050
Melihat pseudokod kami, kami juga mempunyai gelung bersarang di dalam

141
00:07:12,050 --> 00:07:14,420
lagi gelung, yang sememangnya bunyi seperti O

142
00:07:14,420 --> 00:07:16,480
operasi n kuasa dua.

143
00:07:16,480 --> 00:07:19,250
Walau bagaimanapun, ingat bahawa kita tidak perlu untuk melihat lebih

144
00:07:19,250 --> 00:07:23,460
seluruh senarai apabila menentukan elemen Unsorted minimum?

145
00:07:23,460 --> 00:07:26,600
Apabila kita tahu bahawa 4 telah disusun, sebagai contoh, kita tidak

146
00:07:26,600 --> 00:07:28,170
perlu melihat ia lagi.

147
00:07:28,170 --> 00:07:31,020
Jadi adakah ini mengurangkan masa berjalan?

148
00:07:31,020 --> 00:07:34,510
Untuk senarai kami sebanyak 6 panjang, kita diperlukan untuk membuat lima

149
00:07:34,510 --> 00:07:37,990
perbandingan bagi elemen pertama, empat perbandingan untuk

150
00:07:37,990 --> 00:07:40,750
elemen kedua, dan sebagainya.

151
00:07:40,750 --> 00:07:44,690
Itu bermakna bahawa jumlah langkah-langkah adalah jumlah

152
00:07:44,690 --> 00:07:49,160
integer dari 1 hingga panjang senarai tolak 1.

153
00:07:49,160 --> 00:07:51,005
Kita boleh mewakili ini dengan penjumlahan.

154
00:07:57,980 --> 00:07:59,910
Kami tidak akan pergi ke dalam penjumlahan sini.

155
00:07:59,910 --> 00:08:04,900
Tetapi ternyata bahawa penjumlahan ini adalah sama untuk kali n

156
00:08:04,900 --> 00:08:07,540
n tolak 1 lebih 2.

157
00:08:07,540 --> 00:08:14,220
Atau sebandingnya, n kuasa dua lebih 2 tolak n lebih dari 2.

158
00:08:14,220 --> 00:08:18,860
Apabila bercakap tentang runtime asimptot, n istilah kuasa dua

159
00:08:18,860 --> 00:08:22,070
akan menguasai istilah ini n.

160
00:08:22,070 --> 00:08:27,850
Jadi apapun pemilihan O n kuasa dua.

161
00:08:27,850 --> 00:08:31,460
Ingatlah bahawa dalam contoh kita, apapun pemilihan masih diperlukan untuk

162
00:08:31,460 --> 00:08:33,850
memeriksa jika nombor yang telah disusun

163
00:08:33,850 --> 00:08:35,450
diperlukan untuk dipindahkan.

164
00:08:35,450 --> 00:08:38,929
Supaya bermakna bahawa jika kita berlari apapun pemilihan lebih yang sudah

165
00:08:38,929 --> 00:08:43,070
disusun senarai, ia akan memerlukan jumlah yang sama langkah-langkah kerana ia

166
00:08:43,070 --> 00:08:46,340
akan apabila berjalan lebih senarai sepenuhnya Unsorted.

167
00:08:46,340 --> 00:08:51,470
Jadi apapun pemilihan mempunyai kes prestasi terbaik n kuasa dua,

168
00:08:51,470 --> 00:08:56,820
yang kita mewakili dengan omega n kuasa dua.

169
00:08:56,820 --> 00:08:58,600
Dan itulah ia untuk menyelesaikan pemilihan.

170
00:08:58,600 --> 00:09:00,630
Hanya salah satu algoritma banyak kita boleh

171
00:09:00,630 --> 00:09:02,390
gunakan untuk menyusun senarai.

172
00:09:02,390 --> 00:09:05,910
Nama saya adalah Tommy, dan ini adalah cs50.