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

2
00:00:05,830 --> 00:00:07,910
>> All right, కాబట్టి, గణన సంక్లిష్టత.

3
00:00:07,910 --> 00:00:10,430
ఒక హెచ్చరిక కేవలం ఒక బిట్
మేము చాలా far-- ఈత కొట్టడానికి ముందు

4
00:00:10,430 --> 00:00:13,070
ఈ బహుశా మధ్య ఉంటాం
అత్యంత గణిత-భారీ విషయాలు

5
00:00:13,070 --> 00:00:14,200
మేము CS50 గురించి మాట్లాడటానికి.

6
00:00:14,200 --> 00:00:16,950
ఆశాజనక అది చాలా అధిక వుండదు
మరియు మేము ప్రయత్నించండి మరియు మీరు మార్గనిర్దేశం చేస్తాము

7
00:00:16,950 --> 00:00:19,200
ప్రక్రియ ద్వారా, కానీ
ఒక సరసమైన హెచ్చరిక కేవలం ఒక బిట్.

8
00:00:19,200 --> 00:00:21,282
కొద్దిగా ఉంది
గణిత ఇక్కడ చేరి.

9
00:00:21,282 --> 00:00:23,990
అన్ని కుడి, క్రమంలో చేయడానికి
మా గణన వనరులను వాడుకోవడం

10
00:00:23,990 --> 00:00:28,170
నిజమైన world-- అది నిజంగా వార్తలు
అల్గోరిథంలు అర్థం ముఖ్యం

11
00:00:28,170 --> 00:00:30,750
మరియు ఎలా వారు డేటా ప్రాసెస్.

12
00:00:30,750 --> 00:00:32,810
మేము కలిగి ఉంటే ఒక నిజంగా
సమర్థవంతమైన అల్గోరిథం, మేము

13
00:00:32,810 --> 00:00:36,292
వనరుల మొత్తం తగ్గిస్తుంది
మేము అది వ్యవహరించే అందుబాటులో ఉన్నాయి.

14
00:00:36,292 --> 00:00:38,750
మేము ఒక అల్గోరిథం ఉంటే ఆ
పని చాలా పడుతుంది అన్నారు

15
00:00:38,750 --> 00:00:41,210
నిజంగా ఒక ప్రాసెస్
డేటా పెద్ద సెట్, అంతే

16
00:00:41,210 --> 00:00:44,030
మరింత అవసరం అన్నారు
ఎక్కువ వనరులను, మరియు ఇది

17
00:00:44,030 --> 00:00:47,980
విషయాన్ని డబ్బు, RAM, అన్ని ఆ రకమైన ఉంది.

18
00:00:47,980 --> 00:00:52,090
>> కాబట్టి, సామర్థ్యం ఒక విశ్లేషించడానికి
అల్గోరిథం, ఈ సాధనం సమితి ఉపయోగించి

19
00:00:52,090 --> 00:00:56,110
ప్రధానంగా, ప్రశ్న అడుగుతుంది
ఈ అల్గోరిథం ఎత్తున ఎలా

20
00:00:56,110 --> 00:00:59,020
మేము అది వద్ద మరింత డేటా త్రో వంటి?

21
00:00:59,020 --> 00:01:02,220
CS50 లో, మేము డేటా మొత్తం ఉన్నాము
పని అందంగా చిన్నది.

22
00:01:02,220 --> 00:01:05,140
సాధారణంగా, మా కార్యక్రమాలు వెళ్తున్నారు
రెండవ లేదా less-- లో అమలు

23
00:01:05,140 --> 00:01:07,830
బహుశా చాలా తక్కువ
ముఖ్యంగా ప్రారంభ న.

24
00:01:07,830 --> 00:01:12,250
>> కానీ ఆ ఒప్పందాలు కంపెనీ గురించి ఆలోచించడం
వినియోగదారులు వందల మిలియన్ల.

25
00:01:12,250 --> 00:01:14,970
మరియు వారు ప్రాసెస్ అవసరం
ఆ కస్టమర్ డేటా.

26
00:01:14,970 --> 00:01:18,260
వినియోగదారుల సంఖ్య వంటి వారు
కలిగి, పెద్ద పెద్ద గెట్స్

27
00:01:18,260 --> 00:01:21,230
అది అవసరం జరగబోతోంది
మరింత వనరులు.

28
00:01:21,230 --> 00:01:22,926
ఎన్ని ఎక్కువ వనరులను?

29
00:01:22,926 --> 00:01:25,050
Well, ఎంత ఆధారపడి
మేము అల్గోరిథం విశ్లేషించడానికి,

30
00:01:25,050 --> 00:01:28,097
ఈ టూల్ లో టూల్స్ ఉపయోగించి.

31
00:01:28,097 --> 00:01:31,180
మేము సంక్లిష్టత గురించి మాట్లాడేటప్పుడు
ఒక అల్గోరిథం ఇది కొన్నిసార్లు మీరు చేస్తాము

32
00:01:31,180 --> 00:01:34,040
ఇది సమయం సూచిస్తారు వినడానికి
సంక్లిష్టత లేదా ఖాళీ సంక్లిష్టత

33
00:01:34,040 --> 00:01:36,190
కానీ మేము కేవలం చూడాలని
complexity-- కాల్

