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

2
00:00:05,760 --> 00:00:08,900
>> డౌ LLOYD: కాబట్టి CS50 లో మేము గురించి నేర్చుకున్నాడు
సార్టింగ్ అండ్ సెర్చింగ్ వివిధ

3
00:00:08,900 --> 00:00:09,442
అల్గోరిథంలు.

4
00:00:09,442 --> 00:00:11,400
కొన్నిసార్లు ఉంటుంది
ఉంచడానికి ఒక చిన్న గమ్మత్తైన

5
00:00:11,400 --> 00:00:14,161
ఏమి అల్గోరిథం యొక్క ట్రాక్ దేనిని.

6
00:00:14,161 --> 00:00:15,910
మమ్మల్ని మాత్రమే చేసిన
చాలా ఉపరితల తీసే

7
00:00:15,910 --> 00:00:18,740
అనేక ఇతర శోధించడం ఉన్నాయి
మరియు సార్టింగ్ అల్గోరిథంలు.

8
00:00:18,740 --> 00:00:21,780
సో ఈ వీడియో లో లెట్స్
కేవలం కొన్ని నిమిషాలు పట్టవచ్చు

9
00:00:21,780 --> 00:00:24,980
ప్రయత్నించండి మరియు ప్రతి అల్గోరిథం పరిశుద్ధం
దాని కోర్ అంశాలు క్రిందికి

10
00:00:24,980 --> 00:00:27,810
కాబట్టి మీరు చాలా గుర్తుంచుకోగలరు
వాటిని గురించి ముఖ్యమైన సమాచారం

11
00:00:27,810 --> 00:00:31,970
మరియు ఉచ్చరించు చేయగలరు
తేడాలు, అవసరమైతే.

12
00:00:31,970 --> 00:00:34,220
>> మొదటి ఎంపిక విధమైన ఉంది.

13
00:00:34,220 --> 00:00:38,210
ఎంపిక విధమైన వెనుక ప్రధాన ఆలోచన
చిన్న క్రమబద్ధీకరించనిది మూలకం కనుగొనేందుకు ఉంది

14
00:00:38,210 --> 00:00:42,890
వ్యూహంలో తో స్వాప్
ఆ శ్రేణి యొక్క మొదటి క్రమబద్ధీకరించనిది మూలకం.

15
00:00:42,890 --> 00:00:46,620
మేము దారుణమైన చెప్పారు
ఆ రన్ టైం స్క్వేర్డ్ n జరిగినది.

16
00:00:46,620 --> 00:00:50,060
మరియు మీరు ఎందుకు గుర్తుకు అనుకుంటే, పడుతుంది
ఎంపిక విధమైన వీడియో చూడండి.

17
00:00:50,060 --> 00:00:54,560
ఉత్తమ కేసు అమలు సమయం
కూడా స్క్వేర్డ్ n.

18
00:00:54,560 --> 00:00:58,910
>> బబుల్ సార్ట్, ఆ ఆలోచనకు
ఒక ప్రక్కనే ఉన్న జతల మారడానికి ఉంది.

19
00:00:58,910 --> 00:01:01,730
తద్వారా మీరు సహాయపడుతుంది కీ
ఇక్కడ తేడా గుర్తుంచుకోవాలి.

20
00:01:01,730 --> 00:01:04,920
ఎంపిక విధమైన, ఇప్పటివరకు,
సూక్ష్మ బబుల్ కనుగొనేందుకు

21
00:01:04,920 --> 00:01:06,790
సార్ట్ ప్రక్కనే ఉన్న జతల మార్పిడి.

22
00:01:06,790 --> 00:01:08,710
మేము ప్రక్కనే ఉన్న జతల మార్పిడి
అంశాల వారు ఉంటే

23
00:01:08,710 --> 00:01:12,530
ఇది సమర్థవంతంగా క్రమం బయటవున్న
కుడి, పెద్ద అంశాలు బుడగలు

24
00:01:12,530 --> 00:01:17,060
మరియు అదే సమయంలో అది కూడా ప్రారంభమవుతుంది
ఎడమ చిన్న అంశాలు తరలించడానికి.

25
00:01:17,060 --> 00:01:20,180
చెత్త-కేసు విషయంలో రన్ టైం
బబుల్ సార్ట్ స్క్వేర్డ్ n.

26
00:01:20,180 --> 00:01:23,476
ఉత్తమ కేసు అమలు సమయం
బబుల్ విధమైన n.

27
00:01:23,476 --> 00:01:25,350
ఎందుకంటే ఆ పరిస్థితిలో
మేము నిజానికి లేదు

28
00:01:25,350 --> 00:01:27,141
మేము అవసరం లేదు ఉండవచ్చు
అన్ని వద్ద ఏ మార్పిడులు చేయటం.

29
00:01:27,141 --> 00:01:31,026
మేము కేవలం ఒక చేసుకోవాలి
అన్ని n మూలకాలు అంతటా పాస్.

