1
00:00:00,000 --> 00:00:05,760

2
00:00:05,760 --> 00:00:08,900
>> Doug LLOYD: Jadi di CS50 kami belajar tentang
berbagai memilah dan mencari

3
00:00:08,900 --> 00:00:09,442
algoritma.

4
00:00:09,442 --> 00:00:11,400
Dan kadang-kadang bisa
sedikit rumit untuk menjaga

5
00:00:11,400 --> 00:00:14,161
melacak apa algoritma melakukan apa.

6
00:00:14,161 --> 00:00:15,910
Kami sudah benar-benar hanya
skim permukaan juga,

7
00:00:15,910 --> 00:00:18,740
ada banyak pencarian lain
dan algoritma pengurutan.

8
00:00:18,740 --> 00:00:21,780
Jadi di video ini mari kita
hanya mengambil beberapa menit

9
00:00:21,780 --> 00:00:24,980
untuk mencoba dan menyaring setiap algoritma
ke elemen inti

10
00:00:24,980 --> 00:00:27,810
sehingga Anda dapat mengingat paling
informasi penting tentang mereka

11
00:00:27,810 --> 00:00:31,970
dan mampu mengartikulasikan
perbedaan, jika perlu.

12
00:00:31,970 --> 00:00:34,220
>> Yang pertama adalah semacam seleksi.

13
00:00:34,220 --> 00:00:38,210
Ide dasar di balik pilihan semacam
adalah menemukan elemen terkecil disortir

14
00:00:38,210 --> 00:00:42,890
dalam array dan swap dengan
elemen disortir pertama dari array itu.

15
00:00:42,890 --> 00:00:46,620
Kami mengatakan bahwa kasus terburuk
menjalankan waktu yang n kuadrat.

16
00:00:46,620 --> 00:00:50,060
Dan jika Anda ingin mengingat mengapa, mengambil
a melihat pilihan semacam video.

17
00:00:50,060 --> 00:00:54,560
Yang terbaik-kasus jangka waktu
juga n kuadrat.

18
00:00:54,560 --> 00:00:58,910
>> Bubble sort, ide di balik itu
salah satunya adalah dengan menukar pasangan yang berdekatan.

19
00:00:58,910 --> 00:01:01,730
Jadi itulah kunci yang membantu Anda
ingat perbedaan di sini.

20
00:01:01,730 --> 00:01:04,920
Seleksi semacam adalah, sejauh ini,
menemukan gelembung smallest--

21
00:01:04,920 --> 00:01:06,790
semacam yaitu menukar pasangan yang berdekatan.

22
00:01:06,790 --> 00:01:08,710
Kami bertukar pasangan yang berdekatan
elemen jika mereka

23
00:01:08,710 --> 00:01:12,530
adalah rusak, yang secara efektif
gelembung elemen yang lebih besar ke kanan,

24
00:01:12,530 --> 00:01:17,060
dan pada saat yang sama juga mulai
untuk memindahkan elemen yang lebih kecil ke kiri.

25
00:01:17,060 --> 00:01:20,180
Terburuk-kasus waktu kasus run
dari bubble sort adalah n kuadrat.

26
00:01:20,180 --> 00:01:23,476
Yang terbaik-kasus jangka waktu
dari bubble sort adalah n.

27
00:01:23,476 --> 00:01:25,350
Karena dalam situasi yang
kita tidak actually--

28
00:01:25,350 --> 00:01:27,141
kita mungkin tidak perlu
membuat swap sama sekali.

29
00:01:27,141 --> 00:01:31,026
Kami hanya perlu membuat satu
lulus di semua elemen n.

30
00:01:31,026 --> 00:01:34,600
>> Dalam insertion sort, yang
Ide dasar di sini bergeser.

31
00:01:34,600 --> 00:01:36,630
Itulah kata kunci untuk insertion sort.

32
00:01:36,630 --> 00:01:39,630
Kita akan melangkah sekali melalui
array dari kiri ke kanan.

33
00:01:39,630 --> 00:01:41,670
Dan seperti yang kita lakukan, kita
akan menggeser elemen

34
00:01:41,670 --> 00:01:46,260
kita sudah melihat untuk memberikan ruang bagi
yang lebih kecil yang harus sesuai tempat

35
00:01:46,260 --> 00:01:48,080
kembali bahwa sebagian diurutkan.

36
00:01:48,080 --> 00:01:51,600
Jadi kami membangun array diurutkan satu
elemen pada suatu waktu, kiri ke kanan,

37
00:01:51,600 --> 00:01:54,740
dan kita menggeser hal untuk membuat ruang.

38
00:01:54,740 --> 00:01:58,650
The terburuk run time dari
insertion sort adalah n kuadrat.

39
00:01:58,650 --> 00:02:02,380
Yang terbaik-kasus berjalan waktu n.

40
00:02:02,380 --> 00:02:05,380
>> Menggabungkan sort-- kata kunci
di sini adalah membagi dan menggabungkan.

41
00:02:05,380 --> 00:02:08,949
Kami membagi array penuh, apakah
itu enam elemen, delapan elemen,

42
00:02:08,949 --> 00:02:13,790
10.000 elements-- kita membaginya
turun hingga setengahnya, setengahnya, setengahnya,

43
00:02:13,790 --> 00:02:17,720
sampai kita memiliki array yang di bawah
n satu elemen array.