34
00:01:36,190 --> 00:01:38,770
మేము సాధారణంగా గురించి మాట్లాడటం చేస్తున్నాం
చెత్త దృష్టాంత.

35
00:01:38,770 --> 00:01:42,640
సంపూర్ణ చెత్త కుప్ప ఇచ్చిన
మేము అది వద్ద విసిరి అని డేటా

36
00:01:42,640 --> 00:01:46,440
ఎలా ఈ అల్గోరిథం అన్నారు
ప్రాసెస్ లేదా ఆ డేటా ఎదుర్కోవటానికి?

37
00:01:46,440 --> 00:01:51,450
మేము సాధారణంగా దారుణమైన కాల్
ఒక అల్గోరిథం పెద్ద-O యొక్క రన్టైమ్.

38
00:01:51,450 --> 00:01:56,770
కాబట్టి ఒక అల్గోరిథం కావచ్చు
స్క్వేర్డ్ n లేదా n యొక్క O యొక్క O లో అమలు.

39
00:01:56,770 --> 00:01:59,110
గురించి మరియు మరింత ఏమిటి
ఆ రెండవ అర్థం.

40
00:01:59,110 --> 00:02:01,620
>> కొన్నిసార్లు, మేము సంరక్షణ
ఉత్తమ దృష్టాంత గురించి.

41
00:02:01,620 --> 00:02:05,400
డేటా ప్రతిదీ ఉంటే మనం కోరుకున్న
అది ఉండాలి మరియు అది ఖచ్చితంగా పక్కాగా

42
00:02:05,400 --> 00:02:09,630
మరియు మేము ఈ పరిపూర్ణ పంపడం జరిగింది
మా అల్గోరిథం ద్వారా డేటా సెట్.

43
00:02:09,630 --> 00:02:11,470
ఇది ఎలా ఆ పరిస్థితిలో నిర్వహిస్తారనే?

44
00:02:11,470 --> 00:02:15,050
మేము కొన్నిసార్లు ఆ చూడండి
పెద్ద ఒమేగా, పెద్ద O విరుద్ధంగా కాబట్టి,

45
00:02:15,050 --> 00:02:16,530
మేము పెద్ద ఒమేగా కలిగి.

46
00:02:16,530 --> 00:02:18,880
ఉత్తమ దృష్టాంత కోసం బిగ్ ఒమేగా.

47
00:02:18,880 --> 00:02:21,319
చెత్త దృష్టాంత కోసం బిగ్-O.

48
00:02:21,319 --> 00:02:23,860
సాధారణంగా, మేము గురించి ఉన్నప్పుడు మాట్లాడటానికి
ఒక అల్గోరిథం యొక్క సంక్లిష్టత,

49
00:02:23,860 --> 00:02:26,370
మనం మాట్లాడే
చెత్త దృష్టాంత.

50
00:02:26,370 --> 00:02:28,100
కాబట్టి గుర్తుంచుకోండి.

51
00:02:28,100 --> 00:02:31,510
>> మరియు ఈ తరగతి లో, మేము సాధారణంగా చూడాలని
పక్కన ఖచ్చితమైన విశ్లేషణ విడిచి.

52
00:02:31,510 --> 00:02:35,350
శాస్త్రాలు మరియు ఖాళీలను ఉన్నాయి
stuff ఈ రకమైన అంకితం.

53
00:02:35,350 --> 00:02:37,610
మేము తార్కికం గురించి మాట్లాడేటప్పుడు
అల్గారిధం ద్వారా,

54
00:02:37,610 --> 00:02:41,822
మేము అనేక ముక్క-ద్వారా-ముక్క చేస్తాను ఇది
అల్గోరిథంలు మేము తరగతి లో మాట్లాడండి.

55
00:02:41,822 --> 00:02:44,780
మేము నిజంగా కేవలం గురించి మాట్లాడటం చేస్తున్నాం
ఇంగితజ్ఞానం తో ద్వారా రీజనింగ్,

56
00:02:44,780 --> 00:02:47,070
కాదు సూత్రాలు, లేదా నిర్ధారణలతో,
లేదా అలాంటిదే ఏదైనా.

57
00:02:47,070 --> 00:02:51,600
కాబట్టి చింతించకండి, మేము వుండదు
ఒక పెద్ద గణిత తరగతి పెట్టటము.

58
00:02:51,600 --> 00:02:55,920
>> కాబట్టి మనం సంక్లిష్టత గురించి శ్రద్ధ వహిస్తాను
అది ప్రశ్న, ఎలా అడుగుతుంది ఎందుకంటే

59
00:02:55,920 --> 00:03:00,160
మా అల్గోరిథంలు పెద్ద నిర్వహించడానికి లేదు మరియు
పెద్ద డేటా సమితుల వాటిని విసిరేవారు.

60
00:03:00,160 --> 00:03:01,960
Well, ఒక డేటా సమితి ఏమిటి?

61
00:03:01,960 --> 00:03:03,910
నేను చెప్పినప్పుడు నేను పదానికి అర్ధమేమి?

62
00:03:03,910 --> 00:03:07,600
ఇది చాలా కలిగించే పనులను అర్థం
సందర్భంలో భావం, నిజాయితీగా ఉండటానికి.

63
00:03:07,600 --> 00:03:11,160
మేము ఒక అల్గోరిథం ఉంటే
ప్రాసెసెస్ Strings-- మేము బహుశా ఉన్నాము

