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 عندما نتحدث عن تعقيد وalgorithm-- التي في بعض الأحيان عليك 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 نسميه عادة الأسوأ وقت التشغيل خوارزمية كبير-O. 38 00:01:51,450 --> 00:01:56,770 لذلك يمكن القول خوارزمية ل تشغيل في O ن أو O ن المربعة. 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 نشير إلى أنه في بعض الأحيان كبير أوميغا، وذلك في تناقض مع كبير-O، 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 كبير-O لسيناريو أسوأ الحالات. 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 >> الآن، يمكننا قياس ل algorithm-- على وجه الخصوص، 74 00:03:39,272 --> 00:03:40,980 عندما أقول ما في وسعنا قياس خوارزمية، I 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 وو ن هو عدد سمثينغس. 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 في الواقع، نحن نادرا جدا will-- بالتأكيد سوف أبدا في هذا I class-- 85 00:04:13,700 --> 00:04:18,709 الغوص في أي عمق حقا تحليل ما و ن هو. 86 00:04:18,709 --> 00:04:23,510 نحن ذاهبون لمجرد الحديث عن ما و ل ن تقريبا أو ما يميل إليه. 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 أولها يأخذ ن مكعبة، وبعض وحدات الموارد 92 00:04:39,350 --> 00:04:42,880 لمعالجة مجموعة من البيانات من حجم ن. 93 00:04:42,880 --> 00:04:47,000 لدينا خوارزمية الثانية التي تأخذ ن مكعبة بالإضافة إلى الموارد ن التربيعية 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 يستغرق فترة تصل ن ناقص مكعبة 8N تربيع بالإضافة إلى 20 ن وحدات الموارد 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 يأخذ 1000 وحدة من الموارد لمعالجة مجموعة من البيانات من حجم 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 إذا مجموعة البيانات من حجم 1000 والخوارزمية الأولى 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 كما يجري بناء على أمر من ن مكعبة أو كبيرة O-ن مكعبة. 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 يعمل في ن سجل ن، الذي لا يزال أفضل من الدرجة الثانية time-- ن تربيع. 164 00:08:13,370 --> 00:08:17,320 أو وقت متعدد الحدود، ن اثنين أي عدد أكبر من اثنين. 165 00:08:17,320 --> 00:08:20,810 أو الوقت المتسارع، الذي هو حتى worse-- C إلى ن. 166 00:08:20,810 --> 00:08:24,670 لذلك أثار بعض رقم ثابت ل قوة حجم المدخلات. 167 00:08:24,670 --> 00:08:28,990 حتى إذا كان هناك 1،000-- إذا كان إدخال البيانات من حجم 1000، 168 00:08:28,990 --> 00:08:31,310 ان الامر سيستغرق C إلى قوة 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 لذلك لدينا example-- أو مثالين here-- 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 بالنسبة لك، والتي يأخذ مجموعة من حجم 1000. 189 00:09:23,952 --> 00:09:25,660 ولكن بعد ذلك على ما يبدو لا تبدو في الواقع 190 00:09:25,660 --> 00:09:29,000 في it-- لا يهتم حقا ما هو داخل منه، من أن مجموعة. 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 يأخذ 1000 عناصر لا فعل أي شيء معهم. 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 لكنها دائما ثابتة، بغض النظر عن أو ب. 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 >> وهنا مثال على خطي algorithm-- الوقت 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 يمكنك التأكد من ذلك عن طريق استقراء قليلا قائلا: 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 هنا أن يدير من ي يساوي 0، وصولا إلى m. 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 هل تخمين كبير O-من م؟ 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 لدينا حلقة الخارجي تنطلق من صفر إلى ص. 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 حسنا، مرة أخرى، لدينا الحلقة الخارجي الذي يمتد الأوقات ص. 248 00:12:06,140 --> 00:12:09,660 وكل التكرار time-- تلك الحلقة، إلى حد ما. 249 00:12:09,660 --> 00:12:13,170 لدينا حلقة داخلية الذي يعمل أيضا أوقات ص. 250 00:12:13,170 --> 00:12:16,900 ثم داخل ذلك، هناك ل ثابت قصاصة صغيرة time-- هناك. 251 00:12:16,900 --> 00:12:19,890 >> حتى إذا كان لدينا حلقة الخارجي الذي يدير الأوقات ص الداخل والتي هي 252 00:12:19,890 --> 00:12:22,880 حلقة الداخلية التي يدير ص times-- ما هو 253 00:12:22,880 --> 00:12:26,480 أسوأ الحالات وقت هذا مقتطف من التعليمات البرمجية؟ 254 00:12:26,480 --> 00:12:30,730 هل تخمين كبير O-من ص التربيعية؟ 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