1
00:00:00,000 --> 00:00:02,892
>> [સંગીત વગાડવાનો]

2
00:00:02,892 --> 00:00:05,347

3
00:00:05,347 --> 00:00:07,180
ડો LLOYD: લીનિયર
શોધ અલ્ગોરિધમનો અમે છે

4
00:00:07,180 --> 00:00:09,840
એક એરે એક તત્વ શોધવા માટે ઉપયોગ કરી શકો છો.

5
00:00:09,840 --> 00:00:11,990
એક એલ્ગોરિધમ રિકોલ
એક પગલું દ્વારા પગલું સમૂહ છે

6
00:00:11,990 --> 00:00:15,030
એક કાર્ય પૂર્ણ કરવા માટે સૂચનો.

7
00:00:15,030 --> 00:00:17,480
>> રેખીય શોધ
નીચે પ્રમાણે અલ્ગોરિધમનો કામ કરે છે.

8
00:00:17,480 --> 00:00:22,200
ડાબેથી એરે ફરી વળવું સમગ્ર
અધિકાર સ્પષ્ટ તત્વ માટે જોઈ.

9
00:00:22,200 --> 00:00:26,380
>> સ્યુડોકોડનો માં જે વધુ
આ સજા નિસ્યંદિત આવૃત્તિ

10
00:00:26,380 --> 00:00:29,840
પ્રથમ તત્વ છે તો શું
તમે બંધ કરી શકો છો શોધી રહ્યાં છે.

11
00:00:29,840 --> 00:00:33,930
નહિંતર, આગામી તત્વ ખસેડવા અને
તમે શોધવા સુધી અને ઉપર ચાલુ રાખવા

12
00:00:33,930 --> 00:00:36,389
તત્વ, અથવા તમે નથી.

13
00:00:36,389 --> 00:00:38,680
તેથી અમે રેખીય ઉપયોગ કરી શકો છો
શોધ અલ્ગોરિધમનો, ઉદાહરણ તરીકે,

14
00:00:38,680 --> 00:00:42,330
લક્ષ્ય કિંમત શોધવા માટે
આ એરે નવ.

15
00:00:42,330 --> 00:00:43,870
વેલ અમે શરૂઆતમાં શરૂ કરો.

16
00:00:43,870 --> 00:00:45,970
તે અમે શું કરશો તો
માટે છીએ, અમે બંધ કરી શકો છો.

17
00:00:45,970 --> 00:00:47,890
તે અમે 11 માટે નથી જોઈ રહ્યા છો નથી.

18
00:00:47,890 --> 00:00:50,220
તેથી નહિંતર, આગામી તત્વ ખસેડવા.

19
00:00:50,220 --> 00:00:51,510
>> તેથી અમે 23 જુઓ.

20
00:00:51,510 --> 00:00:52,730
અમે શોધી રહ્યાં છો તે 23 છે?

21
00:00:52,730 --> 00:00:55,614
કોઈ સારું, તેથી અમે આગામી પર ખસેડો
તત્વ છે, અને આગામી તત્વ,

22
00:00:55,614 --> 00:00:57,780
અને અમે મારફતે ચાલુ રાખવા
ઉપર અને ઉપર આ પ્રક્રિયા

23
00:00:57,780 --> 00:01:01,030
અને ઉપર સુધી અમે જમીન
આ જેમ એક પરિસ્થિતિ છે.

24
00:01:01,030 --> 00:01:03,910
>> નવ, અમે શોધી રહ્યાં છો તે છે
અને એરે આ તત્વ

25
00:01:03,910 --> 00:01:05,787
છે, તે કિંમત નવ છે.

26
00:01:05,787 --> 00:01:08,120
અને તેથી અમે શું કરી રહ્યાં છો મળી
માટે જોઈ છે, અને અમે બંધ કરી શકો છો.

27
00:01:08,120 --> 00:01:11,910
રેખીય શોધ છે
સફળતાપૂર્વક પૂર્ણ કરી હતી.

28
00:01:11,910 --> 00:01:15,370
>> પરંતુ અમે શું શોધી રહ્યાં છો, તો વિશે
અમારા એરે નથી કે એક તત્વ.

29
00:01:15,370 --> 00:01:17,040
રેખીય શોધ હજુ પણ કામ કરે છે?

30
00:01:17,040 --> 00:01:17,540
વેલ તેની ખાતરી કરો.

31
00:01:17,540 --> 00:01:19,947
તેથી અમે આ પ્રક્રિયા પુનરાવર્તન
પ્રથમ તત્વ શરૂ થાય છે.

32
00:01:19,947 --> 00:01:21,780
તે અમે શું કરશો તો
માટે છીએ, અમે બંધ કરી શકો છો.

33
00:01:21,780 --> 00:01:22,800
તે નથી.