64
00:03:11,160 --> 00:03:13,440
స్ట్రింగ్ యొక్క పరిమాణం గురించి మాట్లాడటం.

65
00:03:13,440 --> 00:03:15,190
ఆ డేటా వార్తలు సెట్
పరిమాణం, సంఖ్య

66
00:03:15,190 --> 00:03:17,050
స్ట్రింగ్ తయారు చేసే అక్షరాలు.

67
00:03:17,050 --> 00:03:20,090
మేము ఒక గురించి మాట్లాడుతూ ఉంటే
ఫైళ్లు ప్రాసెస్ అల్గోరిథం,

68
00:03:20,090 --> 00:03:23,930
మేము ఎలా గురించి మాట్లాడుతూ ఉండవచ్చు
అనేక కిలోబైట్లు ఆ ఫైల్ వహిస్తాయి.

69
00:03:23,930 --> 00:03:25,710
మరియు ఆ డేటా సమితి యొక్క.

70
00:03:25,710 --> 00:03:28,870
మేము ఒక అల్గోరిథం గురించి మాట్లాడుతూ ఉంటే
ఆ, మరింత సాధారణంగా శ్రేణుల నిర్వహిస్తుంది

71
00:03:28,870 --> 00:03:31,510
ఇటువంటి సార్టింగ్ అల్గోరిథంలు వంటి
లేదా అల్గోరిథంలు శోధించడం,

72
00:03:31,510 --> 00:03:36,690
మేము బహుశా సంఖ్య గురించి మాట్లాడటం చేస్తున్నాం
వ్యూహం కలిగి అంశాల.

73
00:03:36,690 --> 00:03:39,272
>> ఇప్పుడు, మేము ఒక అంచనా వేయవచ్చు
అల్గోరిథం ముఖ్యంగా,

74
00:03:39,272 --> 00:03:40,980
నేను చెప్పినప్పుడు మేము
నేను ఒక అల్గోరిథం కొలిచేందుకు

75
00:03:40,980 --> 00:03:43,840
మేము ఎలా అంచనా వేయవచ్చు అర్థం
అనేక వనరులు అది తీసుకుంటుంది.

76
00:03:43,840 --> 00:03:48,990
ఆ వనరులను ఉన్నాయి లేదో, ఎన్ని
RAM యొక్క బైట్లు లేదా RAM యొక్క మెగాబైట్ల

77
00:03:48,990 --> 00:03:49,790
ఇది ఉపయోగిస్తుంది.

78
00:03:49,790 --> 00:03:52,320
లేదా ఎంత సమయం రన్ పడుతుంది.

79
00:03:52,320 --> 00:03:56,200
మరియు మేము ఈ కాల్ చేయవచ్చు
n యొక్క f, ఏకపక్ష, కొలిచేందుకు.

80
00:03:56,200 --> 00:03:59,420
ఎక్కడ n సంఖ్య
డేటా సెట్ లో అంశాలు.

81
00:03:59,420 --> 00:04:02,640
మరియు n యొక్క f ఎన్ని somethings ఉంది.

82
00:04:02,640 --> 00:04:07,530
ఎన్ని వనరుల యూనిట్లు చేస్తుంది
ఆ డేటా ప్రాసెస్ అవసరం.

83
00:04:07,530 --> 00:04:10,030
>> ఇప్పుడు, మేము నిజంగా పట్టించుకోను
సరిగ్గా n యొక్క f ఏమిటి గురించి.

84
00:04:10,030 --> 00:04:13,700
నిజానికి, మేము చాలా అరుదుగా అభీష్టం
ఖచ్చితంగా ఎప్పటికీ ఈ తరగతి నేను

85
00:04:13,700 --> 00:04:18,709
ఏ నిజంగా లోతైన ప్రవేశిస్తాడు
యొక్క f n అని ఏ విశ్లేషణ.

86
00:04:18,709 --> 00:04:23,510
మేము కేవలం ఏమి f గురించి మాట్లాడటానికి వెళుతున్న
n సుమారు లేదా దానిని కలిగి ఉంటుంది.

87
00:04:23,510 --> 00:04:27,600
మరియు ఒక అల్గోరిథం యొక్క ప్రవృత్తి
దాని అత్యధిక ఆర్డర్ పదం రాయించుకున్నాడు.

88
00:04:27,600 --> 00:04:29,440
మరియు మేము ఏమి చూడగలరు నేను
తీసుకొని ఆ అర్ధం

89
00:04:29,440 --> 00:04:31,910
ఒక మరింత కాంక్రీటు ఉదాహరణ చూడండి.

90
00:04:31,910 --> 00:04:34,620
>> కాబట్టి యొక్క మేము చెబుతాను
మూడు వేర్వేరు అల్గోరిథంలు.

91
00:04:34,620 --> 00:04:39,350
వీటిలో మొదటి n పడుతుంది
వనరుల ఆరోపించింది, కొన్ని యూనిట్లు

92
00:04:39,350 --> 00:04:42,880
పరిమాణం n యొక్క ఒక డేటా సమితి ప్రాసెస్.

93
00:04:42,880 --> 00:04:47,000
మేము పడుతుంది అని రెండవ అల్గోరిథం కలిగి
ఆరోపించింది ప్లస్ స్క్వేర్డ్ n వనరులు n

