[Powered by Google Translate] [القسم 3 - أكثر راحة]
[روب بودين - جامعة هارفارد]
>> [هذا CS50. - CS50.TV]
>> بحيث يتم صياغتها بشكل غريب على السؤال الأول.
GDB يتيح لك "تصحيح" برنامج، ولكن، وبشكل أكثر تحديدا، ماذا لك أن تفعل؟
أنا سأجيب أن واحد، وأنا لا أعرف بالضبط ما هو متوقع،
لذلك أنا التخمين انها شيء على غرار فإنه يتيح لك خطوة خطوة
المشي من خلال برنامج والتفاعل معها، والمتغيرات التغيير، تفعل كل هذه الأشياء -
في الأساس السيطرة تماما تنفيذ برنامج
وتفقد أي جزء معين من تنفيذ البرنامج.
حتى تلك الميزات تسمح لك تصحيح الأمور.
حسنا.
لماذا البحث الثنائية تتطلب أن يتم فرز مجموعة؟
الذي يريد أن تجيب على ذلك؟
[طالب] لأنه لا يعمل إذا لم يكن تم الفرز عليه. نعم >>. [ضحك]
وإذا ما غير مصنفة ذلك، ثم أنه من المستحيل أن تقسيمه إلى نصفين
ويعرف أن كل شيء على يسار أقل وكل شيء إلى اليمين
أكبر من القيمة الوسطى.
لذلك لا بد من فرزها.
حسنا.
لماذا هو نوع من فقاعة في O ن التربيعية؟
لا أحد أريد أولا لإعطاء سريعة جدا على مستوى عال محة عامة عن ما هو نوع فقاعة؟
[طالب] تذهب أساسا من خلال كل عنصر من عناصر وعليك مراجعة العناصر القليلة الأولى.
لو انهم من المكان الذي مقايضتهم، ثم قمت بفحص العناصر القليلة المقبلة، وهلم جرا.
عندما تصل إلى نهاية، ثم انت تعرف ان يتم وضع أكبر عنصر في النهاية،
لذلك أنت تتجاهل أن واحدا ثم عليك أن تبقي على الذهاب من خلال،
وفي كل مرة كان لديك للتحقق من عنصر واحد أقل حتى قمت بإجراء أية تغييرات. نعم >>.
انه دعا نوع فقاعة لأنه إذا كنت الوجه الصفيف على جانبها لذلك فمن صعودا وهبوطا، العمودي،
ثم سوف القيم الكبيرة تنزل الى القاع والقيم الصغيرة سوف فقاعة يصل إلى الأعلى.
تلك هي الكيفية التي حصلت على اسمها.
ونعم، كنت مجرد الذهاب من خلال.
واصلتم يمر الصفيف، مبادلة قيمة أكبر
للحصول على أكبر القيم إلى أسفل.
>> لماذا هو O ن التربيعية؟
أولا، لا أحد يريد أن يقول لماذا هو O ن التربيعية؟
[طالب] لأن لكل تشغيله مرة يذهب ن.
فقط يمكنك أن تكون على يقين من أن كنت قد اتخذت أكبر عنصر على طول الطريق،
ثم لديك لتكرار ذلك لأنه كما العديد من العناصر. نعم >>.
حتى تبقي في الاعتبار ما يعني وكبيرة O ما الوسائل أوميغا كبيرة.
وO كبيرة مثل الحد الأعلى حول كيفية بطيئة يمكن تشغيلها فعليا.
ذلك بالقول انها O ن التربيعية، فإنه ليس من غير O وإلا فإنه سيكون قادرا على تشغيل
في الوقت الخطية، وإنما هو من مكعبة O ن
لأن يحدها من مكعبة O ن.
وإذا ما يحدها O ن التربيعية، ثم انها يحدها أيضا مكعبة ن.
ذلك أنه هو ن مربع، وفي حال الأسوأ علي الاطلاق تكنولوجيا المعلومات لا تستطيع أن تفعل أفضل من N مربع،
وهذا هو السبب انها O ن المربعة.
ذلك أن نرى الرياضيات طفيف في كيفية يتعلق الأمر إلى أن تكون ن مربع،
اذا كان لدينا خمسة أشياء في قائمتنا، وهي المرة الأولى كيف يمكن مقايضة العديد نحن بحاجة لجعل يحتمل
من أجل الحصول على هذا؟ دعونا فقط في الواقع -
عدد التبادل نحن ذاهبون الى ان تجعل في الجولة الأولى من نوع فقاعة من خلال مجموعة؟
[طالب] ن - 1. نعم >>.
>> إذا كان هناك 5 عناصر، ونحن بحاجة الى الذهاب الى جعل ن - 1.
ثم في ثانية واحدة كم عدد التبادل نحن ذاهبون الى ان تجعل؟
[طالب] ن - 2. نعم >>.
والثالثة ستكون N - 3، ومن ثم لراحة سأكتب الماضيين
كما ثم نحن بحاجة الى الذهاب الى جعل 2 التبادل والمقايضة 1.
أعتقد أن آخر قد أو قد لا تحتاج في الواقع أن يحدث.
هل هو مبادلة؟ لا أعرف.
لذلك فان هذه هي إجمالي مبالغ عمليات مقايضة أو على الأقل مقارنات لديك لجعل.
حتى لو كنت لا تبديل، لا تزال تحتاج لمقارنة القيم.
لذلك هناك ن - 1 مقارنات في الجولة الأولى من خلال مجموعة.
إذا كنت إعادة ترتيب هذه الأمور، دعونا نجعل فعلا ستة أشياء من الأشياء كومة طيف،
ومن ثم سأفعل 3، 2، 1.
حتى إعادة ترتيب هذه المبالغ فقط، نريد أن نرى كيف العديد من المقارنات التي نتخذها
في الخوارزمية بأكمله.
إذا كان الأمر كذلك نأتي إلى هنا هؤلاء الرجال،
ثم نحن لا تزال مجرد تلخيص مقارنات كثيرة ولكن كانت هناك.
ولكن إذا كنا تلخيص هذه الخلاصة هذه، ونحن ونحن جمع هذه،
انها لا تزال نفس المشكلة. خلاصة القول أننا فقط تلك الجماعات خاصة.
>> لذلك نحن الآن تلخيص 3 في ن. انها ليست مجرد 3 N في.
انها دائما ما يكون ن / 2 ن ل.
لذلك نحن هنا يحدث لدينا 6.
إذا كان لدينا 10 أشياء، ثم يمكن أن نفعل هذا التجمع لمدة 5 أزواج مختلفة من الأشياء
وينتهي مع ن ن + + + ن + ن ن.
لذلك كنت دائما ما تحصل ن / 2 ن، وحتى هذا سنقوم بها الذرة إلى n مربع / 2.
وذلك على الرغم من انها عامل النصف، والذي يحدث أن تأتي في
بسبب حقيقة أنه من خلال كل تكرار خلال مجموعة قارنا 1 أقل
هذا كيف نحصل على أكثر من 2، ولكن لا يزال هو ن مربع.
نحن لا نهتم عاملا ثابتا من النصف.
لذلك الكثير من الاشياء الكبيرة مثل O هذا يعتمد على مجرد نوع من يفعل هذا النوع من الرياضيات،
القيام مبالغ الحساب وهندسية الاشياء السلسلة،
ولكن معظمها في هذه الدورة هي جميلة واضحة.
حسنا.
لماذا هو نوع أوميغا الإدراج في ن؟ ماذا يعني أوميغا؟
[طالبين التحدث في آن واحد - غير مفهومة] نعم >>.
يمكن أوميغا تفكر في مثل الحد الأدنى.
>> ذلك بغض النظر عن مدى كفاءة خوارزمية الترتيب الخاص بك الإدراج،
بغض النظر عن القائمة التي مرت في، فإنه دائما لمقارنة الأشياء على الأقل ن
أو أنه لا يوجد تكرار عبر الأشياء.
لماذا؟
[طالب] لأنه إذا تم فرزها بالفعل في القائمة، ثم من خلال التكرار الأول
يمكنك فقط أن تضمن العنصر الأول هو الأقل جدا،
والتكرار الثاني يمكنك ضمان فقط الأولين هي
لأنك لا تعلم أن يتم فرز باقي القائمة. نعم >>.
إذا كنت تمر في القائمة التي تم فرزها تماما، على الأقل عليك أن تذهب على جميع العناصر
أن نرى أن لا شيء يجب أن يتم نقل حولها.
يمر ذلك عبر قائمة ويقول أوه، يتم فرز هذا بالفعل،
انه من المستحيل بالنسبة لك أن تعرف فإنه يتم فرز حتى تحقق كل عنصر من عناصر
للتأكد من أنهم في ترتيب فرزها.
وبالتالي فإن الحد الأدنى على نوع أوميغا الإدراج ن.
ما هو أسوأ حالة تشغيل وقت نوع الدمج،
أسوأ الحالات يجري O كبيرة مرة أخرى؟
حتى في أسوأ الحالات، كيف يمكن دمج النوع تشغيل؟
[طالب] N ن سجل. نعم >>.
أسرع خوارزميات الفرز العامة .. ن ن سجل. لا يمكنك أن تفعل أفضل.
>> هناك حالات خاصة، واذا كان لدينا وقت اليوم - ولكننا مقتبل ربما -
يمكننا أن نرى واحد أن يفعل أفضل من ن ن سجل.
ولكن في حالة عامة، لا يمكنك أن تفعل أفضل من ن ن سجل.
ودمج النوع يحدث لتكون واحدة يجب أن نعرف أن لهذه الدورة هو ن ن سجل.
ولذا فإننا سوف يتم تنفيذ ذلك في الواقع اليوم.
وأخيرا، في ما لا يزيد عن ثلاث جمل، كيف اختيار نوع العمل؟
لا شخص الرغبة في الرد، وسوف نعول جملك
لأنه إذا ذهبت أكثر من 3 -
لا أحد يتذكر نوع الاختيار؟
نوع الاختيار عادة ما يكون من السهل جدا أن نتذكر فقط من الاسم.
كنت تكرار ما يزيد قليلا على مجموعة، والعثور على كل ما هو أكبر قيمة أو أصغر -
مهما كنت أمر الفرز فيها.
لذلك دعونا نقول اننا الفرز من الأصغر إلى الأكبر.
كنت تكرار عبر مجموعة، وتبحث عن كل ما هو العنصر الحد الأدنى،
تحديده، ومن ثم مبادلة فقط كل ما هو في المقام الأول.
ومن ثم على مرور الثاني على مجموعة، والبحث عن العنصر الحد الأدنى مرة أخرى،
تحديده، ثم مبادلتها مع ما هو في المرتبة الثانية.
لذلك نحن فقط في اختيار واختيار القيم الدنيا
وإدراجها في الجزء الأمامي من مجموعة حتى يتم فرز ذلك.
الأسئلة على ذلك؟
>> هذه تظهر حتما في أشكال لديك لملء عندما كنت تقديم pset.
تلك هي أساسا إجابات لتلك.
حسنا، لذلك الترميز الآن مشاكل.
أنا أرسلت بالفعل عبر البريد الإلكتروني - هل أي شخص لا تحصل على هذا البريد الإلكتروني؟ حسنا.
أنا أرسلت بالفعل عبر البريد الإلكتروني المساحة التي نحن ذاهبون إلى استخدام،
وإذا نقرت على اسمي - لذلك أعتقد أنني ذاهب ليكون في أسفل
بسبب R الوراء - ولكن إذا نقرت على اسمي سوف انظر 2 التنقيحات.
التنقيح 1 سوف يتم نسخها بالفعل أنا ولصق الشفرة في الفراغات
البحث عن الشيء وأنت تسير لدينا لتنفيذها.
وسوف التنقيح 2 أن يكون الشيء النوع الذي ننفذ بعد ذلك.
لذلك يمكنك النقر على مراجعة بلدي (1) والعمل من هناك.
والآن نريد أن تنفيذ بحث ثنائية.
>> لا أحد يريد ان يعطي مجرد شبة الكود رفيع المستوى التفسير
ما نحن ذاهبون الى القيام به للبحث؟ نعم.
[طالب] أنت تأخذ فقط وسط مجموعة ومعرفة ما اذا ما كنت تبحث عن
هو أقل من ذلك أو أكثر من ذلك.
وإذا كان أقل من ذلك، تذهب إلى النصف وهذا أقل،
وإذا كان أكثر من ذلك، تذهب إلى النصف وهذا أكثر ولكم أن أكرر حتى تحصل على شيء واحد فقط.
[بودين] نعم.
تلاحظ أن يتم فرز الأرقام لدينا بالفعل مجموعة،
وبحيث يعني أننا يمكن أن نستفيد من ذلك وأننا يمكن أن تحقق الأولى،
حسنا، أنا أبحث عن عدد 50.
حتى أتمكن من الذهاب الى وسطها.
الأوسط من الصعب تحديد عندما يكون عدد زوجي من الأشياء،
ولكن دعنا نقول فقط أننا سوف اقتطاع دائما إلى الوسط.
حتى هنا لدينا 8 الأشياء، لذلك سيكون منتصف 16.
أنا أبحث عن 50، حتى 50 هو أكبر من 16.
حتى الآن لا أستطيع علاج أساسا مجموعة بصفتي هذه العناصر.
ويمكنني أن نرمي كل شيء من أكثر من 16.
الآن مجموعة بلدي هو مجرد هذه العناصر 4، وأكرر.
حتى ذلك الحين أريد أن أجد منتصف مرة أخرى، والتي ستكون 42.
42 هو أقل من 50، حتى أتمكن من رمي بعيدا هذين العنصرين.
هذا هو بلدي مجموعة المتبقية.
انا ذاهب الى العثور على منتصف مرة أخرى.
اعتقد 50 تم مثالا سيئا لأنني كنت دائما رمي الأشياء بعيدا إلى اليسار،
ولكن عن طريق هذا الإجراء نفسه، إذا أنا أبحث عن شيء
وانها أقل من العنصر أنا أبحث حاليا في،
ثم أنا ذاهب لرمي بعيدا كل شيء إلى اليمين.
حتى الآن نحن بحاجة لتنفيذ ذلك.
لاحظت أننا في حاجة لتمرير في الحجم.
يمكننا أيضا لا تحتاج إلى رمز يصعب الحجم.
إذا كان الأمر كذلك نتخلص من أن تعريف # -
حسنا.
كيف يمكنني معرفة ما لطيف حجم مجموعة الأعداد حاليا؟
>> كم عدد العناصر في الصفيف الأرقام؟
[طالب] أرقام، بين قوسين،. طول؟
[بودين] وهذا غير موجود في C.
تحتاج إليها. طول.
صفائف لم يكن لديك الخصائص، لذلك ليس هناك خاصية طول صفائف
والتي تعطي فقط لأنك مهما طال يحدث أن تكون.
[طالب] انظر مقدار الذاكرة لديه والقسمة على مدى - نعم >>.
فكيف نرى مقدار الذاكرة لديها؟ >> [طالب] Sizeof. نعم >>، sizeof.
Sizeof هي المشغل أن يحدث لإرجاع حجم الصفيف الأرقام.
والتي ستكون صحيحة ولكن هناك العديد من أضعاف حجم عدد صحيح
منذ ذلك مقدار الذاكرة يستغرق وقتا فعليا حتى.
إذا كان الأمر كذلك أريد عدد من الأشياء في الصفيف،
ثم أنا تريد الذهاب الى تقسيم حسب حجم عدد صحيح.
حسنا. بحيث يتيح لي تمر في الحجم هنا.
لماذا أحتاج لتمرير في حجم على الإطلاق؟
لماذا لا يمكن أن أفعل للتو هنا حجم كثافة العمليات = sizeof (كومة قش) / sizeof (الباحث)؟
لماذا لا تعمل هذه؟
[طالب] انها ليست متغير عمومي.
كومة التبن [بودين] موجود ونحن تمرير في الأرقام كما كومة قش،
وهذا هو نوع من ينذر من ما يأتي. نعم.
[طالب] كومة التبن هو مجرد الإشارة إلى ذلك، لذلك فإنه يعود كيف الكبيرة التي المرجع.
نعم.
أشك في أن محاضرة كنت قد رأيت كومة حتى الآن حقا، أليس كذلك؟
تحدثنا فقط عن ذلك.
ذلك هو المكان المكدس جميع المتغيرات الخاصة بك سوف تكون مخزنة.
>> أي الذاكرة التي خصصت لانها المتغيرات المحلية تسير في المكدس،
ويحصل كل وظيفة الفضاء الخاصة بها على المكدس، إطاره كومة الخاصة هو ما يطلق عليه.
الرئيسية بحيث يحتوي إطاره المكدس، وداخل منه هو الذهاب الى وجود أعداد هذه المجموعة،
وسيكون من sizeof حجم (أرقام).
انها ستكون لدينا حجم الأرقام مقسوما على حجم العناصر،
ولكن أن كل حياة داخل إطار مكدس الرئيسي.
عندما ندعو البحث، البحث إطاره يحصل كومة الخاصة،
الفضاء الخاصة بها لتخزين كافة المتغيرات المحلية الخاصة به.
ولكن هذه الحجج - حتى كومة قش ليست نسخة من هذه المجموعة بأكملها.
نحن لا تمر في مجموعة كاملة كنسخة في البحث.
يمر مجرد الإشارة إلى أن مجموعة.
لذلك يمكن الوصول إلى هذه الأرقام البحث من خلال هذا المرجع.
انها لا تزال الحصول على الأشياء التي تعيش داخل الإطار الرئيسي لمكدس،
ولكن في الأساس، عندما نصل إلى المؤشرات، التي ينبغي أن تكون في وقت قريب،
هذا هو ما هي المؤشرات.
مؤشرات ليست سوى إشارات إلى الأشياء، ويمكنك استخدام المؤشرات للوصول إلى الأشياء
التي هي في إطارات المكدس أمور أخرى ".
ذلك على الرغم من الأرقام المحلي إلى الرئيسية، يمكننا الوصول إلى أنها لا تزال من خلال هذا المؤشر.
ولكن منذ انها مجرد مؤشر وانها مجرد إشارة،
sizeof (كومة قش) بإرجاع فقط من الحجم الإشارة نفسها.
فإنه لا يرجع حجم الشيء انها تشير الى.
فإنه لا يرجع الحجم الفعلي من الأرقام.
وحتى هذه ليست الذهاب الى العمل لأننا نريد أن.
>> الأسئلة على ذلك؟
ستزول مؤشرات إلى حد كبير بالتفصيل أكثر دموية في الأسابيع المقبلة.
وهذا هو السبب في الكثير من الأشياء التي تراها، أكثر الأشياء أو الأشياء نوع البحث،
انهم جميعا تقريبا بحاجة الى الذهاب الى اتخاذ الحجم الفعلي للمجموعة،
لأنه في C، ليس لدينا أي فكرة عما حجم الصفيف.
تحتاج إلى تمرير يدويا فيه.
وأنت لا تستطيع تمرير يدويا في مجموعة كاملة لأنك مجرد مرور في المرجع
وأنه لا يمكن الحصول على حجم من المرجع.
حسنا.
حتى الآن نحن نريد لتنفيذ ما تم شرح من قبل.
يمكنك العمل على ذلك لمدة دقيقة،
وكنت لا داعي للقلق حول الحصول على كل شيء تماما 100٪ العمل.
الكتابة للتو في pseudocode نصف لكيفية كنت تعتقد أنه يجب أن تعمل.
حسنا.
لا تحتاج إلى القيام به تماما مع هذا الموضوع حتى الآن.
ولكن لا أحد يشعر بالراحة مع ما لديهم حتى الآن،
وكأنه شيء يمكن أن نعمل معا مع؟
لا أحد يريد أن يتطوع؟ أو سوف يختار بشكل عشوائي.
فإنه ليس من الضروري أن يكون على حق بكل المقاييس ولكن شيء لا يمكن تعديل في حالة عمل.
[طالب] بالتأكيد. حسنا >>.
بحيث تقوم بحفظ مراجعة عن طريق النقر على أيقونة حفظ قليلا.
كنت راميا، أليس كذلك؟ >> [طالب] نعم. >> [بودين] حسنا.
حتى الآن لا أستطيع مراجعة عرض الخاص بك ويمكن سحب ما يصل الجميع إلى مراجعة.
وهنا لدينا - حسنا.
حتى ذهب راميا مع حل العودية، الذي هو بالتأكيد الحل صحيح.
هناك طريقتان يمكنك القيام به هذه المشكلة.
يمكنك أن تفعل ذلك إما تكراري أو بشكل متكرر.
ويمكن أيضا معظم المشاكل التي تواجه الذي يمكن القيام به بشكل متكرر أن يتم تكرارا.
حتى هنا فعلناه ذلك بشكل متكرر.
>> لا شخص تريد تعريف ما يعنيه أن تكون وظيفة العودية؟
[طالب] عندما يكون لديك وظيفة الكلمة نفسها
وثم استدعاء نفسها حتى يخرج مع صحيح وحقيقي. نعم >>.
وظيفة العودية هو مجرد وظيفة التي تطلق على نفسها.
هناك ثلاثة أشياء كبيرة أن وظيفة العودية يجب أن يكون.
الأول هو واضح، فإنه يطلق على نفسه.
والثاني هو الحالة الأساسية.
حتى في مرحلة ما وظيفة يحتاج إلى وقف تطلق على نفسها،
وهذا ما هو الحال للقاعدة.
حتى هنا ونحن نعلم أننا يجب أن يتوقف، يجب أن نتخلى في بحثنا
عندما يساوي بداية النهاية - وسنذهب على ما يعنيه ذلك.
ولكن في النهاية، وآخر شيء هذا أمر مهم لوظائف العودية:
يجب الاقتراب وظائف على نحو ما الحالة الأساسية.
مثل إذا كنت لا تحديث اي شيء في الواقع عند إجراء المكالمة الثانية عودي،
إذا كنت حرفيا فقط وظيفة الدعوة مرة أخرى مع نفس الحجج
وتغيرت أي المتغيرات العالمية أو أي شيء،
وأنك لن تصل إلى الحالة الأساسية، وفي هذه الحالة فهذا أمر سيئ.
فسوف تكون لالعودية لانهائية وتجاوز سعة مكدس.
ولكن هنا نرى أن التحديث يحدث منذ بدء نقوم بتحديث + نهاية / 2،
نحن تحديث حجة نهاية هنا، نحن تحديث الحجة بداية هنا.
حتى في كل المكالمات العودية نقوم بتحديث شيء. حسنا.
هل ترغب في السير بنا من خلال الحل؟ بالتأكيد >>.
أنا باستخدام SearchHelp بحيث في كل مرة أقوم هذه الدعوة وظيفة
لدي بداية حيث أنا أبحث عن في مجموعة والنهاية
من حيث أنا أبحث الصفيف.
>> في كل خطوة حيث انها تقول انها عنصر الأوسط، والذي هو بداية نهاية + / 2،
هو أن يساوي ما تبحث عنه؟
وإذا كان، ثم تبين لنا ذلك، وأعتقد أن يحصل على تمرير لأعلى مستويات العودية.
وإذا كان هذا غير صحيح، ثم نتحقق ما إذا كان هذا القيمة الوسطى للصفيف كبير جدا،
وفي هذه الحالة ننظر إلى النصف الأيسر من مجموعة من خلال الذهاب من البداية للمؤشر الأوسط.
وإلا فإننا نفعل النصف النهائي.
[بودين] حسنا.
فكرة جميلة.
حسنا، لذلك بضعة أشياء، والواقع، وهذا هو الشيء رفيع المستوى
أن وأنك لن تحتاج إلى معرفته لهذه الدورة، ولكن كان صحيحا.
وظائف متكررة، تسمع دائما انهم صفقة سيئة
لأنه إذا كان استدعاء متكرر نفسك في كثير من الأحيان، وتحصل على تجاوز سعة مكدس
منذ ذلك الحين، كما قلت من قبل، كل وظيفة يحصل إطاره كومة الخاصة.
لذلك كل دعوة من وظيفة العودية يحصل إطاره كومة الخاصة.
إذا كان الأمر كذلك إجراء المكالمات العودية 1000، وتحصل على إطارات المكدس 1،000،
والسرعة التي تؤدي إلى وجود عدد كبير جدا من إطارات المكدس وتحطيم الأشياء فقط.
ولهذا السبب ظائف عودي سيئة عموما.
ولكن هناك ما يسمى مجموعة فرعية لطيفة من وظائف عودي عودي وظائف الذيل،
وهذا يحدث ليكون مثالا واحدا حيث يلاحظ إذا كان المترجم هذا
وينبغي، على ما أعتقد - في ضجيج إذا كنت تمر عليها-O2 العلم
بعد ذلك سوف تلاحظ هذا هو الذيل العودية وجعل الامور جيدة.
>> فإنه سيتم إعادة استخدام الإطار مكدس نفسه مرارا وتكرارا عن كل مكالمة العودية.
وذلك منذ كنت تستخدم نفس الإطار مكدس، لا داعي للقلق بشأن
كومة من أي وقت مضى تفيض، وفي الوقت نفسه، قال مثلك من قبل،
حيث بمجرد العودة الحقيقية، ثم عليه أن يعود عن كل من هذه الأطر مكدس
والدعوة إلى 10 SearchHelp لديه للعودة إلى 9، وللعودة إلى 8.
بحيث لا يحتاج أن يحدث عندما ظائف الذيل العودية.
وذلك ما يجعل هذا الذيل هو دالة العودية لاحظ أن أي دعوة إلى إعطاء searchHelp
الدعوة التي العودية انها ما جعل انها العائدين.
حتى في المكالمة الأولى لSearchHelp، ونحن إما العودة فورا كاذبة،
العودة فورا صحيح، أو أننا إجراء مكالمة عودي إلى SearchHelp
حيث ما نقوم العودة هو ما تعود تلك الدعوة.
ونحن لا يمكن أن تفعل ذلك إذا فعلنا شيئا مثل الباحث س = SearchHelp، وعودة 2 * X،
فقط بعض التغيير عشوائي.
>> حتى الآن هذه الدعوة متكررة، وهذا الباحث س = SearchHelp دعوة متكررة،
لم يعد الذيل العودية لأنه في الواقع لا يجب أن تعود
العودة إلى إطار المكدس السابق بحيث أن الدعوة السابقة إلى وظيفة
ويمكن بعد ذلك القيام بشيء ما مع قيمة الإرجاع.
وهذا ليس الذيل متكررة، ولكن ما كان لدينا هو لطيف قبل الذيل العودية. نعم.
[وينبغي أن الطالب] لا يمكن التحقق من الحالة الأساسية الثانية الأولى
لأنه يمكن أن يكون هناك حالة حيث أنه عند تمرير الوسيطة
كنت قد تبدأ نهاية =، ولكنها قيمة الإبرة.
كان يمكن للمسألة لا ندير في الحالة التي يكون فيها هو القيمة نهاية الإبرة
أو اضافة = النهاية، بشكل مناسب، تبدأ نهاية =
وكنت قد لا محددا في الواقع أن قيمة خاصة حتى الآن،
ثم تبدأ نهاية + / 2 هو الذهاب لمجرد أن يكون نفس القيمة.
ولكن لقد عدنا بالفعل كاذبة ونحن لم التحقق في الواقع قيمة.
لذلك على أقل تقدير، في أول دعوة، إذا كان حجم 0، ثم نريد أن عودة كاذبة.
ولكن إذا كان حجم هو 1، ثم بدء هو لن ينتهي على قدم المساواة،
وسنقوم على الأقل تحقق من عنصر واحد.
ولكن أعتقد أنك على حق في أننا يمكن في نهاية المطاف في حالة حيث تبدأ نهاية + / 2،
بدء ينتهي به الأمر في نفس بداية نهاية + / 2،
لكننا في الواقع أبدا فحص هذا العنصر.
>> إذا كان الأمر كذلك فإننا أولا التحقق هو العنصر الأوسط القيمة نحن نبحث عن،
ثم يمكننا العودة فورا صحيح.
والا اذا انهم على قدم المساواة، ثم ليس هناك نقطة في مواصلة
منذ ونحن في طريقنا لمجرد تحديث لحالة ما نحن فيه على مجموعة واحدة العنصر.
إذا كان هذا عنصر واحد ليست واحدة ونحن نبحث عن،
ثم كل شيء من الخطأ. نعم.
[طالب] الشيء هو أنه منذ حجم أكبر في الواقع من عدد العناصر في الصفيف،
هناك بالفعل إزاحة - >> فهل المطاطية -
[طالب] قل لو كان حجم الصفيف 0، ثم سوف تحقق فعلا SearchHelp كومة قش من 0
على المكالمة الأولى.
مجموعة لديها حجم 0، وبالتالي فإن 0 هو - نعم >>.
هناك شيء آخر أن - أنه قد يكون من الجيد. دعنا نفكر.
إذا كان الأمر كذلك كان لمجموعة 10 عناصر والمتوسطة واحدة ونحن في طريقنا للتحقق هو مؤشر 5،
لذلك نحن فحص 5، ودعونا نقول أن القيمة هي أقل من ذلك.
لذلك نحن رمي كل شيء بعيدا في الفترة من 5 إلى الأمام.
حتى يبدأ نهاية + / 2 ستكون نهايتنا جديدة،
لذا نعم، انه سيكون دائما على البقاء إلى ما بعد نهاية الصفيف.
لو كان الحال لو كان غريبا أو حتى، ثم نتحقق، ويقول، 4،
ولكننا لا يزال بعيدا رمي -
لذا نعم، نهاية دائما ما يكون إلى ما بعد نهاية الفعلية للمجموعة.
وبالتالي فإن العناصر فإننا نركز على، نهاية دائما ما تكون واحدة بعد ذلك.
وحتى إذا كان من أي وقت مضى لا نهاية بداية متساوية، ونحن في مجموعة من حجم 0.
>> والشيء الآخر كنت أفكر هو أننا نقوم بتحديث بداية أن تبدأ نهاية + / 2،
لذلك هذا هو الحال أن أواجه مشكلة مع، حيث تبدأ نهاية + / 2
هو العنصر أننا التحقق.
دعنا نقول كان لدينا هذه المجموعة 10-العنصر. أيا كان.
حتى يبدأ نهاية + / 2 سيكون شيئا مثل هذا واحد،
واذا كان هذا لا قيمة، ويقول نحن نريد لتحديث.
قيمة أكبر، لذلك نحن نريد أن ننظر إلى هذا النصف من الصفيف.
فكيف ونحن نقوم بتحديث بداية، نحن تحديث البداية وحتى الآن يكون هذا العنصر.
ولكن هذا قد لا تزال تعمل، أو على أقل تقدير، يمكنك القيام به بداية نهاية + / 2 + 1.
[طالب] أنت لا تحتاج إلى أن تبدأ نهاية + [غير مسموع] >> نعم.
لقد بحثنا بالفعل هذا العنصر وأعلم أنها ليست تلك التي كنا نبحث عنها.
لذلك نحن لسنا في حاجة لبدء التحديث أن يكون هذا العنصر.
يمكننا تخطي فقط وبدء التحديث أن يكون هذا العنصر.
وهناك قضية من أي وقت مضى، دعنا نقول، أن هذا كان الهدف،
حتى تبدأ بعد ذلك سيكون هذا، بدء نهاية + / 2 يكون هذا شأنه،
بدء نهاية + - نعم، وأعتقد أنه يمكن أن ينتهي بهم المطاف في العودية لانهائية.
دعنا نقول انها مجرد مجموعة من حجم 2 أو مجموعة من حجم 1. وأعتقد أن هذا سوف يعمل.
ذلك في الوقت الحالي، هو أن بداية ونهاية العنصر هو 1 الى ابعد من ذلك.
ذلك العنصر الذي نحن في طريقنا للتحقق من هذا واحد،
وبعد ذلك عندما نقوم بتحديث بداية، نحن تحديث البداية وحتى تكون 0 + 1/2،
التي سوف تنتهي بنا إلى الوراء مع بداية يجري هذا العنصر.
>> لذلك نحن فحص العنصر نفسه مرارا وتكرارا.
لذلك هذا هو الحال حيث كل مكالمة العودية يجب تحديث في الواقع شيئا.
لذلك نحن بحاجة للقيام بداية نهاية + / 2 + 1، وإلا هناك حالة
حيث أننا لا تحديث فعلا البداية.
الجميع يرى ذلك؟
حسنا.
هل لديها أسئلة حول هذا الحل أو أية تعليقات أخرى؟
حسنا. هل هناك حل تكرارية أننا يمكن أن ننظر في جميع؟
فعلنا كل ما في ومتكرر؟
أو كما أعتقد إذا فتحت لها، ثم قد يكون لديك لديك واحدة تجاوز السابقة.
هل حفظ تلقائيا؟ أنا لست إيجابية.
هل لديها متكررة؟
يمكننا المشي من خلال ذلك معا إن لم يكن.
فكرة سوف تكون هي نفسها.
تكرارية الحل.
ونحن في طريقنا إلى تريد أن تفعل نفس الفكرة في الأساس
حيث أننا نريد أن تتبع نهاية الجديد للمجموعة وبداية جديدة لمجموعة
وفعل ذلك مرارا وتكرارا.
وإذا كان ما نقوم تتبع وبداية ونهاية تتقاطع من أي وقت مضى،
ثم لم نجد ذلك، ونحن يمكن أن عودة كاذبة.
فكيف أفعل ذلك؟ أي شخص لديك اقتراحات أو رمز بالنسبة لي لسحب ما يصل؟
[طالب] هل حلقة من الوقت. نعم >>.
كنت تريد الذهاب الى القيام حلقة.
>> هل لديك رمز أتمكن من سحب ما يصل، أو ما كنت ذاهب الى توحي؟
[طالب] أعتقد ذلك. حسنا >>. وهذا يجعل الأمور أسهل. ما هو اسمك؟
[طالب] لوكاس.
مراجعة 1. حسنا.
المنخفض هو ما أسميناه تبدأ قبل.
متروك تماما ليس ما كنا نسميها قبل نهاية.
في الواقع، الآن داخل نهاية الصفيف. انها عنصر لا بد أن ننظر.
منخفضة جدا 0، هو ما يصل حجم الصفيف - 1،
ونحن الآن حلقات، ونحن فحص و-
أعتقد يمكنك المشي من خلال ذلك.
ما هو التفكير الخاص بك من خلال هذا؟ المشي لنا من خلال التعليمات البرمجية.
[طالب] بالتأكيد. ننظر إلى قيمة كومة قش في الوسط، وذلك لمقارنة الإبرة.
حتى لو كان أكبر من الإبرة الخاص بك، فإنك ترغب في - أوه، في الواقع، ينبغي أن يكون الوراء.
كنت تريد الذهاب الى رمي بعيدا النصف الأيمن، وهكذا نعم، هذا يجب أن يكون الطريق.
[بودين] لذلك ينبغي أن يكون هذا أقل؟ هل هذا ما قال لك؟ >> [طالب] نعم.
[بودين] حسنا. أقل.
إذا كان الأمر كذلك ما نحن نبحث في أصغر من ما نريد،
ثم نعم، نحن نريد أن نرمي النصف الأيسر،
وهو ما يعني أننا نقوم بتحديث كل ما تفكر
عن طريق تحريك الأقل إلى الحق من الصفيف.
هذا يبدو جيدا.
اعتقد انه لديه نفس المشكلة ان قلنا على واحد السابقة،
حيث إذا منخفضة هو 0 ويرجع 1، ثم منخفضة تصل + / 2 هو الذهاب الى وضع ليكون الشيء نفسه مرة أخرى.
>> وحتى لو كان هذا ليس هو الحال، فإنه لا يزال أكثر كفاءة على أقل تقدير
لمجرد رمي بعيدا العنصر نظرنا فقط الذي نعرفه هو خطأ.
منخفضة جدا + لأعلى / 2 + 1 - >> [طالب] وهذا ينبغي أن يكون في الاتجاه الآخر.
[بودين] أو هذا ينبغي أن يكون - 1، والآخر يجب أن يكون + 1.
[طالب] ويجب أن يكون هناك علامة يساوي مزدوجة. >> [بودين] نعم.
[طالب] نعم.
حسنا.
وأخيرا، الآن أن لدينا هذا 1 + - 1 الشيء،
هل هو - أنه قد لا يكون - هل من الممكن من أي وقت مضى لانخفاض في نهاية المطاف مع قيمة أكبر من يصل؟
أعتقد أن الطريقة الوحيدة التي يمكن أن يحدث - هل من الممكن؟ >> [طالب] أنا لا أعرف.
ولكن إذا كان يحصل على اقتطاع ومن ثم يحصل أن 1 ناقص ومن ثم - نعم >>.
[طالب] وربما الحصول على وعابث.
وأعتقد أنه يجب أن تكون جيدة فقط ل
لذلك ينتهي بهم الأمر إلى انخفاض أنها يجب أن تكون على قدم المساواة، على ما أعتقد.
ولكن إذا كانوا على قدم المساواة، ثم ونحن لن فعلت حلقة حين لتبدأ
وكنا قد عادوا للتو القيمة. لذلك أعتقد نحن في حالة جيدة الآن.
لاحظت أنه على الرغم من هذه المشكلة لم تعد متكررة،
نفس النوع من الأفكار تنطبق حيث يمكننا أن نرى كيف أن هذا يفسح المجال بسهولة
عودي إلى حل من حقيقة أننا مجرد تحديث مؤشرات مرارا وتكرارا،
نحن جعل المشكلة أصغر وأصغر، ونحن نركز على مجموعة فرعية من مجموعة.
[طالب] إذا منخفضة هو 0 وحتى 1، وكلاهما يكون 0 + 1/2، التي من شأنها أن تذهب إلى 0،
ومن ثم يمكن لأحد أن يكون + 1، فإن للمرء أن يكون - 1.
[طالب] أين نحن فحص المساواة؟
مثل إذا واحد هو في الواقع الأوسط إبرة؟
نحن لا نقوم حاليا ذلك؟ أوه!
إذا it's -
نعم. يمكننا القيام به وليس فقط اختبار إلى هنا لأن دعونا نقول منتصف الأولى -
[طالب] انها في الواقع ليست مثل رمي بعيدا محدد.
حتى إذا كنت رمي ​​بعيدا محدد، لديك للتحقق من ذلك الأول أو أيا كان.
ه. نعم. >> [طالب] نعم.
حتى الآن لقد وضعنا بعيدا واحدة ونحن ننظر حاليا في،
وهو ما يعني أننا في حاجة الآن لدينا أيضا
إذا كان (كومة قش [(الأقل حتى +) / 2] == إبرة)، ثم يمكننا العودة الحقيقية.
وعما إذا كان أضع آخر أو كما لو أنه يعني حرفيا الشيء نفسه
لأن عادوا هذا صحيح.
وهكذا لن أضع الا اذا، ولكن لا يهم.
>> آخر حتى إذا كان آخر، هذا هذا، وهذا هو الشيء المشترك أفعل
حيث حتى لو كان هو الحالة التي يكون فيها كل شيء جيد هنا،
مثل انخفاض لا يمكن أبدا أن تكون أكبر من يصل، انها ليست حول ما إذا كان يستحق التفكير هذا صحيح.
لذلك قد كذلك يقول بينما هو انخفاض أقل من أو يساوي
أو أثناء المنخفض أقل من
حتى إذا كانت تساوي أو منخفضة من أي وقت مضى يحدث لتمرير ما يصل،
ثم يمكننا الخروج من هذه الحلقة.
الأسئلة والشواغل والتعليقات؟
حسنا. هذا يبدو جيدا.
الآن نريد أن نفعله الفرز.
إذا ذهبنا إلى مراجعة بلدي الثاني، ونحن نرى نفس هذه الأرقام،
ولكن الآن أنها لم تعد من أجل فرزها.
ونحن نريد لتنفيذ الفرز باستخدام أي خوارزمية في O ن ن سجل.
ذلك الذي خوارزمية هل أعتقد أننا ينبغي أن تنفذ هنا؟ >> [طالب] الترتيب دمج.
[بودين] نعم. دمج النوع هو O (N سجل ن)، بحيث ما نحن بصدد القيام به.
والمشكلة ستكون مشابهة جدا،
حيث يضفي نفسها بسهولة إلى حل العودية.
يمكننا تأتي أيضا مع حل تكرارية إذا كنا نريد،
ولكن سوف يكون من الأسهل العودية وهنا ينبغي لنا أن نفعل العودية.
أعتقد أننا سوف يسير من خلال دمج النوع الأول،
على الرغم من أن هناك فيديو جميل على دمج النوع بالفعل. [ضحك]
دمج النوع حتى هناك - وأنا إضاعة الكثير لهذه الورقة.
أوه، هناك واحدة فقط من الزمن.
دمج ذلك.
أوه، 1، 3، 5.
حسنا.
دمج يأخذ اثنين صفائف منفصلة.
على حد سواء بشكل فردي مصنفة تلك المصفوفات اثنين.
لذلك هذه المجموعة، 1، 3، 5، فرزها. هذه المجموعة، 0، 2، 4، فرزها.
الآن ما يجب عليك فعله هو دمج الجمع بينها في مجموعة واحدة التي هي في حد ذاتها فرزها.
لذلك نحن نريد مجموعة من حجم 6 التي ستكون لدينا هذه العناصر داخل منه
من أجل فرزها.
>> وحتى نتمكن من الاستفادة من حقيقة أن يتم تصنيف هذه صفيفين
للقيام بذلك في الوقت الخطية،
معنى الخطية إذا كانت هذه المرة هي مجموعة X الحجم وهذا هو حجم Y،
ثم يجب أن تكون الخوارزمية مجموع O (X + Y). حسنا.
حتى اقتراحات.
[طالب] هل يمكن أن نبدأ من اليسار؟
لذلك عليك وضع ال 0 إلى أسفل أولا ثم 1 ثم هنا كنت في ال 2.
لذلك نوع من مثل لديك علامة التبويب التي تتحرك إلى اليمين. >> [بودين] نعم.
لكل من هذه المصفوفات إذا ركزنا فقط على العنصر الموجود في أقصى اليسار.
لأن كل من يتم فرز المصفوفات، ونحن نعلم أن هذه الأركان 2
هي أصغر العناصر في أي مجموعة.
وهذا يعني أن 1 من هذه العناصر 2 يجب أن يكون أصغر عنصر في مجموعتنا المدمجة.
انها مجرد أن ذلك يحدث أصغر هي واحد على هذا هو الوقت المناسب.
لذلك نحن نأخذ 0، أدخله على اليسار لأن 0 أقل من 1،
حتى تأخذ 0، أدخلها في موقفنا أولا، ثم نقوم بتحديث هذه
لنركز الآن على العنصر الأول.
والآن نكرر.
حتى الآن ما قارنا 2 و 1. 1 هو أصغر، لذلك سنقوم بإدراج 1.
نقوم بتحديث هذا المؤشر للإشارة إلى هذا الرجل.
الآن نحن نفعل ذلك مرة أخرى، لذلك 2. وهذا التحديث، قارن هذه 2، 3.
هذه التحديثات، ثم 4 و 5.
بحيث يتم الدمج.
>> وينبغي أن يكون واضحا جدا أن الوقت قد حان منذ الخطية نذهب فقط عبر كل عنصر مرة واحدة.
وهذا هو أكبر خطوة لتنفيذ دمج النوع يقوم به هذا.
وانها ليست بالأمر الصعب.
بضعة أشياء ما يدعو للقلق هو دعونا نقول كنا دمج 1، 2، 3، 4، 5، 6.
في هذه الحالة نحن في نهاية المطاف في السيناريو هذا واحد حيث سيكون أصغر حجما،
ثم نقوم بتحديث هذا المؤشر، هذا واحد سيكون أصغر حجما وتحديث هذا،
هذا واحد من أصغر، والآن عليك أن تعترف
عندما كنت فعلا نفدت عناصر للمقارنة مع.
منذ أننا استنفدنا بالفعل هذه المجموعة بأكملها،
الآن كل شيء في هذه المجموعة للتو بإدراجه في هنا.
إذا كان الأمر كذلك فإننا نتعرض إلى أي وقت مضى إلى النقطة التي يتم دمج تماما لدينا واحدة من صفائف بالفعل،
ثم نأخذ فقط كل عناصر مجموعة أخرى وإدراجها في نهاية الصفيف.
حتى نتمكن من مجرد إدراج 4، 5، 6. حسنا.
وهذا هو شيء واحد لمشاهدة ل.
تنفيذ ذلك يجب أن يكون الخطوة 1.
دمج فرز ثم بناء على ذلك، فإنه من 2 خطوات، 2 الخطوات سخيفة.
دعونا نعطي هذه المجموعة فقط.
دمج النوع حتى، هو الخطوة 1 لكسر متكرر الصفيف الى نصفين.
تقسيم هذه المجموعة حتى الى نصفين.
لدينا الآن 4، 15، 16، 50 و 8، 23، 42، 108.
والآن نحن نفعل ذلك مرة أخرى ويمكننا تقسيم هذه الى نصفين.
أنا فقط تفعل ذلك في هذا الجانب.
SO 4 و 15 و 16 و 50.
ونحن نفعل نفس الشيء هنا.
وتقسيم ونحن الآن مرة أخرى إلى نصفين.
ونحن لدينا 4، 15، 16، 50.
بحيث هو قضيتنا الأساسية.
مرة واحدة في المصفوفات ذات حجم 1، ثم نتوقف مع تنقسم الى نصفين.
>> الآن ماذا نفعل مع هذا؟
نحن في نهاية المطاف سوف كسر هذا أيضا أسفل إلى 8، 23، 42، و 108.
حتى الآن أننا في هذه المرحلة، الخطوة الآن اثنين من نوع الدمج ودمج أزواج فقط للقوائم.
لذلك نحن نريد لدمج هذه. ندعو فقط الدمج.
نحن نعرف دمج هذه سيعود من أجل فرزها.
4، 15.
الآن نريد أن دمج هذه، والتي سيعود قائمة مع تلك من أجل فرزها،
16، 50.
نحن دمج تلك - لا أستطيع أن أكتب - 8، 23 و 42 و 108.
لذلك لدينا أزواج المدمجة مرة واحدة.
الآن نحن فقط دمج مرة أخرى.
تلاحظ أن يتم فرز كل من هذه القوائم في حد ذاته،
وبعد ذلك يمكننا دمج هذه القوائم فقط للحصول على قائمة من حجم 4 التي تم فرزها
ودمج هاتين القائمتين للحصول على قائمة من حجم 4 التي تم فرزها.
وأخيرا، يمكننا دمج هاتين القائمتين من حجم 4 للحصول على قائمة واحدة من حجم 8 التي تم فرزها.
ذلك أن نرى أن هذا هو العام ن ن السجل، رأينا بالفعل أن الدمج هو الخطية،
لذلك عندما نتعامل مع دمج هذه، لذلك مثل التكلفة الإجمالية للدمج
لهذه القائمتين هو 2 فقط لأنه -
أو جيدا، انها O ن، ن ولكن هنا هو مجرد هذه العناصر 2، لذلك فمن 2.
وسوف تكون هذه 2 2 و 2 سوف تكون هذه 2 و 2 سيكون هذه 2،
لذلك عبر كل من دمج أننا بحاجة إلى القيام به، نلجأ إلى القيام ن.
مثل 2 + 2 + 2 + 2 هو 8، وهو ن،
ذلك هو ن تكلفة دمج في هذه المجموعة.
ثم نفس الشيء هنا.
سنقوم دمج هذه 2، ثم هذه 2، وحدة الدمج هذه سوف يستغرق أربع عمليات،
وهذا الدمج اتخاذ أربع عمليات، ولكن مرة أخرى، وبين كل هذه،
نحن في نهاية المطاف دمج ن مجموع الأشياء، وهكذا يأخذ هذه الخطوة ن.
وهكذا يأخذ كل مستوى العناصر التي اندمجت ن.
>> وكيف العديد من المستويات هناك؟
على كل مستوى، لدينا مجموعة ينمو حسب حجم 2.
هنا لدينا هي صفائف من حجم 1، هنا انهم من حجم 2، هنا انهم من حجم 4،
وأخيرا، وانهم من حجم 8.
منذ ذلك يتضاعف، وهناك سيكون ما مجموعه سجل ن من هذه المستويات.
حتى مع دخول ن المستويات، المستوى الفردي مع كل ن إجمالي العمليات،
نحصل على السجل ن ن الخوارزمية.
الأسئلة؟
لقد جعل الناس بالفعل تقدما بشأن كيفية تنفيذ ذلك؟
هو أي شخص بالفعل في حالة حيث يمكنني سحب للتو التعليمات البرمجية الخاصة بهم؟
وأستطيع أن أعطي لمدة دقيقة.
هذا واحد سيكون لفترة أطول.
أنا أوصي تتكرر -
لم يكن لديك للقيام العودية لدمج
لأن القيام العودية لدمج، وأنت تسير لدينا لتمرير مجموعة من مختلف الأحجام.
يمكنك، لكنه مزعج.
ولكن العودية لنوع نفسه من السهل جدا.
كنت للتو دعوة حرفيا النوع على النصف الأيسر، النصف الأيمن على نوع. حسنا.
أي شخص لديه أي شيء أستطيع سحب ما يصل بعد؟
وإلا سوف أعطي لمدة دقيقة.
حسنا.
أي شخص يحصل شيء يمكننا العمل معها؟
وإلا سوف نعمل فقط مع هذا ومن ثم التوسع من هناك.
>> أي شخص لديها أكثر من هذا أستطيع أن سحب ما يصل؟
[طالب] نعم. يمكنك سحب ما يصل الألغام. حسنا >>.
نعم!
[طالب] كان هناك الكثير من الشروط. أوه >>، واطلاق النار. يمكنك -
[طالب] لدي لحفظه. نعم >>.
وكذلك فعل نقوم به الدمج بشكل منفصل.
أوه، ولكنها ليست سيئة لهذه الدرجة.
حسنا.
لذلك هو في حد ذاته نوع فقط يدعو mergeSortHelp.
يشرح لنا ما mergeSortHelp لا.
[طالب] MergeSortHelp جميلة لا بكثير الخطوات الرئيسيتين،
وهو لفرز كل شوط من الصفيف ثم دمج كل منهما.
[بودين] حسنا، حتى تعطي لي الثانية.
وأعتقد أن هذا - >> [طالب] ولست بحاجة ل-
نعم. أنا في عداد المفقودين شيئا.
في الدمج، وأنا أدرك أنني بحاجة إلى إنشاء مجموعة جديدة
لأن أنا لا يمكن أن تفعل ذلك في المكان. نعم >>. لا يمكنك. تصحيح.
[طالب] لذلك أنا خلق مجموعة جديدة.
لقد نسيت في نهاية دمج لإعادة تغيير.
حسنا. نحن بحاجة إلى مجموعة جديدة.
في دمج النوع، وهذا هو دائما تقريبا صحيح.
جزء من تكلفة خوارزمية أفضل وقت الحكيم
هو دائما تقريبا التي تحتاج لاستخدام الذاكرة أكثر قليلا.
حتى هنا، بغض النظر عن كيفية القيام دمج النوع،
قد تحتاج حتما إلى استخدام بعض الذاكرة الإضافية.
هو أو هي إنشاء مجموعة جديدة.
ثم يقول في النهاية نحن بحاجة فقط لنسخ مجموعة جديدة في مجموعة الأصلي.
[طالب] أعتقد ذلك، نعم.
أنا لا أعرف ما اذا كان يعمل من حيث العد بالرجوع أو أيا كان -
نعم، أنه سوف يعمل. >> [طالب] حسنا.
هل جربت تشغيل هذا؟ >> [طالب] لا، ليس بعد. حسنا >>.
حاول تشغيل، ثم سأتحدث عن ذلك لثانية واحدة.
[طالب] أنا بحاجة إلى كل النماذج الدالة وكل شيء، على الرغم من، أليس كذلك؟
وظيفة النماذج. أوه، كنت تعني مثل - نعم.
نوع تدعو mergeSortHelp.
>> لذلك من أجل ترتيب لدعوة mergeSortHelp، يجب إما mergeSortHelp تم تعريفها
قبل الفرز أو نحن فقط في حاجة إلى النموذج. مجرد نسخ ولصق ذلك.
وبالمثل، mergeSortHelp تدعو دمج،
ولكن لم يتم دمج تحدد بعد، حتى نتمكن من مجرد السماح mergeSortHelp تعرف
أن هذا ما يجري دمج لتبدو وكأنها، وانتهى الأمر.
حتى mergeSortHelp.
لدينا مشكلة هنا حيث لدينا قاعدة بأي حال من الأحوال.
MergeSortHelp هو عودي، عودي حتى أي وظيفة
سوف تحتاج الى بعض النوع من الحالة الأساسية أن تعرف متى تتوقف بشكل متكرر يدعو نفسه.
ما حالتنا ستكون قاعدة هنا؟ نعم.
[طالب] إذا كان حجم هو 1؟ >> [بودين] نعم.
مثل ذلك رأينا هناك حق، توقفنا صفائف تقسيم
عندما وصلنا إلى صفائف حجم 1، والذي حتما يتم تصنيف أنفسهم.
حتى إذا كان حجم يساوي 1، ونحن نعلم بالفعل يتم فرز الصفيف،
حتى نتمكن من العودة فقط.
>> تلاحظ أن هذا الفراغ، لذلك نحن لا يعودون أي شيء خاص، نعود فقط.
حسنا. بحيث لقضيتنا الأساسية.
أعتقد حالتنا قاعدة يمكن أيضا أن يكون إذا كان لنا أن يحدث ليكون دمج مجموعة من حجم 0،
ربما نريد التوقف عند نقطة ما،
لذلك يمكننا القول فقط حجم أقل من 2 أو أقل من أو يساوي 1
بحيث هذا العمل لأي مجموعة الآن.
حسنا.
بحيث لقضيتنا الأساسية.
الآن تريد أن المشي من خلال دمج لنا؟
ماذا يعني كل هذه الحالات؟
هنا، نقوم به مجرد فكرة نفسها، -
[طالب] I تحتاج إلى تمرير جميع المكالمات مع حجم mergeSortHelp و.
أضفت حجم باعتبارها الأولية إضافية وانها ليست هناك، مثل حجم / 2.
[بودين] أوه، حجم / 2، وحجم / 2. >> [طالب] نعم، وأيضا في وظيفة أعلاه أيضا.
[بودين] هنا؟ >> [طالب] فقط الحجم. >> [بودين] أوه. الحجم، حجم؟ >> [طالب] نعم.
[بودين] حسنا.
اسمحوا لي أن التفكير للحظة.
لا اجهتنا مشكلة؟
نحن دائما علاج اليسار ك 0. >> [طالب] رقم
وهذا خطأ أيضا. آسف. ينبغي أن يكون البداية. نعم.
[بودين] حسنا. أود أن أفضل.
ونهاية. حسنا.
حتى الآن لا تريد السير بنا من خلال دمج؟ >> [طالب] حسنا.
أنا مجرد المشي من خلال هذه المجموعة الجديدة التي قمت بإنشائه.
حجمه هو حجم ذلك الجزء من مجموعة أننا نريد أن يكون فرز
ومحاولة للعثور على العناصر التي ينبغي لي أن وضعت في خطوة مجموعة جديدة.
حتى للقيام بذلك، أولا أنا التحقق إذا كان النصف الأيسر من مجموعة عناصر ما زالت تعاني من أي أكثر من ذلك،
وإذا لم يحدث ذلك، ثم تذهب الى هذا الشرط آخر، والتي تقول فقط
حسنا، يجب أن يكون الحق في الصفيف، ونحن سوف أضع ذلك في الفهرس الحالي من newArray.
>> ثم خلاف ذلك، وأنا التحقق إذا تم الانتهاء أيضا الجانب الأيمن من الصفيف،
في هذه الحالة أنا فقط وضعت في اليسار.
قد لا يكون في الواقع أن الضرورة. لست متأكدا.
ولكن على أي حال، والآخران الاختيار أي من هما أصغر في اليسار أو اليمين.
وأيضا في كل حالة، وأنا تزايد أيهما نائب I زيادة.
[بودين] حسنا.
التي تبدو جيدة.
هل لديها تعليقات أو أسئلة أو مخاوف؟
وبالتالي فإن أربع حالات التي لدينا لتحقيق الأشياء إلى الوجود فقط - أو يبدو الخمس -
ولكن علينا أن ننظر ما إذا كان اليسار ومجموعة ينفد من الاشياء ونحن بحاجة لدمج،
ما إذا كان قد تشغيل مجموعة الحق في الخروج من الأشياء التي تحتاج إلى دمج -
أنا لافتا في شيء.
حتى ما إذا كانت مجموعة اليسار قد نفد من الأشياء أو مجموعة الحق قد نفد من الأشياء.
تلك هي حالتين.
نحن بحاجة أيضا حالة ما إذا كانت تافهة من الصواب أقل من الصواب.
ثم نريد أن اختيار الصواب.
تلك هي الحالات.
لذلك كان هذا الحق، لذلك هذا هو ذلك.
ترك مجموعة. انها 1، 2، 3. حسنا. لذا نعم، تلك هي الأمور الأربعة أننا قد ترغب في القيام به.
ونحن لن نذهب أكثر تكرارية الحل.
لا أنصح -
دمج النوع هو مثال على وظيفة في آن معا لا ذيل متكررة،
انها ليست سهلة لجعله ذيل متكررة،
ولكن أيضا ليس من السهل جدا أن تجعل من تكرارية.
هذا من السهل جدا.
هذا النوع من تنفيذ الدمج،
دمج، بغض النظر عن ما تفعله، وأنت تسير لبناء الدمج.
>> دمج النوع حتى بنيت على رأس الدمج بشكل متكرر فقط هذه الخطوط الثلاثة.
تكراري، هو أكثر مزعج وأكثر صعوبة للتفكير.
ولكن لاحظ أنه ليس من الذيل متكررة منذ mergeSortHelp - عندما تطلق على نفسها -
ما زال يحتاج إلى فعل الأشياء بعد هذه المكالمة عوائد متكررة.
لذلك يجب أن هذا الإطار مكدس لا تزال موجودة حتى بعد استدعاء هذا.
ثم عند استدعاء هذا، يجب أن الإطار مكدس لا تزال موجودة
لأنه حتى بعد هذا النداء، ونحن لا تزال بحاجة إلى الدمج.
ومن غير بديهي لجعل هذا الذيل العودية.
الأسئلة؟
حسنا.
الذهاب حتى العودة لفرز - أوه، هناك شيئان اريد ان تظهر. حسنا.
العودة للترتيب، سوف نفعل ذلك بسرعة.
أو البحث. نوع؟ الفرز. نعم.
العودة إلى بدايات الفرز.
نريد لإنشاء خوارزمية فرز الصفيف باستخدام أي خوارزمية
في O ن.
فكيف يكون هذا ممكنا؟ هل لديها أي نوع من ال -
I لمح قبل في -
إذا نحن على وشك تحسين سجل من لا يوجد لO ن،
فقد قمنا بتحسين خوارزمية وقتنا الحكيم،
وهو ما يعني ما نحن ذاهبون إلى القيام به للتعويض عن ذلك؟
[طالب] الفضاء. نعم >>. ونحن في طريقنا إلى استخدام مساحة أكبر.
وليس حتى مجرد مساحة أكبر، انها مساحة أكثر أضعافا مضاعفة.
لذلك أعتقد أن هذا النوع من الخوارزمية هو شيء زائف، زائف polynom -
الزائفة - لا أستطيع تذكر. الزائفة شيء.
ولكن هذا لأننا في حاجة إلى استخدام الكثير من الفضاء
أن هذا يمكن تحقيقه ولكن واقعية لا.
>> وكيف يمكننا تحقيق ذلك؟
يمكننا تحقيق ذلك إذا نحن نضمن أن أي عنصر معين في مجموعة
أقل من حجم معين.
لذلك دعونا نقول فقط أن حجم هو 200،
أي عنصر في صفيف أقل من حجم 200.
وهذا هو في الواقع واقعية جدا.
يمكنك بسهولة جدا من مجموعة أن تعرف كل شيء فيه
سيكون أقل من عدد بعض.
إذا كان لديك مثل ناقلات ضخمة للغاية بعض أو شيء
لكنك تعلم كل شيء سيكون بين 0 و 5،
ثم انها سوف تكون أسرع بكثير للقيام بذلك.
وربط على أي من العناصر هو 5،
لذلك هذا محدد، وهذا هو مقدار الذاكرة وأنت تسير إلى استخدام.
وبالتالي فإن المربوطة 200.
من الناحية النظرية هناك دائما عدد صحيح محدد منذ لا يمكن إلا أن تصل إلى 4 مليار دولار،
ولكن هذا غير واقعي ومنذ ذلك الحين ونحن سنكون باستخدام الفضاء
بناء على أمر من 4 مليار دولار. ولهذا غير واقعي.
ولكن هنا سوف نقوله منضم لدينا هو 200.
خدعة لفعل ذلك في O n هو من جعل آخر ونحن مجموعة تسمى تهمة حجم محدد.
في الواقع كذلك، وهذا هو اختصار ل- أنا في الواقع لا أعرف إذا كان ضجيج يفعل ذلك.
ولكن في دول مجلس التعاون الخليجي على أقل تقدير - أنا على افتراض أنه لا ضجيج أيضا -
وهذا مجرد تهيئة مجموعة بالكامل لتكون 0S.
حتى لو كنت لا تريد أن تفعل ذلك، ثم ما يمكن القيام به بشكل منفصل عن (كثافة العمليات ط = 0؛
ط <BOUND، وأنا + +) وتعول [أنا] = 0؛
حتى الآن كل شيء يتم تهيئة إلى 0.
I تكرار عبر مجموعة بلدي،
وما أفعله هو أنني أعول عدد كل - دعنا نذهب الى هنا.
لدينا 4، 15، 16، 50، 8، 23، 42، 108.
ما أنا العد هو عدد تكرارات كل من هذه العناصر.
دعونا نضيف فعلا أكثر زوجين في هنا مع بعض يكرر.
وبالتالي فإن قيمة لدينا هنا، وقيمة ذلك ستكون مجموعة [ط].
لذلك يمكن أن تكون فال 4 أو 8 أو أيا كان.
والآن أنا أعول عدد من تلك القيمة رأيت،
حتى التهم [فال] + +؛
بعد ذلك، المهم في الأمر هو الذهاب الى تبدو شيء مثل 0001.
دعونا نفعل التهم [فال] - ملزمة + 1.
>> الآن هذا مجرد لحساب لحقيقة أننا بدأنا من 0.
حتى إذا 200 هو سيكون لدينا عدد أكبر،
0 حتي 200 ثم 201 الأشياء.
حتى التهم، وأنها سوف تبدو وكأنها 00001 لأننا واحد 4.
ثم سيكون لدينا 0001 حيث ستكون لدينا 1 في مؤشر 8 من العد.
سيكون لدينا مؤشر 2 في 23 من العد.
سيكون لدينا مؤشر 2 في 42 من العد.
حتى نتمكن من استخدام العد.
حتى num_of_item = التهم [أنا].
وإذا كان الأمر كذلك num_of_item هو 2، وهذا يعني أننا نريد لادخال عدد 2 من أنا
في مجموعتنا فرزها.
لذلك نحن بحاجة لتتبع مدى نحن في الصفيف.
= ذلك مؤشر 0.
مجموعة - أنا أكتب فقط.
التهم -
مجموعة [مؤشر + +] = ط؛
هو أن ما أريد؟ أعتقد أن هذا ما أريد.
نعم، هذا يبدو جيدا. حسنا.
حتى لا يفهم الجميع ما هو الغرض من مجموعة التهم بلدي؟
فإنه يعول على عدد من الأحداث من كل من هذه الأرقام.
ثم أنا بالتكرار عبر مجموعة التهم التي،
وموقف إيث في مجموعة التهم
هو عدد من أنا التي يجب أن تظهر في مجموعة بي فرزها.
هذا هو السبب في التهم من 4 سوف يكون 1
وتعول من 8 سيكون 1، التهم من 23 ستكون 2.
ولهذا كم منهم أريد أن تضاف الى مجموعة بلدي فرزها.
ثم أفعل ذلك تماما.
أنا أنا هو إدخال num_of_item في مجموعة بي فرزها.
>> الأسئلة؟
وذلك مرة أخرى، وهذا هو الوقت الخطية بما أننا بالتكرار ما يزيد قليلا على هذا مرة واحدة،
لكنه أيضا خطية في هذا العدد ما يحدث أن تكون،
وذلك يعتمد بشكل كبير على ما منضم الخاصة بك.
مع متجهة من 200، وهذا ليس سيئا.
إذا منضم الخاص سيكون 10،000، ثم هذا هو أسوأ قليلا،
ولكن إذا منضم الخاص بك هو الذهاب إلى 4 مليار دولار، وهذا غير واقعي تماما
وهذه المجموعة ستكون لدينا لتكون من حجم 4 مليار وهو غير واقعي.
ولهذا ذلك. الأسئلة؟
[رد الطالب غير مسموع] >> حسنا.
أدركت شيئا واحدا أخرى عندما كنا يمر بها.
أعتقد أن المشكلة كانت في لوكاس، وربما كل واحد رأيناه.
لقد نسيت تماما.
الشيء الوحيد الذي كنت أريد أن أعلق عليه هو أنه عندما كنت تتعامل مع أشياء مثل مؤشرات،
أنت لا ترى حقا هذا عندما كنت تكتب لحلقة،
لكن من الناحية الفنية، كلما كنت تتعامل مع هذه المؤشرات،
يجب عليك دائما جميلة كثيرا التعامل مع الأعداد الصحيحة غير الموقعة.
والسبب في ذلك هو عندما كنت تتعامل مع الأعداد الصحيحة وقعت،
إذا كان الأمر كذلك لديك 2 أعداد صحيحة وقعت إضافتها معا
وأنهم في نهاية المطاف كبير جدا، ثم ينتهي بك الأمر مع رقم سالب.
بحيث تجاوز عدد صحيح ما هو.
>> إذا كنت تضيف 2 مليار و 1 مليار دولار، في نهاية المطاف مع I 1 مليار السلبية.
هذه هي الطريقة الصحيحة تعمل على أجهزة الكمبيوتر.
وبالتالي فإن المشكلة مع استخدام -
هذا شيء طيب إلا إذا كان يحدث أن تكون منخفضة 2 مليار و يحدث حتى تكون 1 مليار
ثم وهذا سيكون سلبيا 1 مليار و بعد ذلك نحن ذاهبون الى تقسيم هذا بنسبة 2
وينتهي مع 500 مليون السلبية.
لذلك هذا هو فقط مسألة إذا كنت يحدث ليكون البحث من خلال مجموعة
المليارات من الأشياء.
ولكن إذا حدث انخفاض + حتى تجاوز، ثم وهذا هو المشكلة.
بأسرع ما جعلها غير الموقعة، ثم 2 بليون نسمة 1000000000 هو 3 مليار دولار.
3000000000 مقسوما على 2 هو 1.5 مليار دولار.
وذلك في أقرب وقت انهم غير موقعة، كل شيء على ما يرام.
وحتى هذا أيضا مسألة عندما كنت أكتب رأيك عن الحلقات،
وفعلا، فإنه من المحتمل أن تلقائيا.
فإنه في الواقع مجرد الصراخ عليك.
حتى إذا كان هذا الرقم هو أكبر من أن يكون صحيحا في مجرد أنه من المناسب ولكن في عدد صحيح غير الموقعة،
سوف يصيح في لكم، لذلك هذا هو السبب في أنك لن تشغيل حقا في هذه القضية.
يمكنك أن ترى أن مؤشر انها لن تكون سلبية،
وحتى عندما كنت بالتكرار عبر صفيف،
يمكنك دائما تقريبا يقول الباحث غير الموقعة الأول، ولكن لم يكن لديك حقا.
الامور تسير على العمل الى حد كبير فقط كذلك.
حسنا. [همس] ما هو الوقت؟
آخر شيء كنت أرغب في إظهار - وسأفعل ذلك فقط سريعة حقا.
تعرف كيف قمنا # تعريف حتى نتمكن من تحديد # MAX إلى 5 أو شيء؟
دعونا لا تفعل MAX. # تعريف ملزمة إلى 200. هذا ما فعلناه من قبل.
أن يعرف ثابت، الذي هو مجرد الذهاب ليتم نسخها ولصقها
أينما كنا يحدث أن يكتب ملزمة.
>> حتى نتمكن من القيام به في الواقع أكثر مع تعريف #.
يمكننا تعريف # الوظائف.
انهم حقا لا وظائف، ولكننا سوف ندعو لهم وظائف.
مثال سيكون شيئا مثل MAX (س، ص) هو الذي يعرف بأنه (X <Y Y:؟ خ). حسنا.
لذلك يجب أن تعتاد على بناء جملة المشغل الثلاثي،
ولكن هو أقل من X Y؟ العودة Y، X العودة آخر.
حتى تستطيع أن ترى يمكنك ان تجعل هذه الوظيفة منفصلة،
ويمكن أن تكون وظيفة مثل BOOL MAX يأخذ 2 الحجج، والعودة هذه.
هذه هي واحدة من أكثرها شيوعا أرى به مثل هذا. نحن ندعو لهم وحدات الماكرو.
هذا هو الماكرو.
هذا هو مجرد بناء الجملة من أجل ذلك.
يمكنك كتابة ماكرو لتفعل ما تريد.
ترى في كثير من الأحيان وحدات الماكرو من أجل التصحيح printfs والاشياء.
ذلك نوع لل printf، وهناك ثوابت خاصة في مثل C تؤكد خط تسطير،
2 يؤكد خط تسطير،
وهناك أيضا أعتقد 2 يؤكد ظائفه. التي قد تكون عليه. شيء من هذا القبيل.
سيتم استبدال تلك الأشياء مع اسم الدالة
أو عدد السطر الذي كنت على.
في كثير من الأحيان، كنت أكتب هنا أن التصحيح printfs أسفل ثم أتمكن من الكتابة فقط
تصحيح وأنها سوف طباعة رقم السطر وظيفة أنني يحدث ليكون في
أنه واجه هذا البيان DEBUG.
ويمكنك أيضا طباعة أمور أخرى.
ذلك شيء واحد يجب أن احترس من هو إذا كنت يحدث لتعريف # DOUBLE_MAX
شيء من هذا القبيل كما 2 * 2 * Y و X.
ذلك لسبب كان، كنت يحدث لفعل ذلك كثيرا.
حتى جعله ماكرو.
يتم تقسيم هذا الواقع.
ويمكنني أن أسمي ذلك عن طريق القيام شيء من هذا القبيل DOUBLE_MAX (3، 6).
ذلك ما ينبغي أن تعاد؟
[طالب] 12.
نعم، ينبغي أن تعاد 12، وعاد 12.
يحصل استبدال 3 لX، ويحصل على استبدال 6 لY، ونعود 2 * 6، الذي هو 12.
الآن ماذا عن هذا؟ ماذا يجب أن تعاد؟
[طالب] 14. ومن الناحية المثالية >>، 14.
المسألة هي ان تعرف كيف تجزئة العمل، وتذكر انها نسخة حرفية ولصق
من كل شيء الى حد كبير، لذلك هذا ما سوف يتم تفسيره على أنه
هو 3 أقل من 1 زائد 6، 2 مرات (1) مع 6، 2 3 مرات.
>> لذلك لهذا السبب كنت دائما تقريبا التفاف كل شيء بين قوسين.
أي متغير كنت دائما تقريبا بين قوسين التفاف.
هناك حالات حيث لم يكن لديك ل، مثل وأنا أعلم أنني لست بحاجة إلى أن تفعل ذلك هنا
لأن أقل مما هو الى حد كبير دائما مجرد الذهاب للعمل،
على الرغم من أن قد لا يكون صحيحا حتى.
إذا كان هناك شيء مثير للسخرية مثل DOUBLE_MAX (1 == 2)،
ثم أن يحدث للحصول على استبدال مع 3 أقل من 1 يساوي يساوي 2،
وحتى ذلك الحين انها سوف تفعل 3 أقل من 1، لا أن 2 على قدم المساواة،
وهو ما لا نريده.
وذلك من أجل منع أي مشغل مشاكل الأسبقية،
التفاف دائما بين قوسين.
حسنا. وهذا كل شيء، 5:30.
إذا كان لديك أي أسئلة على pset، واسمحوا لنا أن نعرف.
ينبغي أن يكون متعة، والطبعة القراصنة أيضا أكثر واقعية
من طبعة القراصنة من العام الماضي، لذلك نحن نأمل أن الكثير من محاولة ذلك.
وكان العام الماضي الساحق للغاية.
>> [CS50.TV]