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

2
00:00:05,760 --> 00:00:08,900
>> Doug LLOYD: Yani CS50 biz öğrendik
sıralama ve arama çeşitli

3
00:00:08,900 --> 00:00:09,442
algoritmaları.

4
00:00:09,442 --> 00:00:11,400
Ve bazen bu olabilir
tutmak biraz zor

5
00:00:11,400 --> 00:00:14,161
Ne algoritması parça ne yapar.

6
00:00:14,161 --> 00:00:15,910
Biz gerçekten sadece ettik
çok yüzeyi yağsız

7
00:00:15,910 --> 00:00:18,740
Birçok başka arama vardır
ve sıralama algoritmaları.

8
00:00:18,740 --> 00:00:21,780
Yani bu video diyelim
Sadece birkaç dakika sürebilir

9
00:00:21,780 --> 00:00:24,980
denemek ve her algoritma damıtmak için
onun temel unsurları aşağı

10
00:00:24,980 --> 00:00:27,810
böylece en hatırlıyorum
Onlar hakkında önemli bilgiler

11
00:00:27,810 --> 00:00:31,970
ve ifade etmeye muktedir
farklılıklar, gerekirse.

12
00:00:31,970 --> 00:00:34,220
>> İlk seçim türüdür.

13
00:00:34,220 --> 00:00:38,210
Seçim tür arkasındaki temel fikir
En küçük ayrımı yapılmamış diğer eleman bulmak olduğunu

14
00:00:38,210 --> 00:00:42,890
ve bir dizideki ile takas
Bu dizinin ilk sıralanmamış öğesi.

15
00:00:42,890 --> 00:00:46,620
Biz en kötü durum olduğunu söyledi
Bunun çalışma süresi n karesi oldu.

16
00:00:46,620 --> 00:00:50,060
Ve neden hatırlamak istiyorsanız, almak
Seçim sıralama video bakmak.

17
00:00:50,060 --> 00:00:54,560
En iyi durum çalışma süresi
Ayrıca n karesi edilir.

18
00:00:54,560 --> 00:00:58,910
>> Kabarcık sıralama, o arkasındaki fikir
tek bitişik çift takas etmektir.

19
00:00:58,910 --> 00:01:01,730
Yani size yardımcı olur anahtar
Burada fark hatırlıyorum.

20
00:01:01,730 --> 00:01:04,920
Seçim sıralama isimli, şimdiye kadar,
smallest-- balonu bulmak

21
00:01:04,920 --> 00:01:06,790
sıralama isimli bitişik çift takas.

22
00:01:06,790 --> 00:01:08,710
Biz bitişik çift takas
elemanların onlar halinde

23
00:01:08,710 --> 00:01:12,530
hangi etkili, sırasız
sağdaki büyük elemanları kabarcıklar

24
00:01:12,530 --> 00:01:17,060
ve aynı zamanda, aynı zamanda başlar
sola küçük öğeleri taşımak için.

25
00:01:17,060 --> 00:01:20,180
En kötü durum durum çalışma süresi
kabarcık tür n karesi edilir.

26
00:01:20,180 --> 00:01:23,476
En iyi durum çalışma süresi
kabarcık tür n.

27
00:01:23,476 --> 00:01:25,350
Çünkü bu durumda
Biz actually-- yok

28
00:01:25,350 --> 00:01:27,141
Biz gerek olmayabilir
hiç bir swapları yapmak.

29
00:01:27,141 --> 00:01:31,026
Biz sadece bir tane yapmak zorunda
tüm n elemanları arasında geçmektedir.

30
00:01:31,026 --> 00:01:34,600
>> Ekleme sıralamada,
Burada temel fikir kayıyor.

31
00:01:34,600 --> 00:01:36,630
Bu ekleme sıralama için anahtar kelime var.

32
00:01:36,630 --> 00:01:39,630
Biz aracılığıyla bir kez adım gidiyoruz
dan dizi soldan sağa.

33
00:01:39,630 --> 00:01:41,670
Bizim gibi, biz konum
elemanları degisecek

34
00:01:41,670 --> 00:01:46,260
biz zaten yer açmak için gördüm
yere sığdırmak için gereken küçük olanlar

35
00:01:46,260 --> 00:01:48,080
geri o sıralanmış kısmında.

36
00:01:48,080 --> 00:01:51,600
Bu yüzden sıralı dizi inşa biri
soldan sağa bir anda eleman,

37
00:01:51,600 --> 00:01:54,740
ve biz oda yapmak şeyler kaydırır.

38
00:01:54,740 --> 00:01:58,650
En kötü durum çalışma süresi
Ekleme sıralama n karesi edilir.

39
00:01:58,650 --> 00:02:02,380
En iyi durum çalışma zamanı n.

40
00:02:02,380 --> 00:02:05,380
>> Anahtar kelime sort-- Birleştirme
Burada bölme ve birleştirme olduğunu.

41
00:02:05,380 --> 00:02:08,949
Biz ister, tam bir dizi bölünmüş
Altı elemanları, sekiz elemanları var,

42
00:02:08,949 --> 00:02:13,790
10,000 öğelerin-- biz bölmek
Aşağı yarı yarıya yarıya, yarı yarıya,

43
00:02:13,790 --> 00:02:17,720
Biz dizide altında elde edene kadar
n bir unsuru diziler.