94
00:04:47,000 --> 00:04:49,350
పరిమాణం n యొక్క ఒక డేటా సమితి ప్రాసెస్.

95
00:04:49,350 --> 00:04:52,030
మరియు మేము ఒక మూడవ
ఆ in-- నడుస్తుంది ఆ అల్గోరిథం

96
00:04:52,030 --> 00:04:58,300
తీసుకుంటుంది n cubed మైనస్ 8n స్క్వేర్డ్
వనరుల ప్లస్ 20 N యూనిట్లు

97
00:04:58,300 --> 00:05:02,370
ఒక అల్గోరిథం ప్రాసెస్
n పరిమాణం సెట్ డేటా.

98
00:05:02,370 --> 00:05:05,594
>> ఇప్పుడు మళ్ళీ, మేము నిజంగా వెళ్ళడం లేదు
వివరాలు ఈ స్థాయి పొందడానికి.

99
00:05:05,594 --> 00:05:08,260
నేను ఈ అప్ నిజంగా చేస్తున్నాను
ఇక్కడ ఒక పాయింట్ యొక్క దృష్టాంతం

100
00:05:08,260 --> 00:05:10,176
నేను వెళుతున్న
, రెండవ దానిలో అయింది

101
00:05:10,176 --> 00:05:12,980
మేము మాత్రమే నిజంగా పట్టించుకోను ఉంది
విషయాలు ధోరణి గురించి

102
00:05:12,980 --> 00:05:14,870
డేటా సమితుల పెద్ద పొందుటకు గా.

103
00:05:14,870 --> 00:05:18,220
డేటా సెట్ చిన్న చేస్తే, అక్కడ
నిజానికి ఒక అందమైన పెద్ద తేడా

104
00:05:18,220 --> 00:05:19,870
ఈ అల్గోరిథంలు లో.

105
00:05:19,870 --> 00:05:23,000
అక్కడ మూడవ అల్గోరిథం
13 సార్లు ఇక పడుతుంది

106
00:05:23,000 --> 00:05:27,980
వనరుల 13 సార్లు మొత్తం
మొదటి ఒకటి సాపేక్ష అమలు.

107
00:05:27,980 --> 00:05:31,659
>> మా డేటా సెట్ పరిమాణం 10, ఉంటే ఇది
పెద్ద, కానీ తప్పనిసరిగా భారీ కాదు

108
00:05:31,659 --> 00:05:33,950
మేము అక్కడ ఆ చూడగలరు
నిజానికి తేడా యొక్క ఒక బిట్.

109
00:05:33,950 --> 00:05:36,620
మూడవ అల్గోరిథం
మరింత సమర్థవంతంగా అవుతుంది.

110
00:05:36,620 --> 00:05:40,120
ఇది నిజానికి 40% గురించి -
లేదా 60% ఎక్కువ సమర్థవంతమైన.

111
00:05:40,120 --> 00:05:41,580
ఇది 40% సమయం మొత్తం పడుతుంది.

112
00:05:41,580 --> 00:05:45,250
ఇది తీసుకోవాలని చేయవచ్చు, రన్ చేయవచ్చు
వనరుల 400 యూనిట్లు

113
00:05:45,250 --> 00:05:47,570
పరిమాణం 10 యొక్క ఒక డేటా సమితి ప్రాసెస్.

114
00:05:47,570 --> 00:05:49,410
మొదటి అయితే
అల్గోరిథం, దీనికి విరుద్ధంగా,

115
00:05:49,410 --> 00:05:54,520
వనరుల 1,000 యూనిట్లు పడుతుంది
పరిమాణం 10 యొక్క ఒక డేటా సమితి ప్రాసెస్.

116
00:05:54,520 --> 00:05:57,240
కానీ ఏమి జరుగుతుందో గమనించు
మా సంఖ్యలు కూడా పెద్ద పొందండి.

117
00:05:57,240 --> 00:05:59,500
>> ఇప్పుడు, తేడా
ఈ అల్గోరిథంలు మధ్య

118
00:05:59,500 --> 00:06:01,420
కొద్దిగా తక్కువ స్పష్టమైన మారింది మొదలు.

119
00:06:01,420 --> 00:06:04,560
ఉన్నాయి మరియు నిజానికి
దిగువ ఆర్డర్ పదాలు లేదా,

120
00:06:04,560 --> 00:06:09,390
తక్కువ exponents-- అవగాహనకు
అసంబద్ధం మారింది మొదలు.

121
00:06:09,390 --> 00:06:12,290
ఒక డేటా సమితి పరిమాణం యొక్క ఉంటే
1000 మరియు మొదటి అల్గోరిథం

122
00:06:12,290 --> 00:06:14,170
ఒక బిలియన్ దశల్లో నడుస్తుంది.

123
00:06:14,170 --> 00:06:17,880
మరియు రెండవ అల్గోరిథం లో నడుస్తుంది
ఒక బిలియన్ మరియు ఒక మిలియన్ దశలను.

124
00:06:17,880 --> 00:06:20,870
మరియు మూడవ అల్గోరిథం నడుస్తుంది
ఒక బిలియన్ దశలను కేవలం పిరికి లో.

125
00:06:20,870 --> 00:06:22,620
ఇది చాలా చక్కని ఒక బిలియన్ దశలను ఉంది.

