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

2
00:00:05,760 --> 00:00:08,900
>> ڈوگ لایڈ تو 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
ہم بدترین کیس نے کہا کہ
اس کے وقت کو چلانے مربع ن تھا.

16
00:00:46,620 --> 00:00:50,060
اور آپ کو کیوں یاد کرنا چاہتے ہیں تو، لے
ایک انتخاب کی طرح ویڈیو دیکھو.

17
00:00:50,060 --> 00:00:54,560
بہترین کیس چلت وقت
بھی مربع ن ہے.

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
سلیکشن طرح ہے، اب تک،
smallest-- بلبلا مل

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
بدترین کیس چلت وقت
بلبلا کی ترتیب کا مربع ن ہے.

26
00:01:20,180 --> 00:01:23,476
بہترین کیس چلت وقت
بلبلا کی طرح (ن) ہے.

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
ہم صرف ایک بنانے کے لئے ہے
تمام این عناصر بھر منتقل.

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
کے سب سے زیادہ کیس چلت وقت
اندراج کی طرح مربع ن ہے.

39
00:01:58,650 --> 00:02:02,380
بہترین کیس وقت کو چلانے کے (ن) ہے.

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 elements-- ہم اس تقسیم
نیچے نصف کی طرف سے، نصف کی طرف سے، نصف کی طرف سے،

43
00:02:13,790 --> 00:02:17,720
ہم صف کے تحت ہے جب تک
(ن) ایک عنصر arrays کے.

44
00:02:17,720 --> 00:02:19,470
(ن) ایک عنصر arrays کے ایک سیٹ.

45
00:02:19,470 --> 00:02:22,640
تو ہم نے ایک کے ساتھ شروع
1،000 عنصر سرنی،

46
00:02:22,640 --> 00:02:26,550
اور ہم نقطہ پر حاصل ہم کہاں
1،000 ایک عنصر arrays ہے.

47
00:02:26,550 --> 00:02:30,990
تب ہم نے ان ذیلی arrays کے ضم کرنے کے لئے شروع
واپس مل صحیح ترتیب میں.

48
00:02:30,990 --> 00:02:34,860
تو ہم دو ایک عنصر arrays کے لے
اور ایک دو عنصر صف بنانے کے.

49
00:02:34,860 --> 00:02:38,180
ہم نے دو دو عنصر arrays کے لے
اور ایک چار عنصر صف بنانے کے

50
00:02:38,180 --> 00:02:43,900
اور اسی طرح اور اسی طرح ہم نے یہاں تک کہ
پھر سے ایک (ن) عنصر سرنی دوبارہ تعمیر.

51
00:02:43,900 --> 00:02:48,410
>> کے سب سے زیادہ کیس چلت وقت
قسم ہے ضم ن کے اوقات ن لاگ ان کریں.

52
00:02:48,410 --> 00:02:52,390
ہم (ن) کے عناصر ہیں، لیکن
اس recombining عمل

53
00:02:52,390 --> 00:02:56,960
لاگ ان ن اقدامات حاصل کرنے کے لئے
ایک مکمل سرنی کرنے کے لئے واپس.

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
تو (ن) بدترین صورت میں لاگ ان ن،
(ن) بہترین صورت میں لاگ ان ن.

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
بدترین کیس چلانے کے وقت بڑا این اے ہے.

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
کافی ہے جس میں، لاگ ان ن
لکیری تلاش کی (ن) سے بہتر.

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