44
00:02:17,720 --> 00:02:19,470
Satu set n satu elemen array.

45
00:02:19,470 --> 00:02:22,640
Jadi kita mulai dengan satu
Array 1.000-elemen,

46
00:02:22,640 --> 00:02:26,550
dan kami sampai ke titik di mana kita
memiliki 1.000 array satu-elemen.

47
00:02:26,550 --> 00:02:30,990
Kemudian kita mulai untuk menggabungkan mereka sub array
kembali bersama-sama dalam urutan yang benar.

48
00:02:30,990 --> 00:02:34,860
Jadi kami mengambil dua array satu-elemen
dan membuat array dua-elemen.

49
00:02:34,860 --> 00:02:38,180
Kami mengambil dua array dua-elemen
dan membuat array empat-elemen

50
00:02:38,180 --> 00:02:43,900
dan seterusnya dan seterusnya sampai kita sudah
lagi dibangun kembali satu array elemen n.

51
00:02:43,900 --> 00:02:48,410
>> The terburuk run time dari
menggabungkan semacam yaitu n kali log n.

52
00:02:48,410 --> 00:02:52,390
Kami memiliki n elemen, tetapi
proses recombining ini

53
00:02:52,390 --> 00:02:56,960
Dibutuhkan log n langkah-langkah untuk mendapatkan
kembali ke array penuh.

54
00:02:56,960 --> 00:03:01,160
Kasus terbaik menjalankan waktu juga n log
n karena proses ini tidak benar-benar

55
00:03:01,160 --> 00:03:04,090
peduli apakah array adalah
diurutkan atau tidak untuk memulai dengan.

56
00:03:04,090 --> 00:03:07,590
Proses ini sama, ada
ada cara untuk hal hubungan pendek.

57
00:03:07,590 --> 00:03:11,610
Jadi n log n dalam kasus terburuk,
n log n dalam kasus terbaik.

58
00:03:11,610 --> 00:03:13,960
>> Kami berbicara tentang dua
algoritma pencarian.

59
00:03:13,960 --> 00:03:16,230
Jadi pencarian linear adalah tentang iterasi.

60
00:03:16,230 --> 00:03:19,500
Kami melanjutkan di array
sekali, dari kiri ke kanan,

61
00:03:19,500 --> 00:03:21,950
mencoba untuk menemukan nomor
bahwa kita sedang mencari.

62
00:03:21,950 --> 00:03:24,550
The terburuk waktu berjalan adalah O besar n.

63
00:03:24,550 --> 00:03:27,610
Mungkin membawa kita iterasi
di setiap elemen tunggal

64
00:03:27,610 --> 00:03:30,660
untuk menemukan elemen yang kita cari
untuk, baik di posisi terakhir,

65
00:03:30,660 --> 00:03:31,630
atau tidak sama sekali.

66
00:03:31,630 --> 00:03:34,720
Tapi kita tidak bisa mengkonfirmasi bahwa sampai
kita telah melihat segalanya.

67
00:03:34,720 --> 00:03:36,730
m kasus terbaik, kita menemukan segera.

68
00:03:36,730 --> 00:03:41,060
Yang terbaik-kasus run time dari
pencarian linear adalah omega dari 1.

69
00:03:41,060 --> 00:03:43,689
>> Terakhir, ada pencarian biner,
yang membutuhkan berbagai macam array.

70
00:03:43,689 --> 00:03:45,605
Ingat itu sangat
pertimbangan penting

71
00:03:45,605 --> 00:03:47,155
ketika bekerja dengan pencarian biner.

72
00:03:47,155 --> 00:03:50,180
Ini prasyarat untuk menggunakan itu--
array yang Anda cari melalui

73
00:03:50,180 --> 00:03:52,160
harus dipilah.

74
00:03:52,160 --> 00:03:54,500
Jika tidak, kata kunci
adalah membagi dan menaklukkan.

75
00:03:54,500 --> 00:03:58,310
Membagi array menjadi setengah dan
menghilangkan setengah dari elemen

76
00:03:58,310 --> 00:04:00,780
setiap kali Anda melanjutkan melalui.

77
00:04:00,780 --> 00:04:04,330
Karena membagi ini dan menaklukkan
dan hal membelah dua pendekatan,

78
00:04:04,330 --> 00:04:07,450
yang terburuk run time
dari pencarian biner adalah

79
00:04:07,450 --> 00:04:11,730
log n, yang secara substansial
lebih baik daripada pencarian linear ini n.

80
00:04:11,730 --> 00:04:13,570
Yang terbaik-kasus berjalan waktu masih salah.

81
00:04:13,570 --> 00:04:17,010
>> Kami mungkin akan segera
pertama kali kita membuat divisi, tapi,

82
00:04:17,010 --> 00:04:19,339
lagi, ingat bahwa
meskipun pencarian biner adalah

83
00:04:19,339 --> 00:04:24,030
jauh lebih baik dibandingkan pencarian linear
berdasarkan menjadi log n terhadap n,

84
00:04:24,030 --> 00:04:27,110
Anda mungkin harus melalui pekerjaan
penyortiran array pertama, yang

85
00:04:27,110 --> 00:04:32,010
mungkin membuatnya kurang efektif tergantung
pada ukuran dari iterasi diurutkan.

86
00:04:32,010 --> 00:04:35,250
>> Aku Doug Lloyd, ini CS50.

87
00:04:35,250 --> 00:04:36,757