126
00:06:22,620 --> 00:06:25,640
ఆ దిగువ ఆర్డర్ నిబంధనలు మొదలు
నిజంగా అసంబద్ధం మారింది.

127
00:06:25,640 --> 00:06:27,390
మరియు కేవలం నిజంగా
హోమ్ సుత్తి పాయింట్

128
00:06:27,390 --> 00:06:31,240
డేటా ఇన్పుట్ పరిమాణం ఒక యొక్క ఉంటే
million-- వీటిలో మూడు అందంగా చాలా

129
00:06:31,240 --> 00:06:34,960
ఒక quintillion-- ఉంటే పడుతుంది
నా గణిత correct-- దశలను ఉంది

130
00:06:34,960 --> 00:06:37,260
ఒక డేటా ఇన్పుట్ ప్రాసెస్
పరిమాణం ఒక మిలియన్.

131
00:06:37,260 --> 00:06:38,250
ఆ దశలను చాలా ఉంది.

132
00:06:38,250 --> 00:06:42,092
నిజానికి వారికి ఒక మైట్
ఒక జంట 100,000, లేదా ఒక జంట పడుతుంది 100

133
00:06:42,092 --> 00:06:44,650
మిలియన్ కూడా తక్కువ ఉన్నప్పుడు
మేము అనేక గురించి మాట్లాడటం చేస్తున్నాం

134
00:06:44,650 --> 00:06:46,990
ఆ రకమైన అసంబద్ధం big--.

135
00:06:46,990 --> 00:06:50,006
వారు అన్ని సమయం తీసుకుంటారు
సుమారు n cubed,

136
00:06:50,006 --> 00:06:52,380
అందువలన మేము నిజానికి కాలాన్ని
ఈ అల్గోరిథంలు యొక్క అన్ని

137
00:06:52,380 --> 00:06:59,520
n యొక్క ఆర్డర్ మీద గా
ఆరోపించింది లేదా n cubed పెద్ద O.

138
00:06:59,520 --> 00:07:03,220
>> ఇక్కడ మరింత కొన్ని జాబితా ఉంది
సాధారణ గణన సంక్లిష్టత తరగతుల

139
00:07:03,220 --> 00:07:05,820
మేము లో చూస్తారు ఆ
అల్గోరిథంలు సాధారణంగా.

140
00:07:05,820 --> 00:07:07,970
మరియు కూడా ప్రత్యేకంగా CS50 లో.

141
00:07:07,970 --> 00:07:11,410
ఈ నుండి ఆదేశాలు
సాధారణంగా ఎగువన అతివేగంగా

142
00:07:11,410 --> 00:07:13,940
దిగువన సాధారణంగా నెమ్మదైన స్థాయి వరకు.

143
00:07:13,940 --> 00:07:16,920
కాబట్టి స్థిరంగా సమయం అల్గోరిథంలు ఉంటాయి
సంబంధం లేకుండా వేగంగా ఉండాలి,

144
00:07:16,920 --> 00:07:19,110
పరిమాణంతో
డేటా ఇన్పుట్ మీరు పాస్.

145
00:07:19,110 --> 00:07:23,760
వారు ఎల్లప్పుడూ ఒక ఆపరేషన్ పడుతుంది లేదా
ఎదుర్కోవటానికి వనరుల ఒక యూనిట్.

146
00:07:23,760 --> 00:07:25,730
ఇది 2 కావచ్చు, అది బలం
3, 4 కావచ్చు.

147
00:07:25,730 --> 00:07:26,910
కానీ అది స్థిరమైన నెంబర్.

148
00:07:26,910 --> 00:07:28,400
ఇది మారుతూ లేదు.

149
00:07:28,400 --> 00:07:31,390
>> సంవర్గమాన సమయం అల్గోరిథంలు
కాస్త మెరుగని చెప్పవచ్చు.

150
00:07:31,390 --> 00:07:33,950
మరియు ఒక మంచి ఉదాహరణకు
ఒక సంవర్గమాన సమయం అల్గోరిథం

151
00:07:33,950 --> 00:07:37,420
మీరు ఇప్పుడు ద్వారా ఖచ్చితంగా చూసిన చేసిన
ఫోన్ బుక్ కాకుండా చిరిగిపోవడానికి

152
00:07:37,420 --> 00:07:39,480
ఫోన్ బుక్ లో మైక్ స్మిత్ కనుగొనేందుకు.

153
00:07:39,480 --> 00:07:40,980
మేము సగం సమస్య కట్.

154
00:07:40,980 --> 00:07:43,580
మరియు n పెద్ద గెట్స్ కాబట్టి
ఇది పెద్దగా larger--

155
00:07:43,580 --> 00:07:47,290
నిజానికి, ప్రతిసారీ మీరు రెట్టింపు
n, ఇది ఒకే ఒక్క మరింత అడుగు పడుతుంది.

156
00:07:47,290 --> 00:07:49,770
ఆ చాలా ఉత్తమం కాబట్టి
కంటే, చెప్పటానికి, సరళ సమయం.

157
00:07:49,770 --> 00:07:53,030
మీరు n రెట్టింపు అయితే ఇది ఉంది
దశలను సంఖ్య రెట్టింపు పడుతుంది.

158
00:07:53,030 --> 00:07:55,980
మీరు n మూడు రెట్లు ఉంటే, అది పడుతుంది
దశలను సంఖ్య మూడు రెట్లు.

