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

2
00:00:05,830 --> 00:00:07,910
>> બધા હક છે, તેથી, ગણતરીની જટિલતા.

3
00:00:07,910 --> 00:00:10,430
ચેતવણી માત્ર એક બીટ
આપણે પણ અત્યાર સુધી લગભગ ડાઇવ પહેલાં

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
સામગ્રી પૈસા, રેમ, તમામ પ્રકારની છે.

18
00:00:47,980 --> 00:00:52,090
>> તેથી, સક્ષમ હોવા એક વિશ્લેષણ કરવા માટે
અલ્ગોરિધમનો, આ સાધન સમૂહ નો ઉપયોગ

19
00:00:52,090 --> 00:00:56,110
મૂળભૂત રીતે, આ question-- પૂછે
આ અલ્ગોરિધમનો પાયે કેવી રીતે

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
ઠીક છે, કે કેવી રીતે પર આધાર રાખે છે
અમે અલ્ગોરિધમનો વિશ્લેષણ,

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
અમે સામાન્ય રીતે ખરાબ કેસ કૉલ
અલ્ગોરિધમનો મોટા ઓ રનટાઇમ.

38
00:01:51,450 --> 00:01:56,770
તેથી એક અલ્ગોરિધમનો કહી શકાય
સ્ક્વેર્ડ n અથવા n ના ઓ હે ચલાવો.

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
અમે ક્યારેક કે નો સંદર્ભ લો
મોટા ઓમેગા, મોટા ઓ સાથે વિપરીત છે, તેથી

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
વિજ્ઞાન અને ક્ષેત્રો છે
સામગ્રી આ પ્રકારની માટે સમર્પિત.

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
વેલ, એક માહિતી સમૂહ શું છે?

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 ના એફ, આપખુદ માપે છે.

80
00:03:56,200 --> 00:03:59,420
જ્યાં n સંખ્યા છે
માહિતી સમૂહ માં તત્વો છે.

81
00:03:59,420 --> 00:04:02,640
અને એન એફ કેટલા somethings છે.

82
00:04:02,640 --> 00:04:07,530
કેવી રીતે ઘણા સ્રોતો એકમો કરે
તે માહિતી પર પ્રક્રિયા કરવા માટે જરૂરી છે.

83
00:04:07,530 --> 00:04:10,030
>> હવે, અમે ખરેખર કાળજી નથી
બરાબર એ એફ શું છે વિશે.

84
00:04:10,030 --> 00:04:13,700
હકીકતમાં, અમે ખૂબ જ ભાગ્યે જ will--
ચોક્કસપણે કરશે ક્યારેય આ વર્ગ હું

85
00:04:13,700 --> 00:04:18,709
કોઈ પણ ખરેખર ઊંડા માં ડાઇવ
એફ એ શું છે વિશ્લેષણ.

86
00:04:18,709 --> 00:04:23,510
અમે હમણાં જ શું એફ વિશે વાત કરવા જઈ રહ્યાં છો
એ આશરે અથવા શું તે જોવા મળે છે.

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 લે
સાધનો cubed, કેટલાક એકમો

92
00:04:39,350 --> 00:04:42,880
માપ n એક માહિતી સમૂહ પર પ્રક્રિયા કરવા માટે.

93
00:04:42,880 --> 00:04:47,000
અમે લે છે કે બીજા અલ્ગોરિધમનો હોય
cubed વત્તા સ્ક્વેર્ડ n સાધનો n

94
00:04:47,000 --> 00:04:49,350
માપ n એક માહિતી સમૂહ પર પ્રક્રિયા કરવા માટે.

95
00:04:49,350 --> 00:04:52,030
અને અમે ત્રીજા છે
કે વાહ ચાલે છે અલ્ગોરિધમનો

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
તે લઇ શકે છે run-- કરી શકો છો
સાધનો 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
ત્યાં છે અને તે હકીકત એ છે કે
નીચલા ક્રમના terms-- અથવા બદલે,

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 ના ક્રમ પર હોવાથી
cubed અથવા 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
અને એન મોટા નોંધાયો નહીં, જેથી
અને મોટા અને 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
તમે એ ડબલ જે જો તે છે,
પગલાંઓ ડબલ સંખ્યા લે છે.

158
00:07:53,030 --> 00:07:55,980
તમે એ ત્રણ ગણો, તો તે લે છે
પગલાંઓ સંખ્યા ત્રણ ગણો.

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
અથવા બહુપદી સમય, એ બે
બે કરતાં વધારે કોઈપણ સંખ્યા.

165
00:08:17,320 --> 00:08:20,810
અથવા ઘાતાંકીય સમય છે, જે
પણ worse-- સી એન છે.

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-- ઉમેરો જે
અમે પરિચિત હોઈ શકે તે પહેલાં જોઇ છે

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
પરંતુ તે હંમેશા સતત છે
અનુલક્ષીને A અથવા B છે.

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
અમે હજુ પણ જોવા મળે છે
એન બધા તત્વો.

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-- શું છે
આ રનટાઈમ સૌથી ખરાબ કેસ

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
તેથી પરિભાષા મદદથી
અમે પહેલાથી જ શું about-- વાત કરી છે

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
અને બાહ્ય ભાગ
લૂપ એમ વખત ચલાવવા માટે જતા હોય છે.

238
00:11:37,510 --> 00:11:40,260
તેથી રનટાઈમ સૌથી ખરાબ કેસ અહીં શું છે?

239
00:11:40,260 --> 00:11:43,210
તમે એમ મોટા-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
અને અમે બનાવ્યા છે કે આંતરિક લૂપ છે
શૂન્ય માંથી પી, અને તે અંદર,

245
00:11:54,630 --> 00:11:57,890
હું રાજ્ય શરીર કે
લૂપ સતત સમય ચાલે છે.

246
00:11:57,890 --> 00:12:02,330
તેથી રનટાઈમ સૌથી ખરાબ કેસ શું છે
કોડ આ ખાસ સ્નિપેટ?

247
00:12:02,330 --> 00:12:06,140
વેલ, ફરી, અમે એક છે
પી વાર ચાલે છે કે બાહ્ય લૂપ.

248
00:12:06,140 --> 00:12:09,660
અને દરેક time-- પુનરાવૃત્તિ
કે લૂપ બદલે.

249
00:12:09,660 --> 00:12:13,170
અમે એક આંતરિક લૂપ છે
તે પણ પી વખત ચાલે છે.

250
00:12:13,170 --> 00:12:16,900
કે અંદર અને પછી, ત્યાં
ત્યાં સતત time-- ઓછી સ્નીપેટ.

251
00:12:16,900 --> 00:12:19,890
>> અમે એક બાહ્ય લૂપ છે, તેથી જો કે
જે અંદર પી વાર ચાલે છે

252
00:12:19,890 --> 00:12:22,880
આંતરિક લૂપ કે
શું times-- પી ચાલે

253
00:12:22,880 --> 00:12:26,480
આ રનટાઈમ સૌથી ખરાબ કેસ
કોડ આ સ્નીપેટ?

254
00:12:26,480 --> 00:12:30,730
તમે પી મોટા-O સ્ક્વેર્ડ ધારી હતી?

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