34
00:01:22,800 --> 00:01:25,020
અન્યથા, અમે આગામી તત્વ ખસેડવા.

35
00:01:25,020 --> 00:01:29,050
>> પરંતુ અમે આ પ્રક્રિયા પુનરાવર્તન રાખવા કરી શકો છો
વારાફરતી દરેક તત્વ પરિક્ષણ,

36
00:01:29,050 --> 00:01:31,720
અમે નંબર 50 શોધવા કે આશા.

37
00:01:31,720 --> 00:01:33,750
પરંતુ અમે તો ખબર નહીં
અમે નંબર 50 મળી છે

38
00:01:33,750 --> 00:01:38,290
અમે કર્યું, અથવા, જો અમે ઊતર્યા કર્યું ત્યાં સુધી
એરે દરેક એક તત્વ નહીં.

39
00:01:38,290 --> 00:01:40,440
>> માત્ર અમે કર્યું છે
કે અને ટૂંકા આવે

40
00:01:40,440 --> 00:01:43,040
અમે તે પૂર્ણ કરી શકો છો
50 એરે નથી.

41
00:01:43,040 --> 00:01:46,410
અને તેથી રેખીય શોધ
અલ્ગોરિધમનો, તે નિષ્ફળ વેલ, સે દીઠ.

42
00:01:46,410 --> 00:01:49,181
પરંતુ તે અર્થમાં કે
કરવાથી નિષ્ફળ હતું શું

43
00:01:49,181 --> 00:01:49,930
અમે કરવા તે પૂછવામાં.

44
00:01:49,930 --> 00:01:52,390
>> તે નિષ્ફળ હતી
50 શોધી શક્યા ન હતા તેટલી,

45
00:01:52,390 --> 00:01:54,070
પરંતુ 50 એરે ન હતી.

46
00:01:54,070 --> 00:01:57,310
પરંતુ અમે exhaustively શોધ કરી
દરેક એક તત્વ મારફતે

47
00:01:57,310 --> 00:02:00,550
અને તેથી, જ્યારે અમે શોધી શક્યા ન હતા
કંઈપણ રેખીય શોધ હજુ

48
00:02:00,550 --> 00:02:05,230
સફળ થાય તો પણ આ
તત્વ એરે માં નથી.

49
00:02:05,230 --> 00:02:07,507
>> તેથી શું ખરાબ કેસ છે
રેખીય શોધ સાથે દૃશ્ય?

50
00:02:07,507 --> 00:02:09,590
વેલ અમે મારફતે જોવા માટે હોય છે
દરેક એક તત્વ,

51
00:02:09,590 --> 00:02:14,590
ક્યાં છે, કારણ લક્ષ્ય તત્વ
એરે છેલ્લા તત્વ છે,

52
00:02:14,590 --> 00:02:18,510
અથવા આપણે શોધી રહ્યાં છો તે તત્વ નથી
ખરેખર તમામ એરે અસ્તિત્વ ધરાવે છે.

53
00:02:18,510 --> 00:02:19,760
શ્રેષ્ઠ કેસ દૃશ્ય શું છે?

54
00:02:19,760 --> 00:02:22,430
વેલ અમે શોધી શકે છે
તરત જ તત્વ.

55
00:02:22,430 --> 00:02:24,360
અને કેટલા તત્વો
અમે પછી જોવા માટે હોય છે

56
00:02:24,360 --> 00:02:26,859
શ્રેષ્ઠ કિસ્સામાં પર,
અમે તે માટે શોધી રહ્યાં છો, તો

57
00:02:26,859 --> 00:02:28,400
અને અમે ખૂબ શરૂઆતમાં તેને શોધી?

58
00:02:28,400 --> 00:02:29,850
અમે તરત જ બંધ કરી શકો છો.

59
00:02:29,850 --> 00:02:32,984
>> આ વિશે શું કહે છે
રેખીય શોધ જટિલતા?

60
00:02:32,984 --> 00:02:35,650
વેલ, સૌથી ખરાબ કિસ્સામાં, અમે છે
દરેક એક તત્વ જોવા માટે.

61
00:02:35,650 --> 00:02:38,930
અને તેથી તે ઓ ચાલે
n એ, સૌથી ખરાબ કિસ્સામાં.

62
00:02:38,930 --> 00:02:41,540
>> શ્રેષ્ઠ કિસ્સામાં, અમે તેમ છો
તરત જ તત્વ શોધવા.

63
00:02:41,540 --> 00:02:44,750
અને તેથી 1 ઓમેગા ચાલે છે.

64
00:02:44,750 --> 00:02:45,780
>> હું ડો લોયડ છું.

65
00:02:45,780 --> 00:02:48,020
આ CS50 છે.

66
00:02:48,020 --> 00:02:49,876