159
00:07:55,980 --> 00:07:58,580
యూనిట్కు ఒక అడుగు.

160
00:07:58,580 --> 00:08:01,790
>> అప్పుడు విషయాలు కొద్దిగా more-- పొందండి
కొద్దిగా తక్కువ గొప్ప అక్కడ నుండి.

161
00:08:01,790 --> 00:08:06,622
మీరు కొన్నిసార్లు, సరళ లయ సమయం
లాగ్ సరళ సమయం అని లేదా కేవలం n లాగ్ n.

162
00:08:06,622 --> 00:08:08,330
మరియు మేము ఒక ఉదాహరణగా చేస్తాము
ఒక అల్గోరిథం యొక్క

163
00:08:08,330 --> 00:08:13,370
ఇప్పటికీ ఉత్తమం, n లాగ్ n, పరుగులు
కంటే వర్గ time-- n స్క్వేర్డ్.

164
00:08:13,370 --> 00:08:17,320
లేదా బహుపది సమయం, n రెండు
రెండు కంటే ఎక్కువ ఎన్ని.

165
00:08:17,320 --> 00:08:20,810
లేదా ఘాతీయ సమయం, ఇది
కూడా worse-- సి n ఉంది.

166
00:08:20,810 --> 00:08:24,670
సో కొన్ని స్థిరమైన సంఖ్య ఎదిగింది
ఇన్పుట్ పరిమాణం యొక్క శక్తి.

167
00:08:24,670 --> 00:08:28,990
అలా అయితే 1,000-- ఉంది ఉంటే
డేటా ఇన్పుట్, పరిమాణం 1,000 ఉంది

168
00:08:28,990 --> 00:08:31,310
ఇది 1,000 వ అధికారంలోకి సి పడుతుందని.

169
00:08:31,310 --> 00:08:33,559
ఇది బహుపది సమయం కంటే చాలా దారుణంగా ఉంది.

170
00:08:33,559 --> 00:08:35,030
>> కారకమైన సమయం చెత్తగా ఉంది.

171
00:08:35,030 --> 00:08:37,760
నిజానికి, నిజంగా అక్కడ
అపారమైన సమయం అల్గోరిథంలు ఉనికిలో,

172
00:08:37,760 --> 00:08:43,740
దీని ఇటువంటి అని పిలవబడే, తెలివితక్కువదని విధమైన
ఉద్యోగం యాదృచ్ఛికంగా వ్యూహం షఫుల్

173
00:08:43,740 --> 00:08:45,490
ఆపై చూడటానికి తనిఖీ
లేదో అది క్రమబద్ధీకరించబడతాయి.

174
00:08:45,490 --> 00:08:47,589
మరియు ఇది యాదృచ్చికంగా కాదు ఉంటే
మళ్ళీ శ్రేణి షఫుల్

175
00:08:47,589 --> 00:08:49,130
మరియు అది క్రమబద్ధీకరించబడతాయి లేదో చూడండి.

176
00:08:49,130 --> 00:08:51,671
మరియు మీరు బహుశా imagine-- చేయవచ్చు
మీరు ఒక పరిస్థితి ఊహించే

177
00:08:51,671 --> 00:08:55,200
పేరు చెత్త సందర్భంలో, ఆ సంకల్పం
నిజానికి శ్రేణి ప్రారంభం ఎప్పుడూ.

178
00:08:55,200 --> 00:08:57,150
ఆ అల్గోరిథం ఎప్పటికీ అమలు.

179
00:08:57,150 --> 00:08:59,349
అందువలన, ఉంటుంది
అపారమైన సమయం అల్గోరిథం.

180
00:08:59,349 --> 00:09:01,890
ఆశాజనక మీరు రాయడం కాదు
ఏ కారకమైన లేదా అనంతమైన సమయం

181
00:09:01,890 --> 00:09:04,510
CS50 లో అల్గోరిథంలు.

182
00:09:04,510 --> 00:09:09,150
>> కాబట్టి, యొక్క తీసుకుందాం కొంచెం
కొన్ని సులభమైన వద్ద కాంక్రీట్ లుక్

183
00:09:09,150 --> 00:09:11,154
గణన సంక్లిష్టత తరగతులు.

184
00:09:11,154 --> 00:09:13,070
కాబట్టి మేము ఒక ఉదాహరణలో కలిగి
లేదా రెండు ఉదాహరణలు ఇక్కడ

185
00:09:13,070 --> 00:09:15,590
స్థిరంగా సమయం అల్గోరిథంలు యొక్క,
ఇది ఎల్లప్పుడూ పడుతుంది

186
00:09:15,590 --> 00:09:17,980
చెత్త-సందర్భంలో ఒకే ఆపరేషన్.

187
00:09:17,980 --> 00:09:20,050
మొదటి ఉదాహరణలో కాబట్టి
మేము ఒక ఫంక్షన్ కలిగి

188
00:09:20,050 --> 00:09:23,952
మీరు కోసం 4 అనే పేరుతో సూచించిన
పరిమాణం 1,000 వ్యూహం పడుతుంది.

189
00:09:23,952 --> 00:09:25,660
కానీ అప్పుడు స్పష్టంగా
నిజానికి కనిపించడం లేదు