30
00:01:31,026 --> 00:01:34,600
>> చొప్పించడం విధమైన లో,
ఇక్కడ ప్రాథమిక ఆలోచన బదిలీ ఉంది.

31
00:01:34,600 --> 00:01:36,630
అని చొప్పించడం విధమైన కీలకపదం వార్తలు.

32
00:01:36,630 --> 00:01:39,630
మేము ఒకసారి ద్వారా దశను చూడాలని
నుండి శ్రేణి ఎడమ.

33
00:01:39,630 --> 00:01:41,670
మేము వంటి, మేము ఉన్నాము
అంశాలు బదిలీ అన్నారు

34
00:01:41,670 --> 00:01:46,260
మేము ఇప్పటికే కల్పించడం చూసిన
ఎక్కడో సరిపోయే అవసరం చిన్నవి

35
00:01:46,260 --> 00:01:48,080
తిరిగి క్రమబద్ధీకరించబడతాయి భాగం.

36
00:01:48,080 --> 00:01:51,600
కాబట్టి మేము క్రమబద్ధీకరించబడతాయి శ్రేణి నిర్మించడానికి ఒక
ఎడమ నుండి కుడికి ఒక సమయంలో మూలకం,

37
00:01:51,600 --> 00:01:54,740
మరియు మేము కల్పించేలా విషయాలు మారవచ్చు.

38
00:01:54,740 --> 00:01:58,650
చెత్త-కేసు రన్ టైం
చొప్పించడం విధమైన n స్క్వేర్డ్.

39
00:01:58,650 --> 00:02:02,380
ఉత్తమ కేసు అమలు సమయం n.

40
00:02:02,380 --> 00:02:05,380
>> కీవర్డ్ విధమైన విలీనం
ఇక్కడ విడిపోయి కలిసిపోయినా.

41
00:02:05,380 --> 00:02:08,949
మేము అని, పూర్తి శ్రేణి విడిపోయారు
ఇది ఆరు అంశాలు, ఎనిమిది అంశాలు వార్తలు,

42
00:02:08,949 --> 00:02:13,790
10,000 మూలకాల మేము అది విడిపోయింది
డౌన్ సగం, సగం ద్వారా సగానికి,

43
00:02:13,790 --> 00:02:17,720
మేము శ్రేణి కింద వరకు
n ఒక మూలకం శ్రేణుల.

44
00:02:17,720 --> 00:02:19,470
N ఒక మూలకం శ్రేణుల సెట్.

45
00:02:19,470 --> 00:02:22,640
కాబట్టి మేము ఒక ప్రారంభించండి
1,000 మూలకం శ్రేణి,

46
00:02:22,640 --> 00:02:26,550
మరియు మేము పాయింట్ చోటే మేము
1,000 ఒక మూలకం శ్రేణుల ఉన్నాయి.

47
00:02:26,550 --> 00:02:30,990
అప్పుడు మేము ఆ ఉప శ్రేణుల విలీనం ప్రారంభమవుతుంది
తిరిగి కలిసి సరైన క్రమంలో.

48
00:02:30,990 --> 00:02:34,860
కాబట్టి మేము రెండు ఒక మూలకం శ్రేణుల పడుతుంది
మరియు ఒక రెండు మూలకం శ్రేణి సృష్టించండి.

49
00:02:34,860 --> 00:02:38,180
మేము రెండు రెండు మూలకం శ్రేణుల పడుతుంది
మరియు నాలుగు-మూలకం శ్రేణి సృష్టించడానికి

50
00:02:38,180 --> 00:02:43,900
అందువలన మరియు అందువలన న మేము చేసిన వరకు
మళ్ళీ ఒకటి n మూలకాల శ్రేణి పునర్నిర్మించబడింది.

51
00:02:43,900 --> 00:02:48,410
>> చెత్త-కేసు రన్ టైం
సార్ట్ విలీనం n సార్లు లాగ్ n.

52
00:02:48,410 --> 00:02:52,390
మేము n మూలకాలు కలిగి, కానీ
ఈ పునఃకలయిక ప్రక్రియ

53
00:02:52,390 --> 00:02:56,960
లాగిన్ పడుతుంది n దశలను పొందడానికి
పూర్తి శ్రేణి వెనుకకు.

54
00:02:56,960 --> 00:03:01,160
సమయం అమలు ఉత్తమ సందర్భంలో కూడా n లాగ్
n ఈ ప్రక్రియ నిజంగా లేదు ఎందుకంటే

55
00:03:01,160 --> 00:03:04,090
అర్రే ఉంది లేదో శ్రద్ధ
క్రమంలో క్రమబద్ధీకరించబడిన లేదా ప్రారంభం.

56
00:03:04,090 --> 00:03:07,590
ప్రాసెస్ ఉంది, అదే
షార్ట్ సర్క్యూట్ విషయాలు ఏ విధంగా.

