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
سامان کی رقم، RAM، تمام اس قسم ہے.

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
تو ایک الگورتھم کے لئے کہا جا سکتا ہے
مربع ن یا اے اے میں چلانے کے.

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
ہم ایک الگورتھم کے بارے میں بات کر رہے ہیں
کہ، زیادہ عام طور پر arrays کے ہینڈل

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
اور ہم نے اس کال کر سکتے ہیں
(ن) کے F، منمانے، پیمائش.

80
00:03:56,200 --> 00:03:59,420
جہاں (ن) کی تعداد ہے
ڈیٹا سیٹ میں عناصر.

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
>> اب، ہم واقعی پرواہ نہیں کرتے
بالکل (ن) کے F کیا ہے کے بارے.

84
00:04:10,030 --> 00:04:13,700
اصل میں، ہم بہت کم will--
یقینی طور پر کبھی اس class-- میں

85
00:04:13,700 --> 00:04:18,709
کوئی واقعی گہری میں کودو
چ ن ہے کا تجزیہ.

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
جن میں سے پہلے ن لیتا ہے
وسائل کی cubed کی، کچھ یونٹس

92
00:04:39,350 --> 00:04:42,880
سائز (ن) کے ایک ڈیٹا مذکور کارروائی کے.

93
00:04:42,880 --> 00:04:47,000
ہم سے لیتا ہے کہ ایک دوسرے الگورتھم ہے
cubed کی علاوہ مربع ن وسائل N

94
00:04:47,000 --> 00:04:49,350
سائز (ن) کے ایک ڈیٹا مذکور کارروائی کے.

95
00:04:49,350 --> 00:04:52,030
اور ہم نے ایک تہائی ہے
کہ in-- چلتا ہے کہ الگورتھم

96
00:04:52,030 --> 00:04:58,300
لیتا ن cubed مائنس 8N مربع
وسائل کے علاوہ 20 N یونٹس

97
00:04:58,300 --> 00:05:02,370
ایک الگورتھم پر عملدرآمد کرنے میں
سائز (ن) کے مقرر کی معلومات کے ساتھ.

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
وہ سب لے جاتے ہیں
تقریبا ن cubed،

136
00:06:50,006 --> 00:06:52,380
اور تو ہم اصل سے رجوع کریں گے
ان یلگوردمز کی سب کے لئے

137
00:06:52,380 --> 00:06:59,520
(ن) کے حکم پر کیا جا رہا ہے کے طور پر
cubed کی یا ن cubed کی بڑی اے.

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، رنز
سے چکوری ہیں وقت مربع ن.

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،000th اقتدار میں سی لے جائے گا.

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
تو ہم ایک مثال ہے
یا دو مثالیں یہاں

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
صرف دو integers پر عملدرآمد.

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
آپ کو ایک حاصل، آپ B حاصل، آپ کو ان میں شامل کریں
ایک دوسرے کے ساتھ، اور آپ کی پیداوار کے نتائج.

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
ہم اب بھی پر نظر پڑے
(ن) کے عناصر کے تمام.

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
اور ہم چلتا ہے کہ ایک اندرونی لوپ ہے
صفر سے P کرنے کے لئے، اور اس کے اندر،

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
آپ 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