44
00:02:17,720 --> 00:02:19,470
N bir unsuru dizilerin kümesi.

45
00:02:19,470 --> 00:02:22,640
Bu yüzden biriyle başladık
1000-eleman dizisi,

46
00:02:22,640 --> 00:02:26,550
ve biz noktaya nereden biz
1000 tek eleman diziler var.

47
00:02:26,550 --> 00:02:30,990
Sonra o alt dizilerini birleştirmek başlar
tekrar bir araya doğru sırayla.

48
00:02:30,990 --> 00:02:34,860
Bu yüzden iki tek eleman dizileri almak
ve bir iki eleman dizi oluşturmak.

49
00:02:34,860 --> 00:02:38,180
Biz iki, iki eleman dizileri almak
ve dört element dizi oluşturmak

50
00:02:38,180 --> 00:02:43,900
ve böylece ve böylece biz ettik kadar
yine bir n elemanı dizisi yeniden inşa edildi.

51
00:02:43,900 --> 00:02:48,410
>> En kötü durum çalışma süresi
sıralama isimli birleştirme n kat n oturum açın.

52
00:02:48,410 --> 00:02:52,390
Biz n unsurlar var, ama
Bu yeniden birleştirici süreci

53
00:02:52,390 --> 00:02:56,960
log alır n adımlar almak
Tam diziye geri.

54
00:02:56,960 --> 00:03:01,160
Çalışma süresi en iyi durumda da n log
n bu süreç gerçekten yok çünkü

55
00:03:01,160 --> 00:03:04,090
Dizi olup olmadığını bakım
sıralanmış ya da başlamak.

56
00:03:04,090 --> 00:03:07,590
Süreç var, aynı
kısa devre şeyler hiçbir şekilde.

57
00:03:07,590 --> 00:03:11,610
Yani n kötü durumda log n,
n iyi durumda log n.

58
00:03:11,610 --> 00:03:13,960
>> Biz iki konuştuk
algoritmaları arıyor.

59
00:03:13,960 --> 00:03:16,230
Yani doğrusal arama iterating ilgili.

60
00:03:16,230 --> 00:03:19,500
Biz dizi boyunca devam
Bir kez, soldan sağa doğru,

61
00:03:19,500 --> 00:03:21,950
numarasını bulmak için çalışıyor
biz arıyoruz.

62
00:03:21,950 --> 00:03:24,550
En kötü durum çalışma zamanı n büyük O'dur.

63
00:03:24,550 --> 00:03:27,610
Bu yineleme Bizi alabilir
her elemanın karşısında

64
00:03:27,610 --> 00:03:30,660
Biz arıyoruz eleman bulmak için
için, ya da en son yer,

65
00:03:30,660 --> 00:03:31,630
ya da hiç.

66
00:03:31,630 --> 00:03:34,720
Ama biz gelene kadar teyit edemez
biz her şeyi baktım.

67
00:03:34,720 --> 00:03:36,730
En iyi davayı m, biz hemen bulabilirsiniz.

68
00:03:36,730 --> 00:03:41,060
En iyi durum çalışma süresi
doğrusal arama 1 omega olduğunu.

69
00:03:41,060 --> 00:03:43,689
>> Son olarak, ikili arama, orada
hangi çeşitli dizi gerektirir.

70
00:03:43,689 --> 00:03:45,605
Bu çok var: Ol
önemli bir husus

71
00:03:45,605 --> 00:03:47,155
İkili arama ile çalışırken.

72
00:03:47,155 --> 00:03:50,180
Bu Durdur-- kullanarak bir ön koşul var
Üzerinden aradığınız dizi

73
00:03:50,180 --> 00:03:52,160
sıralanması gerekir.

74
00:03:52,160 --> 00:03:54,500
Aksi takdirde, anahtar kelime
böl ve fethet olduğunu.

75
00:03:54,500 --> 00:03:58,310
Yarıya dizi Split ve
elemanların yarı ortadan

76
00:03:58,310 --> 00:04:00,780
Her zaman doğru ilerlerken.

77
00:04:00,780 --> 00:04:04,330
Çünkü bu böl ve yönet arasında
ve yarım yaklaşımda yarma şeyler,

78
00:04:04,330 --> 00:04:07,450
en kötü durum çalışma süresi
ikili arama olduğunu

79
00:04:07,450 --> 00:04:11,730
esas olan, log n
Lineer arama en n daha iyi.

80
00:04:11,730 --> 00:04:13,570
En iyi durum çalışma süresi hala biridir.

81
00:04:13,570 --> 00:04:17,010
>> Biz hemen bulabilirsiniz
İlk kez biz, bir bölümü yapmak, ancak

82
00:04:17,010 --> 00:04:19,339
Yine, unutmayın
İkili arama olmasına rağmen

83
00:04:19,339 --> 00:04:24,030
Lineer arama daha önemli ölçüde daha iyi
Günlük olmanın gereği n n karşı,

84
00:04:24,030 --> 00:04:27,110
Eğer çalışma sayesinde gitmek zorunda kalabilirsiniz
İlk dizinizi sıralama hangi

85
00:04:27,110 --> 00:04:32,010
bağlı daha az etkili hale getirebileceğini
kriteri iterating boyutuna.

86
00:04:32,010 --> 00:04:35,250
>> Ben Doug Lloyd değilim, bu CS50 olduğunu.

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