57
00:03:07,590 --> 00:03:11,610
కాబట్టి n చెత్త సందర్భంలో n లాగ్,
n ఉత్తమ సందర్భంలో n లాగ్.

58
00:03:11,610 --> 00:03:13,960
>> మేము రెండు గురించి మాట్లాడారు
అల్గోరిథంలు శోధన.

59
00:03:13,960 --> 00:03:16,230
సో సరళ శోధన iterating గురించి.

60
00:03:16,230 --> 00:03:19,500
మేము శ్రేణి అంతటా వెళ్లండి
ఒకసారి, ఎడమ నుండి కుడికి,

61
00:03:19,500 --> 00:03:21,950
సంఖ్య కనుగొనేందుకు ప్రయత్నిస్తున్న
మేము చూస్తున్న.

62
00:03:21,950 --> 00:03:24,550
చెత్త-కేసు అమలు సమయం n యొక్క పెద్ద O ఉంది.

63
00:03:24,550 --> 00:03:27,610
ఇది iterating మాకు పడుతుంది
ప్రతి మూలకం అంతటా

64
00:03:27,610 --> 00:03:30,660
మేము చూస్తున్న మూలకం కనుగొనేందుకు
కోసం గాని చివరి స్థానం లో,

65
00:03:30,660 --> 00:03:31,630
లేదా అన్ని వద్ద.

66
00:03:31,630 --> 00:03:34,720
కానీ మేము వరకు నిర్ధారించలేము
మేము ప్రతిదీ చూశారు చేసిన.

67
00:03:34,720 --> 00:03:36,730
ఉత్తమ కేసు రెడీ, మేము వెంటనే కనుగొనేందుకు.

68
00:03:36,730 --> 00:03:41,060
యొక్క ఉత్తమ కేసు అమలు సమయం
సరళ శోధన 1 ఒమేగా ఉంది.

69
00:03:41,060 --> 00:03:43,689
>> చివరగా, బైనరీ శోధన, ఉంది
ఇది వర్గీకృత శ్రేణి అవసరమవుతుంది.

70
00:03:43,689 --> 00:03:45,605
ఆ చాలా గుర్తుంచుకోవాలి
ముఖ్యమైన పరిగణన

71
00:03:45,605 --> 00:03:47,155
బైనరీ శోధన పనిచేసేటప్పుడు.

72
00:03:47,155 --> 00:03:50,180
ఇది దానిని ఉపయోగించి కు అంత అవసరం ఉంది
మీరు చూస్తున్న ఆ శ్రేణి

73
00:03:50,180 --> 00:03:52,160
వేరు చేయాల్సి ఉంటుంది.

74
00:03:52,160 --> 00:03:54,500
లేకపోతే, కీవర్డ్
విభజించి జయించటానికి ఉంది.

75
00:03:54,500 --> 00:03:58,310
సగం లోకి శ్రేణి విడిపోయారు మరియు
అంశాలు సగం తొలగించడానికి

76
00:03:58,310 --> 00:04:00,780
ప్రతిసారీ మీరు ద్వారా కొనసాగండి.

77
00:04:00,780 --> 00:04:04,330
ఎందుకంటే ఈ విభజించి జయించటానికి
మరియు సగం విధానం విడిపోవడం విషయాలు,

78
00:04:04,330 --> 00:04:07,450
దారుణమైన రన్ టైం
బైనరీ శోధన

79
00:04:07,450 --> 00:04:11,730
గణనీయంగా ఇది, n లాగిన్
సరళ శోధన యొక్క n కంటే మెరుగైన.

80
00:04:11,730 --> 00:04:13,570
ఉత్తమ కేసు అమలు సమయం ఇప్పటికీ ఒకటి.

81
00:04:13,570 --> 00:04:17,010
>> మేము వెంటనే కలిగించే
మొదటిసారి మేము ఒక విభాగం, అయితే

82
00:04:17,010 --> 00:04:19,339
మళ్ళీ, గుర్తుంచుకోవాలి
బైనరీ శోధన అయితే

83
00:04:19,339 --> 00:04:24,030
సరళ శోధన కంటే గణనీయంగా మంచి
లాగ్ ఉండటం ఉండటం ద్వారా N N వర్సెస్

84
00:04:24,030 --> 00:04:27,110
మీరు పని ద్వారా వెళ్ళడానికి కలిగి ఉండవచ్చు
మొదటి మీ వ్యూహం క్రమబద్ధీకరించేందుకు ఏ

85
00:04:27,110 --> 00:04:32,010
ఆధారపడి అది తక్కువ ప్రభావవంతంగా సంపాదించగలరు
క్రమబద్ధీకరించబడింది iterating యొక్క పరిమాణం మీద.

86
00:04:32,010 --> 00:04:35,250
>> నేను డౌ లాయిడ్ ఉన్నాను, ఈ CS50 ఉంది.

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