190
00:09:25,660 --> 00:09:29,000
దానిని నిజంగా ఏమిటి పట్టించుకోరు వద్ద
, అది లోపలి శ్రేణి యొక్క.

191
00:09:29,000 --> 00:09:30,820
ఎల్లప్పుడూ కేవలం నాలుగు తిరిగి.

192
00:09:30,820 --> 00:09:32,940
కాబట్టి, ఆ అల్గోరిథం,
ఇది వాస్తవం ఉన్నప్పటికీ

193
00:09:32,940 --> 00:09:35,840
1,000 అంశాలు లేదు పడుతుంది
వారితో ఏదైనా.

194
00:09:35,840 --> 00:09:36,590
జస్ట్ నాలుగు తిరిగి.

195
00:09:36,590 --> 00:09:38,240
ఇది ఎల్లప్పుడూ ఒకే దశలో ఉంది.

196
00:09:38,240 --> 00:09:41,600
>> నిజానికి, 2 nums-- జోడించండి
మేము well-- ముందు చూసిన

197
00:09:41,600 --> 00:09:43,680
కేవలం రెండు పూర్ణాంకాల ప్రాసెస్.

198
00:09:43,680 --> 00:09:44,692
ఇది ఒకే దశలో కాదు.

199
00:09:44,692 --> 00:09:45,900
ఇది నిజానికి ఒక జంట దశలను ఉంది.

200
00:09:45,900 --> 00:09:50,780
మీరు ఒక పొందుటకు, మీరు బి పొందుటకు, మీరు వాటిని జోడించండి
కలిసి, మరియు మీరు అవుట్పుట్ ఫలితాలు.

201
00:09:50,780 --> 00:09:53,270
కాబట్టి ఇది 84 దశలను ఉంది.

202
00:09:53,270 --> 00:09:55,510
కానీ అది ఎప్పుడూ స్థిరంగా ఉంది
సంబంధం లేకుండా లేదా బి యొక్క.

203
00:09:55,510 --> 00:09:59,240
మీరు ఒక తీసుకురావాలి, బి పొందండి జోడించండి
కలిసి, వాటిని అవుట్పుట్ ఫలితంగా.

204
00:09:59,240 --> 00:10:02,900
కాబట్టి ఒక స్థిరమైన సమయం అల్గోరిథం యొక్క.

205
00:10:02,900 --> 00:10:05,170
>> ఇక్కడ ఒక యొక్క ఒక ఉదాహరణ వార్తలు
సరళ సమయం అల్గోరిథం

206
00:10:05,170 --> 00:10:08,740
ఆ పడుతుంది gets-- ఒక అల్గోరిథం
ఒక అదనపు దశను, బహుశా

207
00:10:08,740 --> 00:10:10,740
మీ ఇన్పుట్ 1 వృధ్ధి.

208
00:10:10,740 --> 00:10:14,190
కాబట్టి, యొక్క మేము చూస్తున్న సే తెలియజేయండి
వ్యూహం సంఖ్య 5 లోపల.

209
00:10:14,190 --> 00:10:16,774
మీరు ఒక పరిస్థితి కలిగి ఉండవచ్చు
మీరు చాలా ప్రారంభ వెదుక్కోవచ్చు.

210
00:10:16,774 --> 00:10:18,606
కానీ మీరు కూడా కాలేదు
పరిస్థితి ఇది

211
00:10:18,606 --> 00:10:20,450
శ్రేణి యొక్క చివరి మూలకం కావచ్చు.

212
00:10:20,450 --> 00:10:23,780
పరిమాణం 5 యొక్క వ్యూహం, ఉంటే
మేము సంఖ్య 5 చూస్తున్న.

213
00:10:23,780 --> 00:10:25,930
ఇది 5 దశలను పడుతుంది.

214
00:10:25,930 --> 00:10:29,180
నిజానికి, అక్కడ మనకు ఊహించుకోండి
ఈ శ్రేణి లో లేదు 5 ఎక్కడైనా.

215
00:10:29,180 --> 00:10:32,820
మేము ఇంకా నిజానికి చూడటానికి కలిగి
యెరే యొక్క ప్రతి మూలకం

216
00:10:32,820 --> 00:10:35,550
నిర్ధారించేందుకు
లేదో 5 ఉంది.

217
00:10:35,550 --> 00:10:39,840
>> అలా అని ఇది చెత్త సందర్భంలో,
మూలకం శ్రేణి చివరి ఉంది

218
00:10:39,840 --> 00:10:41,700
లేదా అన్ని వద్ద ఉనికిలో లేదు.

219
00:10:41,700 --> 00:10:44,690
మేము ఇంకా చూడండి కలిగి
n మూలకాలు అన్ని.

220
00:10:44,690 --> 00:10:47,120
అందువలన ఈ అల్గోరిథం
సరళ సమయంలో నడుస్తుంది.

221
00:10:47,120 --> 00:10:50,340
మీరు ద్వారా నిర్ధారించండి చేయవచ్చు
ఈ విధంగా ఒక చిన్న బిట్ extrapolating,

222
00:10:50,340 --> 00:10:53,080
మేము ఒక 6-మూలకం శ్రేణి కలిగి ఉంటే
మేము సంఖ్య 5 వెతుకుతున్న

223
00:10:53,080 --> 00:10:54,890
ఇది 6 దశలను పడుతుంది.

