1 00:00:00,000 --> 00:00:05,760 2 00:00:05,760 --> 00:00:08,900 >> DOUG لويد: حتى في 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 والأسوأ الوقت حالة تشغيل فقاعة نوع n غير المربعة. 26 00:01:20,180 --> 00:01:23,476 وقت التشغيل أفضل الحالات فقاعة النوع هو ن. 27 00:01:23,476 --> 00:01:25,350 لأنه في هذه الحالة نحن لا actually-- 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 10000 elements-- نحن تقسيمه بمقدار النصف، بمقدار النصف، بمقدار النصف، 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 لذلك بدأنا مع واحد مجموعة 1000 عنصر، 46 00:02:22,640 --> 00:02:26,550 ونصل إلى النقطة التي وصلنا لدينا 1000 صفائف عنصر واحد. 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 وهلم جرا وهكذا دواليك حتى قمنا أعيد بناؤها مرة أخرى واحدة مجموعة العنصر n. 51 00:02:43,900 --> 00:02:48,410 >> وقت التشغيل أسوأ حالة دمج النوع غير مرة n السجل ن. 52 00:02:48,410 --> 00:02:52,390 لدينا عناصر ن، ولكن هذه العملية إعادة توحيد 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 لذلك البحث الخطي نحو بالتكرار. 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 قد يستغرق لنا بالتكرار عبر كل عنصر واحد 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 انها شرط أساسي لاستخدام it-- مجموعة التي كنت أبحث من خلال 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 قد جعلها أقل فعالية اعتمادا على حجم بالتكرار فرزها. 86 00:04:32,010 --> 00:04:35,250 >> أنا دوغ ويد، وهذا هو CS50. 87 00:04:35,250 --> 00:04:36,757