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
>> ಕೀವರ್ಡ್ sort-- ವಿಲೀನಗೊಳಿಸಿ
ಇಲ್ಲಿ ಬೇರ್ಪಟ್ಟು ವಿಲೀನಗೊಳ್ಳಲು ಇದೆ.

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
ನಾವು ರಚನೆಯ ಅಡಿಯಲ್ಲಿ ತನಕ
ಎನ್ ಒಂದು ಅಂಶ ಆಯ್ರೆಗಳ.

44
00:02:17,720 --> 00:02:19,470
ಎನ್ ಒಂದು ಅಂಶ ಆಯ್ರೆಗಳ ಸೆಟ್.

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
ಹೀಗೆ ಹೀಗೆ ನಾವು ಮಾಡಿದ ರವರೆಗೆ
ಮತ್ತೆ ಒಂದು ಎನ್ ಅಂಶ ರಚನೆಯ ಮರುನಿರ್ಮಿಸಲಾಯಿತು.

51
00:02:43,900 --> 00:02:48,410
>> ಕೆಟ್ಟ ಸಂದರ್ಭದಲ್ಲಿ ರನ್ ಸಮಯ
ವಿಲೀನ ರೀತಿಯ 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
ಸಮಯ ಔಟ್ ಅತ್ಯುತ್ತಮ ಪ್ರಕರಣವು ಸೂಚನೆ ಪ್ರವೇಶಿಸಲು
ಎನ್ ಈ ಪ್ರಕ್ರಿಯೆ ನಿಜವಾಗಿಯೂ ಏಕೆಂದರೆ

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 ಲಾಗ್.

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 ನ ದೊಡ್ಡ ಒ ಆಗಿದೆ.

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
ರೇಖೀಯ ಹುಡುಕಾಟ ಗಣನೀಯವಾಗಿ ಉತ್ತಮ
ಲಾಗ್ ಎಂಬ ಕಾರಣದಿಂದ ಎನ್ ವಿರುದ್ಧ,

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