224
00:10:54,890 --> 00:10:57,620
మేము ఒక 7-మూలకం శ్రేణి కలిగి ఉంటే
మేము సంఖ్య 5 చూస్తున్న.

225
00:10:57,620 --> 00:10:59,160
ఇది 7 దశలను పడుతుంది.

226
00:10:59,160 --> 00:11:02,920
మేము మరో మూలకం జోడించండి మా
శ్రేణి, ఇది ఒక మరింత అడుగు పడుతుంది.

227
00:11:02,920 --> 00:11:06,750
ఒక సరళ అల్గోరిథం యొక్క
చెత్త-కేసు.

228
00:11:06,750 --> 00:11:08,270
>> జంట మీరు త్వరగా ప్రశ్నలు.

229
00:11:08,270 --> 00:11:11,170
ఏమిటి runtime-- ఏమిటి
runtime కేసు

230
00:11:11,170 --> 00:11:13,700
కోడ్ యొక్క ఈ ప్రత్యేక స్నిప్పెట్?

231
00:11:13,700 --> 00:11:17,420
నేను నడుస్తుంది ఇక్కడ ఒక 4 లూప్ కలిగి
j 0, చి అన్ని మార్గం అప్ సమానం నుండి.

232
00:11:17,420 --> 00:11:21,980
మరియు నేను ఏ ఇక్కడ చూసిన వెబ్, అని
లూప్ యొక్క శరీరం స్థిరంగా సమయంలో నడుస్తుంది.

233
00:11:21,980 --> 00:11:24,730
కాబట్టి పరిభాష ఉపయోగించి
మేము ఇప్పటికే గురించి మాట్లాడారు చేసిన

234
00:11:24,730 --> 00:11:29,390
చెత్త-సందర్భంలో ఉంటుంది
ఈ అల్గోరిథం యొక్క రన్టైమ్?

235
00:11:29,390 --> 00:11:31,050
రెండవ తీసుకోండి.

236
00:11:31,050 --> 00:11:34,270
లూప్ యొక్క లోపలి భాగం
స్థిరంగా సమయంలో నడుస్తుంది.

237
00:11:34,270 --> 00:11:37,510
మరియు వెలుపలి భాగం
లూప్ m సార్లు అమలు కానుంది.

238
00:11:37,510 --> 00:11:40,260
కాబట్టి చెత్త-runtime కేసు ఇక్కడ ఏమి ఉంది?

239
00:11:40,260 --> 00:11:43,210
మీరు M పెద్ద O అంచనా తెలుసా?

240
00:11:43,210 --> 00:11:44,686
మీరు కుడి భావించాలి.

241
00:11:44,686 --> 00:11:46,230
>> ఎలా మరొక గురించి?

242
00:11:46,230 --> 00:11:48,590
మేము ఒక కలిగి ఈ సమయంలో
ఒక లూప్ యొక్క లోపల లూప్.

243
00:11:48,590 --> 00:11:50,905
మేము ఒక బాహ్య లూప్ కలిగి
సున్నా నుండి పేజి నడుస్తుంది.

244
00:11:50,905 --> 00:11:54,630
మరియు మేము నడుస్తుంది అని ఒక అంతర్గత లూప్ కలిగి
సున్నా నుంచి p, మరియు ఆ లోపల

245
00:11:54,630 --> 00:11:57,890
నేను స్టేట్ శరీరం
లూప్ స్థిరంగా సమయంలో నడుస్తుంది.

246
00:11:57,890 --> 00:12:02,330
కాబట్టి చెత్త-runtime కేసు ఏమిటి
కోడ్ యొక్క ఈ ప్రత్యేక స్నిప్పెట్?

247
00:12:02,330 --> 00:12:06,140
Well, మళ్ళీ, మేము ఒక కలిగి
p సార్లు నడుస్తుంది, ఆ బయటి లూప్.

248
00:12:06,140 --> 00:12:09,660
మరియు ప్రతి time-- మళ్ళా
ఆ లూప్ యొక్క, బదులుగా.

249
00:12:09,660 --> 00:12:13,170
మేము ఒక అంతర్గత లూప్ కలిగి
కూడా p సార్లు నడుస్తుంది.

250
00:12:13,170 --> 00:12:16,900
ఆ లోపలి ఆపై, ఉంది
అక్కడ స్థిరంగా time-- చిన్న స్నిప్పెట్.

251
00:12:16,900 --> 00:12:19,890
>> మేము ఒక బాహ్య లూప్ కలిగి ఉంటే కాబట్టి ఆ
వీటిలో లోపల p సార్లు నడుస్తుంది

252
00:12:19,890 --> 00:12:22,880
అంతర్గత లూప్ ఆ
ఏమి సార్లు పునరావృతం పే నడుస్తుంది

253
00:12:22,880 --> 00:12:26,480
runtime కేసు
కోడ్ యొక్క ఈ స్నిప్పెట్?

254
00:12:26,480 --> 00:12:30,730
మీరు p పెద్ద స్క్వేర్డ్ ఓ అంచనా తెలుసా?

255
00:12:30,730 --> 00:12:31,690
>> నేను డౌ లాయిడ్ ఉన్నాను.

256
00:12:31,690 --> 00:12:33,880
ఈ CS50 ఉంది.

257
00:12:33,880 --> 00:12:35,622