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
একটি সতর্কতা শুধুমাত্র একটি বিট
আমরাও 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
স্টাফ টাকা, র্যাম, যে সব ধরনের হয়.

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
খারাপ কেস দৃশ্যকল্প জন্য বিগ-হে.

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
যে তথ্য আছে set--
আকার, সংখ্যা

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
আর আমরা এই কল করতে পারেন
এন এফ, ইচ্ছামত, পরিমাপ.

80
00:03:56,200 --> 00:03:59,420
যেখানে n সংখ্যা
তথ্য সেটে উপাদানের.

81
00:03:59,420 --> 00:04:02,640
আর এন এর F কতগুলি কিছুটা হয়.

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
আসলে, আমরা খুব কমই ইচ্ছার
অবশ্যই মৃত্যু কামনা করবে না এই বর্গ আমি

85
00:04:13,700 --> 00:04:18,709
কোনো সত্যিই গভীর জলে ডুব
চ এন কি বিশ্লেষণ.

86
00:04:18,709 --> 00:04:23,510
আমরা শুধু কি F সম্পর্কে কথা বলতে যাচ্ছেন
এন আনুমানিক বা কি তা থাকে হয়.

87
00:04:23,510 --> 00:04:27,600
একটি আলগোরিদিম প্রবণতা
তার সর্বোচ্চ শব্দটি দ্বারা dictated.

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
যা প্রথম এন লাগে
সম্পদের ঘনাংকিত, কিছু ইউনিট

92
00:04:39,350 --> 00:04:42,880
আকার n একটি তথ্য সংকলন প্রক্রিয়া.

93
00:04:42,880 --> 00:04:47,000
আমরা যে সময় লাগে একটি দ্বিতীয় আলগোরিদিম আছে
ঘনাংকিত প্লাস 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 বিয়োগ 8n ছক
সম্পদ প্লাস 20 এন ইউনিট

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
একটি তথ্য সংকলন আকারের হয় তাহলে
1,000 এবং প্রথম অ্যালগরিদম

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
আর শুধু সত্যিই
হোম হাতুড়ি point--

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,

136
00:06:50,006 --> 00:06:52,380
এবং তাই আমরা আসলে পড়ুন হবে
এই আলগোরিদিম সমস্ত যাও

137
00:06:52,380 --> 00:06:59,520
এন অনুক্রম হচ্ছে
ঘনাংকিত বা n ঘনাংকিত বড়-হে.

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
আসলে, প্রত্যেক সময় আপনি দ্বিগুণ
এন, এটি শুধুমাত্র একটি পদক্ষেপ নেয়.

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
আপনি কখনও কখনও, রৈখিক নাচুনে সময় আছে
পাসওয়ার্ড ভুলে গেছেন? রৈখিক সময় বলা অথবা এন এন লগ ইন করুন.

162
00:08:06,622 --> 00:08:08,330
এবং আমরা একটি উদাহরণ হবে
একটি অ্যালগরিদম যে

163
00:08:08,330 --> 00:08:13,370
এখনও ভালো, যা n log 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
এটা 1000 তম ক্ষমতায় সি নিতে হবে.

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
যার যেমন তথাকথিত, হিসাবে মূঢ় sort--
পেশা এলোমেলোভাবে একটি অ্যারের পরিহার হয়

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
সুতরাং আমরা একটি example-- আছে
বা দুটি উদাহরণ এখানে

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
প্রথম example-- তাই
আমরা একটি ফাংশন আছে

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
কিন্তু এটা সবসময় ধ্রুবক
নির্বিশেষে 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
আপনি মিটার বড়-হে অনুমান করেছেন?

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
আমরা একটি বাইরের লুপ আছে
যে শূন্য থেকে P চালায়.

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
ওয়েল, আবার, আমরা একটি আছে
P বার সঞ্চালিত হয় যে বাইরের লুপ.

248
00:12:06,140 --> 00:12:09,660
আর প্রতিটি সময়ের মধ্যে পুনরাবৃত্তির
যে লুপ, বরং.

249
00:12:09,660 --> 00:12:13,170
আমরা একটি অভ্যন্তরীণ লুপ আছে
যে P বার রান.

250
00:12:13,170 --> 00:12:16,900
যে এর ভিতরে এবং তারপর, আছে
সেখানে ধ্রুব সময়ের মধ্যে সামান্য স্নিপেট.

251
00:12:16,900 --> 00:12:19,890
>> আমরা একটি বাইরের লুপ আছে সুতরাং যে
যার ভিতর P বার রান

252
00:12:19,890 --> 00:12:22,880
একটি অভ্যন্তরীণ লুপ যে
কি বার পুনরাবৃত্তি P রান

253
00:12:22,880 --> 00:12:26,480
খারাপ-ক্ষেত্রে রানটাইম
এই কোড স্নিপেট?

254
00:12:26,480 --> 00:12:30,730
আপনি পি বড়-বর্গ হে অনুমান করেছেন?

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