[সঙ্গীত বাজানো] 

ডেভিড জে Malan: ঠিক আছে. তাই তোমাকে স্বাগতম. এটি CS50, এবং সপ্তাহে তিন শেষে. 

সুতরাং, গত কয়েক সপ্তাহের মধ্যে প্রত্যাহার আমরা বেশ বিট খরচ করেছি হয়েছে সি উপর, প্রোগ্রামিং, সিনট্যাক্স সময়. আপনি যদি এখনও হন তাহলে এটা খুবই স্বাভাবিক হতে পারে, সমস্যা সেট 2 সঙ্গে সংগ্রাম প্রাচীর বিরুদ্ধে আপনার মাথা banging. এটা রহস্যপূর্ণ সুদর্শন ত্রুটির বার্তা এর এবং বাগ যে আপনি বেশ নিচে পেছনে তাড়া করতে পারবে না. কারণ, নিশ্চিত থাকা, যে মাত্র একটি কয়েক সপ্তাহ সময় আপনার উপর পিছনে তাকান করব সিজার ভালো জিনিস, এবং [? ভী genair,?] এমনকি crack, এবং আপনি এসেছ ঠিক কতদূর বুঝতে সময় অল্প সময়ের মধ্যে. যে কোনো সান্ত্বনা তাই যদি, এখন জন্য সেখানে স্তব্ধ হয়ে যেতে পারে. 

আজ যদিও,, আমরা এই পরিবর্তনকে শুরু জিনিষ উচ্চতর স্তর. এবং আমরা নিশ্চিতভাবে ধরে নিতে শুরু আপনাকে বলছি প্রোগ্রাম জানেন কিভাবে, বা সূত্রপাত কমপক্ষে যে আরাম স্তর. এবং আমরা কিভাবে আমরা করতে পারেন বিবেচনা করা শুরু করব আরো প্রোগ্রাম নকশা সম্পর্কে যান কার্যকরভাবে. আমরা optimizing যেতে পারবেন কিভাবে আমাদের আলগোরিদিম দক্ষতা, এবং সাধারণত সমাধান মজার সমস্যা. এবং, যে মঞ্জুর জন্য নিতে শুরু আমরা চেয়েছিলাম, আমরা কোনো আপ কোড পারে আমরা মাথায় আছে উদাহরণ. আজ তাই আমরা কীবোর্ড স্পর্শ করবেন না কোড কোন ফর্ম জন্য. এটা অনেক উচ্চ স্তরের হতে পারে, এবং করব পরিণামে, সমস্যা সমাধানে ওপর. 

সুতরাং যে পয়েন্ট পেতে, আমাকে উত্থাপন করা যাক নিম্নলিখিত সাত rectangles পিছনে সাত দরজা উপস্থাপন যা আভা আছে সংখ্যা, যার মধ্যে সংখ্যা হল 50. আমাকে এই নেভিগেশন এই প্রকল্পের চলুন শুরু করা যাক পাশাপাশি এখানে পর্দা. এবং আমরা একটি স্বেচ্ছাসেবক প্রয়োজন উত্থাপন আমার সামনে একটি সংখ্যা খুঁজে পেতে সাহায্য দেখতে এখানে ইন্টারনেট. গোলাপী, আপ উপর আসা. ঠিক আছে. আপনার নাম কি? 

Jennifer: [শ্রবণাতীত] 

ডেভিড জে Malan: দুঃখিত? 

Jennifer: জেনিফার. 

ডেভিড জে Malan: জেনিফার. ঠিক আছে, জেনিফার. দেখা হওয়ায় খুশী হলাম. উপর আসা. সুতরাং এই এখানে সাতটি দরজা আছে, এবং কি আমি, আপনি এখানে আমাদের জন্য কিছু করতে চাই আপনার সহপাঠীদের সব সামনে, আমাদের সংখ্যা, 50 এটি করা হয়. একটি সংখ্যা খুঁজে পেতে, আপনি উঁকি পিছনে করতে পারেন সহজভাবে লঘুপাত দ্বারা এই দরজা কোন দরজা এক, এবং এটা তার সংখ্যা প্রকাশ করা হবে. এবং এর দেখতে দিন কিভাবে আপনি দ্রুত আমাদের সংখ্যা, 50 জানতে পারেন. 

15. 16. 50. চমত্কারভাবে কাজ. ঠিক আছে. জেনিফার জন্য সাধুবাদ বৃত্তাকার. 

[সাধুবাদ] 

ঠিক আছে. সুতরাং আপনার কৌশল জন্য কি ছিল , 50 নম্বর খুঁজে পেতে? 

Jennifer: উম, আমি হয়তো যদি চিন্তা - [শ্রবণাতীত] 

ডেভিড জে Malan: ওহ. এটি একটি দ্বিতীয় দিন. সুতরাং আপনার কৌশল ছিল , 50 নম্বর খুঁজে পেতে? 

Jennifer: তাই আমি ঠিক সময়ে শুরু দেখতে শুরু কি প্রথম সংখ্যা হয়তো, যদি ছিল, এবং তারপর আমি চিন্তা তারা সাজানো করছি, আমি চালিয়ে যাব আপ উচ্চ লঘুপাত? 

ডেভিড জে Malan: ঠিক আছে. এবং আমরা খুঁজে পেয়েছি বলে মনে হচ্ছে মামলা হতে পারে. যদিও, ফিরে ছুলা স্তর আসুন অল্পমাত্র বিট, এবং আপনি যেতে চান এগিয়ে যান এবং অন্য দরজা প্রকাশ আপনার চয়ন করা হতে পারে? 

Jennifer: ওহ, দুর্মূল্য. 

ডেভিড জে Malan: আহ. 

Jennifer: তাই আমি ভাগ্যবান পেয়েছিলাম. 

ডেভিড জে Malan: তাই আপনি ভাগ্যবান পেয়েছিলাম. ঠিক আছে. তাই খারাপ না. কিন্তু যে একটি আকর্ষণীয় অন্তর্দৃষ্টি, ডান? , আপনি অধিকৃত, এবং আপনি পেতে থাকেন তাহলে প্রকৃতপক্ষে, একটি বিট আছে ভাগ্যবান. তবে আপনি যদি সংখ্যা ছিল অধিকৃত যে যদি সাজানো, আরও ভালো হতে পারে যে প্রভাবিত কিভাবে হিসেবে আপনার আচরণ? 

Jennifer: তারা অনুসারে সাজানো হয়েছে সুতরাং যদি আমি বৃহত্তম থেকে ক্ষুদ্রতম হয়তো চিন্তা. 

ডেভিড জে Malan: ঠিক আছে. 

Jennifer: অথবা এই শেষ পর্যন্ত যদি হচ্ছে ক্ষুদ্রতম তারপর বৃহত্তম, সত্যিই বড়. 

ডেভিড জে Malan: ঠিক আছে. সুতরাং ক্ষুদ্রতম থেকে বৃহত্তম, অথবা বৃহত্তম থেকে ক্ষুদ্রতম. কিন্তু আমার সম্পর্কে উত্থাপন করা যাক, আপনি অনুমান ছিল দুর্ভাগা অর্জিত, এবং মনে করা যে তারা , আসলে, সাজানো না হয়, কিভাবে অনেক যারা দরজা আপনি উঁকি ছিল থাকতে পারে যে সবচেয়ে খারাপ ক্ষেত্রে পিছনে? 

Jennifer: তাদের সব. 

ডেভিড জে Malan: তাদের সব. তাই এর সর্বজনীন যাক N হিসাবে. সেখানে 7 হতে হবে, কিন্তু এখানে আরো সাধারণত নেভিগেশন N এর দরজা আছে বলে এখানে পর্দা. তাই সবচেয়ে খারাপ ক্ষেত্রে, আপনি হবে 7 দরজা, অথবা N দরজা পিছনে তাকান. এবং তাই এই সত্যিই এটি একটি বিট হল, ভাগ্য আজ, কিন্তু এটি সত্যিই একটি রৈখিক এর প্রকারের অ্যালগরিদম, যদিও আপনি প্রায় কুঁদন ধরনের ছিল. যে ন্যায্য? 

Jennifer: হ্যাঁ. 

ডেভিড জে Malan: আচ্ছা, আমাকে দেখতে দিন যদি আপনার কৌশল পরিবর্তন আমি আমাদের চলে গেলে এখানে আমাদের দ্বিতীয় উদাহরণ 7 বিভিন্ন দরজা. একই সংখ্যা, কিন্তু এই সময় তারা সাজানো হয়. হতে যাচ্ছে এখানে আপনার কৌশল, কি আপনার মনের আউট করা করার চেষ্টা করছেন কি অন্য সংখ্যা ছিল - 

Jennifer: ঠিক আছে. 

ডেভিড জে Malan: - আগে? 

Jennifer: এর শুরু করা যাক প্রথম এক সঙ্গে. 

ডেভিড জে Malan: ঠিক আছে. প্রথম এক সঙ্গে শুরু. 4. এখন যেখানে আপনি যেতে যাচ্ছে, এবং কেন? 

Jennifer: 4 সত্যিই ছোট. তারা বাছাই হয়তো ক্ষুদ্রতম করছি তাই আপনি যদি বৃহত্তম, এটা করা উচিত - দু 'বার, এবং যে হতে. 

ডেভিড জে Malan: ঠিক আছে. চলুন শুরু করা যাক আপনি কি মনে করেন, যা দেখতে? 

Jennifer: গত এক করার চেষ্টা করুন. খুশী হলাম. 

ডেভিড জে Malan: অত্যন্ত সুন্দরভাবে সম্পন্ন. ঠিক আছে. 

[সাধুবাদ] 

ডেভিড জে Malan: ঠিক আছে. সুতরাং আপনি আসলে এই কাজ করছেন আপনি ভয়ঙ্করভাবে, কারণ খুব ভাল এটা করছে. যা আমাদের অক্ষম পাতা নির্দিষ্ট পয়েন্ট করা. সুতরাং এখানে ফিরে পাকানো চেষ্টা করা যাক. 

Jennifer: ঠিক আছে. 

ডেভিড জে Malan: অত্যন্ত ভাল তবু, সম্পন্ন. সুতরাং আপনি এ শুরু আপনি এটি পরে, আপনি 4 যে দেখেছি শেষ সরানো. তবে আপনি যদি ভাগ্যবান পেতে না ঠাউর , এবং সেখানে অনুমান 50 অন্য কোথাও ছিল না. কি আপনার তৃতীয় ধাপে হয়েছে? 

Jennifer: শুরুতে ফিরে যান. 

ডেভিড জে Malan: ফিরে যান শুরুতে. ঠিক আছে, তাই আপনি স্পর্শ করেছি হবে 8 যা ছিল এই দরজা. ঠিক আছে. সুতরাং যে 50 না. যেখানে আপনি পরের তাকিয়ে আছে কেন? 

Jennifer: আমি না করে থাকেন তাহলে তারা অনুসারে বাছাই করা হবে. 

ডেভিড জে Malan: সঠিক. হ্যাঁ, আপনি কি জানেন তারা অনুসারে সাজানো হয় - 

Jennifer: ওহ, হাঁ, জানেন. 

ডেভিড জে Malan: - কিন্তু আপনি না 50 এখনও ছিল যেখানে জানেন? 

Jennifer: শুধু বর্তা. 

ডেভিড জে Malan: ঠিক আছে. ঠিক আছে. বর্তা. ঠিক আছে, যে আমি সঙ্গে কাজ করতে পারেন. 

Jennifer: ঠিক আছে. 

ডেভিড জে Malan: এখন, আপনি ঠিক করছি বর্তা যাচ্ছে, কি আপনার অ্যালগরিদম মধ্যে ব্যাক devolving. 

Jennifer: রৈখিক -. 

ডেভিড জে Malan: এটা রৈখিক ধরনের. কিন্তু এখানে, সম্পর্কে উত্থাপন করা যাক আমার সম্পর্কে স্পট উপর করা. আমার সম্পর্কে পৃষ্ঠাটি রিফ্রেশ করা যাক. একই নম্বর, একই ব্যবস্থা, একই দরজা. কিন্তু যে প্রথম দিন ফিরে মনে আমরা একটি ফোন বই অর্ধবৃত্তাকার পার্শ্বচিত্রের মূর্তি, যখন ক্লাস অর্ধেক বাছাই, এবং কি ছিল সেখানে আমাদের কৌশল? 

Jennifer: মধ্যম থেকে আরম্ভ হয়. 

ডেভিড জে Malan: ঠিক আছে. সুতরাং মাঝখানে আরম্ভ হয়. সুতরাং আসুন এগিয়ে যান এবং যে অনুকরণ করা যাক. দ্বারা মধ্যম এ শুরু করুন যে দরজা প্রকাশক. সুতরাং সংখ্যা 16. তাই শক্তিশালী লোক কি হবে, যারা অর্ধেক ফোন বই অর্ধবৃত্তাকার পার্শ্বচিত্রের মূর্তি পরবর্তী অনুমান পেতে? 

Jennifer: এই অর্ধেক যান. 

ডেভিড জে Malan: কেন ডান? 

Jennifer: তারা যদি সাজানোর ক্ষুদ্রতম সম্পর্কে বৃহত্তম তাহলে 50 হতে হবে যে শেষে. 

ডেভিড জে Malan: গুড. সম্পূর্ণ যুক্তিসঙ্গত. সুতরাং একটি ফোন বইয়ের মত, আপনি যান ডান হিসেবে বাম বিরোধিতা, কিন্তু এখানে কী takeaway হয়. আপনি এখন দূরে নিক্ষেপ করা, বা বন্ধ বিছিন্ন করতে পারেন এই সমস্যা অর্ধেক, আপনি না যাব 7 দরজা দিয়ে, কিন্তু সত্যিই মাত্র 3 সঙ্গে. যার প্রায় অর্ধেক সমস্যা মাপ. ঠিক আছে. তাই এখন আপনি আছে কি আপনি ডান যেতে পরে কাজ? 

Jennifer: তাই 16, এখনও বেশ ছোট 50 আপেক্ষিক, তাই হয়তো আমি চেষ্টা করব এই এক, ভালো লেগেছে. 

ডেভিড জে Malan: ঠিক আছে. 42. ঠিক আছে, তাই এখন কি আপনার আপনি কহন প্রবৃত্তি? 

Jennifer: আমি দূরে নিক্ষেপ করতে পারেন এই এবং তারপর - 

ডেভিড জে Malan: ঠিক আছে. ভাল, আপনি দূরে নিক্ষেপ করতে পারেন সেখানে বাম অর্ধেক. 

Jennifer: - এই এক বাছাই. 

ডেভিড জে Malan: এবং অধিকার. 

Jennifer: হ্যাঁ. 

ডেভিড জে Malan: এটা কঠিন সুতরাং যদিও শুধুমাত্র আছে যখন, সম্ভবত দেখতে 7 দরজা, এখন,, আমার মনে হয় ধারাবাহিকতা আপনি এইমাত্র প্রয়োগ করা এলগরিদম. পূর্ববর্তী ক্ষেত্রে, আপনি কি মহান, যা ছিল পেতে ভাগ্যবান. কিন্তু আপনি একটি অনুসন্ধানমূলক ব্যবহার করেনি আমি বলতে হবে. আপনি আপনার সহজাত বুদ্ধির সাজানোর ব্যবহৃত, এবং এটা প্রশংসনীয় যদি এটা সাজানো বুদ্ধিমান শুরুতে ছোট, সম্ভবত, আমরা করেছি ডানে আরো যেতে পেয়েছিলাম. কিন্তু কিছু অর্থে, আপনি ভাগ্যবান পেয়েছিলাম হয়তো এই, সংখ্যা 100 কারণ এবং হয়ত 50 মাঝখানে বেশী ছিল. হয়তো 50 এখানে উপর, এমনকি ছিল. 

কিন্তু আপনি ভিন্ন একটি সামান্য কি এই সময় ছিল, আপনি একই জিনিস কি আবার এবং আবার. এবং আমি তর্ক করবে যে কি আপনি শুধু , যদ্যপি ফোন দ্বারা প্রভাবিত হয়নি বই যেমন অনেক কিছু আরো আলগোরিদিমিক, এবং আরো অনেক কিছু কম বিশেষ cased. অনেক কম স্বতঃস্ফূর্ত. তাই দিনের শেষে, কিভাবে হবে আপনি দক্ষতা বর্ণনা আপনি গিয়েছিলাম যেখানে প্রথম অ্যালগরিদম, বনাম, ডানে বামে এখানে দ্বিতীয় এলগরিদম? 

Jennifer: এই এক করা উচিত, যেমন, হয়তো সময় halve, বা এমনকি আরও, হাঁ. 

ডেভিড জে Malan: ঠিক আছে, এমনকি আরো. এর যে একটু কঠিন ধাক্কা চলুন শুরু করা যাক. সত্যিই কি, আমরা এই অবিরত যদি যুক্তিবিজ্ঞান, আমরা স্পষ্টভাবে halved এই দ্বিতীয় আলগোরিদিম সঙ্গে চলমান সময় অর্ধেক দূরে ছুঁড়ে সংখ্যা, কিন্তু আমরা পরের কি জেনিফার প্রকাশ যখন পুনরাবৃত্তির, দ্বিতীয় সংখ্যা? 

আমরা আবার দরজা সংখ্যা halved. এবং তারপর আমরা, যে পরে কি করে থাকেন সাথে খেলতে আরও দরজা আছে? আমরা আবার তাদের halve, এবং হবে এবং আবার, এবং আবার. এবং এই সব শুধু আপনাকে বলছি মত ছিল প্রথম সপ্তাহে স্থায়ী আপ আপনি বসা বর্গ, অর্ধেক, অর্ধেক আপনি, আপনি অর্ধেক বসা এক নির্জন, যতক্ষণ না বসা আত্মা স্থায়ী ছিল. এবং আমরা বলেন যে চলমান সময় যে, এটি গ্রহণ ধাপের সংখ্যা ছিল কি করার আছে? 

স্পিকার 1: [শ্রবণাতীত] 

ডেভিড জে Malan: সুতরাং লগ বেস N 2, বা আরও সহজভাবে, এন এর লগ ইন করুন. সুতরাং লগারিদমিক কিছু. এবং গ্রাফ একটি সরল রেখা ছিল না শুধু খারাপ থেকে আরও খারাপ পেয়েছিলাম যে, এটি ছিল না যে এই আকর্ষণীয় বক্ররেখা সময়ের এত খারাপ পেতে. তাই এর এই ধারণা উপর রাখা যাক. এর জেনিফার ধন্যবাদ চলুন শুরু করা যাক. আপ নেভিগেশন আসার জন্য ধন্যবাদ অনেক. এবং, এসইসি এক. কোন ডেস্ক আলো আজ, কিন্তু আমরা এবং CS50 চাপ বল আছে. 

Jennifer: Yay. 

ডেভিড জে Malan: ঠিক আছে, এখানে. Incurring করার জন্য আপনাকে ধন্যবাদ এখানে চাপ আপ. ঠিক আছে. সুতরাং আসুন দেখুন আমরা কি এখন করতে পারেন যদি একটি বিট আরো এই formalize. তাই আবার, আমরা কি কি ছিল আমরা কি হিসাবে মূলত একই জিনিস যে প্রথম সপ্তাহে. বরং শেষ আর মাত্র একটি রৈখিক সঙ্গে আমরা ফোটানো যা অ্যালগরিদম, পূর্বে এই সরল রেখা হিসাবে, যদ্দ্বারা, আমরা আরও একটি দরজা করা হলে পর্দা, তারপর জেনিফার হবে , সম্ভাব্য, চেহারা হয়েছে আরও একটি দরজা পিছনে. আমরা আরো দুটি দরজা করা হলে তিনি বলেন, থাকতে পারে আরো দুটি দরজা পিছনে তাকান. 

এবং তাই, এই রৈখিক ছিল মাপ মধ্যে সম্পর্ক X-অক্ষ,, বলতে উপর সমস্যা, এবং এটা লাগে সময় পরিমাণ Y নেভিগেশন সমাধান. কিন্তু আমি আপনি alluding ছিল ছবি তার আগে এই সবুজ লাইন ছিল. সবুজ ইচ্ছাকৃতভাবে, কারণ এটি শুধু ভাল অনুভূত. তত্ত্ব, আমরা এটি অ্যালগরিদম, যখন ফোন বই সঙ্গে, যখন আমরা তা আপনাকে বলছি একে অপরের বেড়ে চলেছে, এবং সঙ্গে দ্বিতীয় ক্ষেত্রে, যখন জেনিফার ঠিক এখানে এটা কি, এটা সাজানোর ছিল মৌলিকভাবে ভাল না. এটা শুধু দুবার দ্রুত না হওয়ার কারণে. এটি দ্রুত হিসাবে এমনকি চার বার ছিল না. এটা কি উপর সম্পূর্ণরূপে নির্ভরশীল ছিল ইনপুট মাপ হিসাবে, আর কত এটা শেষ পর্যন্ত গ্রহণ করার জন্য প্রয়োজনীয় পদক্ষেপ. 

এবং আমরা সব গ্রহণ তাই এই সহজ ধারণা ফোন বই সঙ্গে দেওয়া জন্য, একইভাবে প্রয়োগ করা যেতে পারে ভালো কিছু কথা. এবং এই আরো আকস্মিকভাবে হতে পারে আপনি প্রতাপ হিসাবে নামেও পরিচিত বিভক্ত করা এবং জেতা, কল্পনা. নেই আমরা কি অসদৃশ, অবশ্যই, ফোন বই সঙ্গে. 

কিন্তু pseudocode, রিকল, এই ছিল. তাই আমরা আবার এই না, কিন্তু প্রত্যাহার করা হবে না প্রথম সপ্তাহে, আমাদের সব দাঁড়িয়ে আপ এবং তারপর আপনি অর্ধেক অর্ধেক, শনি নিচে আপনি শনি নিচে, আপনি অর্ধেক শনি নিচে. যে অ্যালগরিদম মধ্যে বাস্তবায়িত ছিল যে একটি প্রতারণার পথ বিট, এটা আমার সম্পর্কে মাত্র এক, গণনা করা হয়নি মৌলিকভাবে, আরো দক্ষতার সঙ্গে. যে ক্ষেত্রে, আমি ওঠানামা ছিল দ্বিতীয় সম্পদ. বাছাই করা, একাধিক CPU, একাধিক ঘিলু, একাধিক স্মার্ট মানুষ রুমে আমাকে কিছু পেতে সাহায্য করা হয়েছে কিছু রৈখিক কিছু থেকে, লগারিদমিক কিছু সবুজ লাল. 

কিন্তু এই ক্ষেত্রে, জেনিফার একা করতে পারেন মৌলিকভাবে উপর উন্নতি তার প্রথম আলগোরিদিম কর্মক্ষমতা দ্বারা, আবার, শুধু একটু কঠিন চিন্তা. এবং এখন, এটি বাস্তবায়নের সময় আসে যখন এই জিনিস, figuring আউট আপনি যেমন লিখতে পারেন কি কোড লাইন আপনি আবার তাদের পুনরাবৃত্তি, এবং করতে পারেন আবার, এবং আবার, সাজানোর একটি looping ফ্যাশন. আপনি যাচ্ছেন না, কারণ জেনিফার মত বিলাসিতা, আপনি প্রথম করেনি শুধু, IFS আভা আছে বলে হুম, এই প্রথম সংখ্যা 4 হলে, আমার সম্পর্কে শেষ সব পথ তিড়িং লাফ দিন. যে সংখ্যা খুব বড় হলে, Ooh, আমার সম্পর্কে ইচ্ছামত ফিরে সরানো যাক দ্বিতীয় উপাদান. আপনি এটি একটি অনেক হতে যাচ্ছে পাবেন কঠিন formalize কি আমরা মানুষ অত্যন্ত যুক্তিসঙ্গত হিসেবে দেওয়া জন্য গ্রহণ করা হিউরিস্টিক, কিন্তু একটি কম্পিউটার শুধুমাত্র আপনি কি বলতে কি করতে যাচ্ছে. 

এখন এই খুব আকর্ষণীয় হয়েছে বিষয়. এই গ্রাফ ধরণের বাছাই বলতে কী বোঝানো হয় দৃশ্যত অভিভূত করা, কিন্তু বিজ্ঞপ্তি, যেখানে এই গ্রাফ অথবা সোজা লাইন? রৈখিক গ্রাফ কোথায় আমরা n কল? ওয়েল, এটা নিচ দিকে সাজানোর এর এই ছবি, ডান? আমরা সম্পন্ন করেছি আমরা সব ধরণের করেছি তাই X-অক্ষ এবং আউট জুম Y-অক্ষ কি একটা ধারনা পেতে চেষ্টা রেখাচিত্র অন্যান্য ধরনের মত চেহারা. 

এবং গাণিতিক এর সুনির্দিষ্ট এক্সপ্রেশন আজ তাই কোন ব্যাপার হবে না, অনেক, কিন্তু অনেক আছে যে বিজ্ঞপ্তি তুলনায় অনেক খারাপ যে আলগোরিদিম রৈখিক কিছু যে. প্রকৃতপক্ষে, ঘনাংকিত N প্রশংসনীয় খারাপ দেখায়. 2 N বেশ খারাপ দেখায়. ছক N প্রশংসনীয় খারাপ দেখায়. এবং আমরা দেখতে পাবেন কি যারা কিছু বাস্তবে আজ হতে পারে. এবং লগ N খারাপ হিসাবে মনে করেন, কিন্তু না N চেয়ে ভাল N লগ বেস 2. কিন্তু আপনি কি জানেন, এটি এমনকি হয়েছে আরো আশ্চর্যজনক যদি জেনিফার, বা আমরা যদি, প্রথম সপ্তাহ, সঙ্গে আসা পর্যন্ত ছিল N লগ লগ কিছু যে. 

তাই অন্য কথায়, এই পুরো আছে আপনি সম্ভাব্য সমাধান সম্পর্কে পরিসীমা সমস্যা, কিন্তু এখানে, বিজ্ঞপ্তি কি ঘটতে যাচ্ছে. এই রেখাচিত্র আমি জুম আউট, তখন কোন পরম হতে প্রমাণ যাচ্ছে এখন পর্দায় বেশী খারাপ? সুতরাং N ঘনাংকিত দেখতেও সুন্দর লাগে মুহূর্তে খারাপ. কিন্তু আমরা জুম আউট এবং আরও দেখুন যাচ্ছে যারা x এবং y-অক্ষ, পরিণামে আয়ত্ত? সুতরাং এটা আসলে আপনি যে 2 সক্রিয় আউট N, এবং আপনি শুধু এই জিনিসটা করতে পারেন কিছু বর্ধমান প্লাগিং সংখ্যা, এবং আপনি দেখতে পাবেন যে 2 N, সত্যিই, বড় অনেক দ্রুত পায়. আমরা সত্যিই, একটি 2 জুম আউট যদি N অ্যালগরিদম একেবারে sucks. আমি এই নিয়ে যাচ্ছে মানে জন্য সময় বেশ বিট কম্পিউটারের মাধ্যমে মত্তয়া আপনি. 

কিন্তু আপনি বিশেষ করে, সময়ের সঙ্গে দেখতে পাবেন ভবিষ্যতে সমস্যা সেট সঙ্গে এবং এমনকি চূড়ান্ত প্রকল্প, আপনার ডেটা সেট, সব ঠিক বৃহৎ পায়? এমনকি ফেসবুক প্রথম সংস্করণ, বন্ধুদের সংখ্যা এবং নিবন্ধিত ব্যবহারকারীর সংখ্যা, বড় পেয়েছিলাম আপনি ফোন তা বাছাই করতে পারেন , রৈখিক অনুসন্ধান সঙ্গে কিছু বাস্তবায়ন অথবা একটি খুব সহজ শ্রেণীবিভাজন আজ আমরা দেখতে পাবেন আলগোরিদিম. আপনি কঠিন চিন্তা শুরু এবং এই সমস্যা সম্পর্কে কঠিন. এবং সমস্যার জায়গা ধরনের মত ফেসবুক ও গুগল, মাইক্রোসফট, এবং কাজ অন্যদের এই ঠিক হল প্রশ্নের বড় তথ্য সাজানোর সাজানোর ক্রমবর্ধমান এই দিন. 

ঠিক আছে. যে দ্বিতীয় জেনিফার সাফল্য তাই অ্যালগরিদম, সত্যি, সে amazingly করেনি ভাল প্রথম সময়, কিন্তু let এর এটি ভাগ্য হিসেবে লিখুন যাতে আমরা এই বিন্দু করতে পারেন. দ্বিতীয় ক্ষেত্রে, তিনি একটি leveraged আবার পুনরাবৃত্তি এবং যে অ্যালগরিদম দেওয়া জন্য আবার, কিন্তু সে গ্রহণ একটি আমরা অনুমোদিত যে কয়েকটি স্বতঃসিদ্ধ তার, কিন্তু সে কিছু বিস্তারিত শোষিত সে আছে কি না দ্বিতীয় সময় প্রথমবার. কি যা ছিল? 

তালিকা অনুসারে সাজানো ছিল. তালিকা অনুসারে সাজানো ছিল তাই যত তাড়াতাড়ি আমরা জেনিফার করতে সক্ষম ছিল না দাবি করে যে মৌলিকভাবে ভাল. 7 দরজা, হ্যাঁ, যে আকর্ষণীয় নয় কিন্তু আমরা 7 মিলিয়ন দরজা করছি এটা অনুমান. N লগ স্পষ্টভাবে যাচ্ছে অনেক, অনেক সঞ্চালন দীর্ঘ রান দ্রুত. কিন্তু সে আছে ছিল দরজা তার জন্য সাজানো. এখন, আমি যে কাজ করার স্বাধীনতা গ্রহণ কম্পিউটারের পর্দায় অগ্রিম এখানে, কিন্তু যে জেনিফার অনুমান নিজেকে যে কি ছিল? ধরুন যে প্রশ্নের দরজা প্রতিনিধিত্ব একটি ডাটাবেসের মধ্যে তথ্য, অথবা ফেসবুক এর জন্য নিবন্ধভুক্ত লগ বন্ধুরা গেম, অথবা ইন্টারনেটে যে কোন ওয়েব পেজ যে বিভিন্ন ওয়েবসাইটের প্রয়োজন হতে পারে সূচক বা ওভার সন্ধানে. 

আপনি শুধুমাত্র একটি কাঁচা তথ্য ছিল যে ধরুন এবং সেট এটা আপনার বাকি ছিল, অথবা Jennifer যে শ্রেণীবিভাজন করতে হবে? যে পরিবর্তে, আমরা উত্তর প্রয়োজন যে প্রশ্ন, ভাল, কত সময় জেনিফার, অথবা এমনকি আমার সম্পর্কে নেওয়া হবে অগ্রিম ঐ সংখ্যার বাছাই তাই সে গ্রহণ করতে পারে যে? রাইট? সংশ্লেষ, অবশ্যই, কারণ এটি বাছাই সম্পর্কে বেশ কিছুদিনের লাগে যদি নরক আপনি বজায় রাখে যে যারা নম্বর, এত দ্রুত 50 মত একটি সংখ্যা খুঁজে পেতে পারেন, আর জেনিফার এর ক্ষেত্রে, যদি আমরা আরও মোট সময় পরিমাণ গরগর এটা আগাম কিছু বাছাই করে নেন? 

সুতরাং আমরা না পারেন, তাহলে এর দেখতে দিন এখানে ছবি আঁকা. আমি একটি আভা আরো চাপ আছে বল, যে সাহায্য করে যদি এখানে বরফ বিরতি. এবং যদি আপনি কিছু মনে করবেন না, আমরা সাত স্বেচ্ছাসেবক প্রয়োজন - ঠিক আছে, উপর. বাহ. সুতরাং আমরা ব্যয় করতে হবে না ডেস্ক আলো উপর, এটা মনে হচ্ছে. ঠিক আছে. সুতরাং কিভাবে সামনে দুটি আপনার সম্পর্কে. ফিরে দুটি বলছি কিভাবে সম্পর্কে আপনি. সুতরাং যে চার হয়. কিভাবে আপনার সামনে পাঁচ, ছয় এবং সাত. অধিকার আছে. আপনার বন্ধু, আপনি ইশারা এর তাই আপনি পুরস্কার পেতে. 

ঠিক আছে. উপর আসা. এবং কেন আমরা আপনার কাছে নেই বলছি ওভার এখানে আসা. আমি আপনার প্রতিটি একটি নম্বর দিতে যাচ্ছি. এবং এগিয়ে যান এবং নিজের ব্যবস্থা অনুরূপ কি আপনি পর্দায় দেখানো. 

[ভয়েসেস INTERPOSING] 

ডেভিড জে Malan: Oop, দুঃখিত. বাগ. ঠিক আছে. ওয়েল, আমরা এখানে যান. সংখ্যা পাঁচটি. ছয় নম্বরে. এক, দুই, তিন, চার, পাঁচ, ছয়, সাত. ওহ, এই বিশ্রী হয়. 

স্পিকার 2: আমি শুধু একটা পাবেন -. 

ডেভিড জে Malan: ভাল চুক্তি. ঠিক আছে. অংশগ্রহণের জন্য আপনাকে ধন্যবাদ. 

[সাধুবাদ] 

ঠিক আছে. ঠিক আছে. সুতরাং আমরা, চার, দুই, ছয় আছে এক, তিন, সাত, পাঁচ. আমরা সাত স্বেচ্ছাসেবকদের আছে তাই নিখুঁত এখানে প্রস্থ সমান যারা আমরা বাজানো করছি যে অ্যারের তার আগে না. এবং আমি কারণে সাত করতে বেছে নেওয়া হয়েছে যে হবে ঠিক অল্প সুবিধাজনক. এবং আমি প্রথম উত্থাপন করা যাচ্ছে যে আমরা এই সাত স্বেচ্ছাসেবকদের সাজাতে. আপনি প্রথম, চান তাহলে যদিও হ্যালো. বলতে এই একটি হতে যাচ্ছে দেখাও বিশ্রী কয়েক মিনিট. নিজের পরিচয় করিয়ে দিতে. 

GRACE: হাই, আমি গ্রেস না. আমি Leverett হাউস মধ্যে একটি বার্ষিক না. 

Branson: হাই. আমি Branson না. আমি জোড় একটি নবীন না. 

GABE: হাই. আমি Gabe না. আমি Cabot একটি জুনিয়র না. 

Neil: আমি নিল না. আমি ম্যাথুজ একটি নবীন না. 

Jason: আমি জেসন না. আমি Greenough একটি নবীন না. 

Mike: আমি মাইক না. আমি Grays একটি নবীন না. 

Jess: আমি জেস না. আমি Leverett একটি বার্ষিক না. 

ডেভিড জে Malan: চমৎকার. ঠিক আছে. ওয়েল, আমাদের সব থেকে আপনাকে ধন্যবাদ এ পর্যন্ত এখানে স্বেচ্ছাসেবকদের. এবং হাতের চ্যালেঞ্জ এখন যাচ্ছে এই ছেলেরা বাছাই করা হবে, কিন্তু তারপর থেকে আমরা একটু চিন্তা আছে চলুন কিভাবে দক্ষতার সঙ্গে আমরা আসলে ওপর হার্ড তাদের সাজানো. তাই এর প্রথম এই চেষ্টা করা যাক. আপনাকে বলছি একে অপরের সংখ্যা দেখতে পারেন শুধু কোণ কাছাকাছি স্থাপন করে. এগিয়ে যান এবং কয়েক সেকেন্ডের গ্রহণ করা, এবং সাজানোর ক্ষুদ্রতম থেকে নিজের ডান বৃহত্তম বামে. এ যান. 

ঠিক আছে. গুড. যে সত্যিই অভিশাপ দ্রুত ছিল. এখন এখানে কেউ এলগরিদম কি ছিল এই ছেলেরা প্রয়োগ যে? 

স্পিকার: 1 সর্বশ্রেষ্ঠ আপনি সবচেয়ে কম. 

ডেভিড জে Malan: ঠিক আছে. সর্বশ্রেষ্ঠ আপনি অন্তত সত্যিই সাজানোর উদ্দেশ্য, কিন্তু আমি যে কি না নিশ্চিত নই সত্যিই একটি অ্যালগরিদম. সর্বশ্রেষ্ঠ আপনি অন্তত বলুন না আমার সম্পর্কে কি করতে হবে তা ধাপে ধাপে. হ্যাঁ? 

স্পিকার 1: [শ্রবণাতীত] 

ডেভিড জে Malan: ঠিক আছে. আপনার চেয়ে একজন ব্যক্তির ছোট দেখতে তাই আপনি যদি আপনার নম্বর, তারপর সরানো তাদের অধিকার. সুতরাং যে এখন, আরো ভাবপূর্ণ হচ্ছে আরো একটি অ্যালগরিদম মত, কারণ আপনি তারপর যে, এই, যদি বলতে পারেন. তাই আমরা কিছু ধরনের আছে শর্তাধীন কনস্ট্রাক্ট. এবং এই ছেলেরা যে কয়েক কি করলো গুণ, আপনি কিছু একটি বিট সরানো কারণ একটি দূরত্ব. তাই সম্ভবতঃ কোন ধরণের ছিল তাদের হৃদয় ও মন জয় মধ্যে যাওয়া looping. 

কিন্তু যে formalize চেষ্টা করা যাক. আপনাকে বলছি ফিরে রিসেট করতে পারে যদি এই ব্যবস্থার নাম. আমরা এই একটি formalize না পারেন, চলুন শুরু করা যাক দেখুন বিট, এবং তারপর প্রশ্ন জিজ্ঞাসা, শুধু কিভাবে এই দক্ষ? অবশ্যই, আমরা ধীরে ধীরে এই কাজ করতে হলে, এটা হিসাবে ভাল যাচ্ছে একটি অ্যালগরিদম, কিন্তু এর দেখতে দিন আমরা করতে পারেন যদি সুনির্দিষ্ট পদক্ষেপ আমাদের আঙ্গুলের করা. 

তাই আপনি যদি দুটি বলছি চার ও দুটি. অথবা আপনি সঠিক অথবা ভুল করার জন্য? একথাও ঠিক যে ভুল. সুতরাং আমরা আনা. এখন আমি হঠা যাচ্ছি এখানে চার ছয় থেকে, বলে. আপনি সঠিক অথবা ভুল আছে? 

GABE: সঠিক. 

ডেভিড জে Malan: সঠিক. ছয় এবং এক? Nope. অদলবদল. সুতরাং যে দুটি অদলবদল আছে. ছয় এবং তিনটি? Nope. অদলবদল. ছয় এবং সাত? দেখতে ভালো. সাতটি এবং পাঁচটি? 

Jess: [শ্রবণাতীত] 

ডেভিড জে Malan: ঠিক আছে, অদলবদল. এবং সাজানো. ঠিক আছে. তাই সম্ভবত না, ঠিক আছে? যাতে আরও বেশি আছে চালু ছিল. কিন্তু প্রকৃতপক্ষে, এই ছেলেরা, এমনকি শুধু instinctively. চলন্ত রাখা. তারা শুধু একবার, থামাতে না তারা এক সমস্যা সংশোধন করা. তাই. প্রকৃতপক্ষে, আমি যাচ্ছি একই জিনিস করে. আমি আবার গুটিয়ে ফিরে বাছাই করতে যাচ্ছি এই সমস্যার শুরুতে, বা এই অ্যারে শুরুতে মানুষ, তাদের আহ্বান জানিয়ে শুরু করা যাক. 

এবং এখন কি করা উচিত আমার এলগরিদম দ্বিতীয় পাস করা? 

স্পিকার 1: একই জিনিস. 

ডেভিড জে Malan: একই জিনিস. এবং এই, আমি ঠিক আছে, পছন্দ করতে শুরু করছি? আপনি নিজে করছেন জানতে পারেন যত তাড়াতাড়ি একই জিনিস আবার এবং আবার, যে , আরো একটি অ্যালগরিদম মত হয়ে উঠছে এবং কম মানুষের সহজাত প্রবৃত্তি. 

সুতরাং এখন, আমরা এখানে আবার যেতে. দুই ও চার? নং চার এবং এক? আহ, কিছু প্রকৃতপক্ষে ছিল কাজ করতে হবে এখনও কাজ. এবং তিনটি? গুড. চার এবং ছয়? ছয় ও পাঁচটি? ছয় এবং সাত? ঠিক আছে, এখন, সম্পন্ন. ঠিক আছে, কোন. আমি ফিরে যেতে হবে. 

সুতরাং এখন, আবার, আমরা এই কাজ করছেন একটু বেশি ইচ্ছাকৃতভাবে. এবং এখন, শুধু একটা মস্তিষ্ক আছে এই অ্যালগরিদম নির্বাহ. এক CPU-র, যদি আপনি হবে. এবং সত্যি, যে একমাত্র সম্পদ এর আমরা এক্সেস আছে চলুন. এবং একবার আমরা একটি কীবোর্ড ফিরে যান এবং আমাদের এ C-এর মতো কিছু আছে বিক্রয়, আমরা কেবল একটি প্রোগ্রাম লেখা করছি একটি সময়ে এক জিনিস করতে পারেন. একটি মুহূর্ত আগে এইসব বলছি, যেহেতু, আমরা leveraged তাদের সমষ্টিগত brainpower আপনাকে বলছি শুন্য সপ্তাহ করেছিল ভালো লেগেছে. তাই এই কাজ রাখা যাক. 

দুই ও এক. দুই ও তিন. তিন এবং চার. চার এবং পাঁচ. পাঁচ ও ছয়. ছয় এবং সাত. সম্পন্ন? তাই আমি থাকি, কিন্তু আমার খেলা যাক শয়তান এর উকিল. না আমি, কম্পিউটার সাজানোর যারা শুধু এই অ্যারে মাধ্যমে পাস করেছে মানুষ, আমি কাজ করছি জানেন? 

স্পিকার: 1 নং 

ডেভিড জে Malan: সুতরাং কেন? আমি কি করার জন্য কি করতে হবে আমি কাজ করছি যে মীমাংসিত সিদ্ধান্তে আসা? সম্ভবত আরো এক পাস. রাইট? কারণ আমি যে আগের থেকে জানি সব পাস আমি একটি ভুল সংশোধন করা হয়. এবং যে মানে, হয়তো আছে এখনও অন্য ভুল আমি সঠিক যে প্রয়োজন. তাই আমি শুধুমাত্র গুটাতে দ্বারা নিশ্চিত করা, এবং করতে পারেন তারপর, চেক এক থেকে দুই, দুই এবং তিন, তিন এবং চার, চার এবং পাঁচ, পাঁচ এবং ছয়, ছয় এবং সাত. ঠিক আছে, এখন আমি কোন কাজ করেনি. 

আমি অবশ্যই আমি যে মনে করতে পারেন , একটি পরিবর্তনশীল ভালো কিছু সঙ্গে কাজ কোন int না. এটি অদলবদল কল, এবং অদলবদল আমি একবার 0 হলে এখানে পেতে, এবং তারপর, 0 শুরু আমি বর্তা মূঢ় হবে পিছনে আবার চেক, এবং আবার, এবং আবার, ঠিক আছে? আপনি কিছু আটকে কারণ অসীম লুপ ধরনের. 0 অদলবদল আছে, তাই যত তাড়াতাড়ি আমরা যে এই দাবি করতে পারেন অ্যালগরিদম, প্রকৃতপক্ষে সম্পূর্ণ. 

এখন, এর এই একটি নাম করা যাক. আমি শুধু যে আমরা উপস্থাপিত এলগরিদম বুদ্বুদ কিছু বলা হয় বাস্তবায়িত হয়নি অর্থে যেমন পরিচিত সাজানোর যে, বড় ধরনের যে সংখ্যা আপ উপরে বুদবুদ তাদের পথ, অথবা আপ সংখ্যার অ্যারের শেষ. কিন্তু এই অ্যালগরিদম কিভাবে দক্ষ ছিল? আমি শারীরিকভাবে কতগুলি পদক্ষেপ আছে কি এই বাছাই, উদাহরণস্বরূপ, গ্রহণ সাত মানুষের? 

চার থেকে পাঁচ? ঠিক আছে, খুব বেশী সংখ্যক পরিণামে হয় উত্তর হতে যাচ্ছে. এমনকি তারপর, নির্দিষ্ট সংখ্যা তাই আকর্ষণীয় নয়. এটা N হিসাবে সর্বজনীন চলুন শুরু করা যাক. আমি এখানে মানুষের আপ n, এবং তারা ছিল তাই আপনি যদি এ র্যান্ডম ক্রম, সাজানোর ছিল, যে আসল, যাতে শুরু. ওয়েল, কিভাবে অনেক ধাপ আছে আমি নি প্রথম পাস নিতে? এটা এক, দুই, তিন, চার, পাঁচ ছিল তাই ছয়, এবং তারা সাত জনের করছি, যে, ছয় সাত - এর, এন যাতে বিয়োগ এক প্রথমবার আলোচনা করা হয়েছে. 

এখন, কিভাবে অনেক ধাপ আছে আমি নি আমি rewound যখন নিতে? ভাল, আমরা আসলে দ্বিগুন হতে পারে যে যদি আমরা সত্যিই করতে চেয়েছিলেন, কিন্তু এখন জন্য, আমি আছি ঠিক, ঠিক আছে বলতে যাচ্ছি অন্য N বিয়োগ 1. সুতরাং N বিয়োগ 1 পেতে যাচ্ছে ট্র্যাক রাখা বিরক্তিকর, তাই আসুন শুধু সামান্য ধরপাকড়. সুতরাং 2n ধাপ. সুতরাং 14 ধাপ, দিতে বা নিতে. 

আমি কত বার গ্রহণ করা হয়নি একটি পদক্ষেপ পরবর্তী সময়ে? ওয়েল, এটা 3n এর. সত্যিই. এবং এখন, সবচেয়ে খারাপ ক্ষেত্রে, জন্য উদাহরণস্বরূপ, কতবার আমি হবে , পিছনে, পিছনে চলে গেছে সোয়াপিং, এই অ্যালগরিদম নির্বাহ প্রতিটি পাস নেভিগেশন মানুষ, প্রায়? এটা আসলে ঠিক আছে, ছক n এর? 

সবচেয়ে খারাপ ক্ষেত্রে, আপনি কি ধরনের কারণ intuitively এই বিষয়ে মনে করি না, এটা একটু সময় নিতে পারে, যদিও এখনো সদস্য না ডুবা সময় বিট সবচেয়ে খারাপ ক্ষেত্রে, কি হবে এই সাত জনের মধ্যে, যেমন তাকিয়ে আছে ব্যবস্থা শর্তাবলী তাদের সংখ্যা? সম্পূর্ণ পিছন দিকে, ডান? এবং শুধুমাত্র যে, ভান আপনার নাম আবার কি ছিল? 

Mike: মাইক. 

ডেভিড জে Malan: মাইক? ঠিক আছে, মাইক, আপনি আমার উপর যোগ দিতে পারেন এখানে মাত্র এক দ্বিতীয় জন্য? আসলে, কোন. দুঃখিত মাইক, let এর গুটিয়ে নেওয়া. আপনার নাম কি আবার? 

Neil: নিল. 

ডেভিড জে Malan: নিল. ঠিক আছে, নিল, আপনার সাথে আসা আমার সম্পর্কে, যদি আপনি আপত্তি করে না. তাই আমি ঠিক জন্য উত্থাপন করা যাচ্ছে না সরলতা, যে নিল তার মধ্যে এখন হয় সবচেয়ে খারাপ ক্ষেত্রে সম্ভব. কিন্তু আমি কিভাবে বাস্তবায়িত প্রত্যাহার আমার আলগোরিদিম. আমি তুলনা তুলনা তুলনা করছি উহু, তুলনা, তুলনা. এখন এই ছেলেরা বাইরে আদেশ, তাই আমি স্থির করা. তাই আপনাকে বলছি অদলবদল. কিন্তু কত অধিকতর, এখন বিবেচনা নিল যেতে আছে? এটা প্রায় n এর. আপনি কি জানেন, এটি আসলে n না. এটা পছন্দ, এন বিয়োগ 1, কিন্তু আমি পেয়ে করছি একটু এর উত্ত্যক্ত পালন ট্র্যাক সংখ্যা, তাই এটা n কল করা যাক. 

নিল সর্বাধিক এক ধাপ প্রতিটি চলে আসে তাই আপনি যদি সময়, এবং নিল এক ধাপ অগ্রসর, আমি সত্যিই এই ক্লান্তিকর পাস করতে হবে আগে পিছে, এই প্রায় হল এই করছেন, এন পদক্ষেপ, এন বার মোট, এটা আমাকে নিতে যাচ্ছে কারণ অনেক পদক্ষেপ নিল সমস্ত পেতে যে তিনি জন্যে যেখানে উপায়. বাকিদের একা যাক আপনাকে বলছি যদি সমস্ত সেইসাথে MIS শাসিত হয়. 

সুতরাং বুদ্বুদ সাজানোর N ছক কল করা যাক. এই অ্যালগরিদম চলমান সময়, এই অ্যালগরিদম কর্মক্ষমতা, এই অ্যালগরিদম দক্ষতা, আমরা শুধু আরো বর্ণনা হইবে N ছক সাধারণত হিসেবে. আমি কাজ করতে পারে, কারণ, যা সুন্দর আট জনের, নয় সঙ্গে একই উদাহরণ মানুষ, একটি মিলিয়ন মানুষ, এবং যে উত্তর পরিবর্তন করতে হবে না. 

আপনাকে বলছি কিছু মনে করবে না সুতরাং, যদি এর যাক আপনি শুরু যেখানে আপনি পুনরায় সেট করুন. যাক এর দুটি অন্যান্য পন্থা এবং চেষ্টা করুন আমরা মৌলিকভাবে না তা যাচাই করতে হলে এই বেশী ভালো. এই সময় তাই, আমি উত্থাপন করা যাচ্ছে না বিভিন্ন এলগরিদম কেমন. যে, শেষ সময় আমাদের খুব চালাক ছিল এবং আপনাকে বলছি অধিকার ছিল শুধু ধরনের অধিকার সহজাত pairwise সোয়াপিং. কিন্তু আমি সত্যিই এই পদ্ধতি চেয়েছিলেন সহজভাবে, এবং আমার লক্ষ্য সরানো হয় সামান্য সংখ্যার এই সব উপায়, এবং যে বড় সংখ্যার সমস্ত ধাক্কা ভাবে, কেন আমি শুধু যে করবেন না সবচেয়ে উপায় সম্ভব সাদাসিধা এবং দেখুন যদি আমি একটি কি বেশী ভালো করতে পারেন মোটামুটি জটিল এলগরিদম? 

সুতরাং এর দেখতে দিন. চার একটি খুবই ছোট সংখ্যা, তাই আমি আছি সেখানে মুহূর্তে আপনি চলে যাচ্ছে. Ooh, দুই নম্বর, এমনকি ভাল. সুতরাং আপনি ঠিক আগ বাড়া পারেন একটি মুহূর্ত জন্য? এটি বর্তমানে আমার ক্ষুদ্রতম সংখ্যাযুক্ত প্রার্থী, এবং আমি মনে রাখা যাচ্ছে না যে একটি পরিবর্তনশীল, চাই সঙ্গে. কিন্তু আমি পরীক্ষণ রাখা যাচ্ছে না. যার কেউ নেই সংখ্যা কম? ছয়, কোন. ওহ, আবার নিল আছে. 

তাই আমি আপনাকে ফেরত ধাক্কা যাচ্ছি সাজানোর ধারণার দিক থেকে না. নিল এগিয়ে আসতে হবে. এবং এখন, আমি আপনি ভেরিয়েবল ব্যবহার করছি যে ক্ষুদ্রতম যারা আছে ট্র্যাক রাখা নম্বর ধারণ করে আপডেট করা হয়েছে নিল এর অবস্থান. ওয়েল, এর দেখতে দিন. তিন, সাত, পাঁচ. ঠিক আছে, আমি নিল ক্ষুদ্রতম ছিল না. সহজ জিনিস কি আমার জন্য এখন কি আপনি? আমি আমার সময় নষ্ট করতে যাচ্ছি না বাম নিল এক স্পট সাড়া জাগানো. কেন আমি শুধু নিল করা না যেখানে তিনি জন্যে, যার যেখানে অবশ্যই হয়? 

শুরুতে সব পথ. নিল, তাই আমার সাথে আসুন. এবং যদি আপনার নাম আবার কি ছিল? 

GRACE: গ্রেস. 

ডেভিড জে Malan: গ্রেস. ঠিক আছে. গ্রেস তাই দুর্ভাগ্যবশত,, আপনি উপায় ধরনের. তাই কিভাবে আমরা এই সমস্যার সমাধান করবেন? রাইট? এই একটি অ্যারে যদি আছে, মাত্র সাত অবস্থানে. রব সঙ্গে, যে প্রত্যাহার, আমরা যে বিষয়ে কথা বললাম বয়সের প্রকাশক, এবং আমরা শুধুমাত্র একটি ছিল বয়সের সসীম সংখ্যা? এখানে একই ধারণা. আমরা কেবলমাত্র ints একটি সসীম সংখ্যা আছে. চারুতা আমাদের মধ্যে ধরনের হয় ভাবে, আমরা কিভাবে ঠিক করব? 

সবচেয়ে সহজ উপায়, মত হল গ্রেস, দুঃখিত. আপনি ওভার যেতে চলুন তাই আমরা রুম আছে করতে পারেন. এখন, আপনি হয়তো, এই চিন্তা যদি আমরা শুধু সমস্যা খারাপ. এবং হয়তো আমরা, কি কারণ যদি গ্রেস যথাস্থানে ছিল? কিন্তু আমরা সে কারণ, না জানি অন্যথায়, সে হয়েছে এগিয়ে দাঁড়িয়ে পরিবর্তে এই সময় নিল, ডান? আমরা ইতিমধ্যে তার নম্বর চেক আউট. 

ঠিক আছে. সুতরাং এখন, নিল যথাস্থানে, এবং আমি কিছুক্ষণের অপ্টিমাইজেশান করতে পারেন. পরবর্তী মিনিটের জন্য, আমি উপেক্ষা করা যাচ্ছে না যাতে না একসাথে নিল সব, তার সময় নষ্ট, বা ঘটনাক্রমে ভুল জায়গায় তাকে অদলবদল. সুতরাং এখন, কিভাবে আমি আগামী এটি না ক্ষুদ্রতম যে উপাদান? দুই. যদি, একটি প্রশংসনীয় ভাল সংখ্যা এর আপনি আগ বাড়া এবং করতে চান আমি আপনাকে স্মরণ করব. ছয়, কোন ভাল. চার, তিন, সাত, পাঁচ, কোন ভাল. সুতরাং আপনি আমাকে সরানো যাক আপনার সঠিক জায়গায়. এবং আমরা এই সময় ভাগ্যবান পেয়েছিলাম. 

এখন, আমি এই উপেক্ষা করা যাচ্ছে না দুই বলছি, এবং এখন আরো একটি কাজ এই মাধ্যমে পাস. ছয়, একটি খুবই ছোট সংখ্যা. এগিয়ে আসা. ওহ, দুঃখিত. গ্রেস এর নম্বর, ভাল তাই এগিয়ে নেভিগেশন পদক্ষেপ. চার. দুঃখিত, গ্রেস. আবার ফিরে যান. সংখ্যা তিনটি ভাল. সাত. পাঁচ. এবং এখন আপনার নাম আবার কি? 

Jason: জেসন. 

ডেভিড জে Malan: জেসন. সুতরাং জেসন এখন ক্ষুদ্রতম হয় উপাদান আমি নির্বাচন করেছেন. তিনি যেতে কোথায় যাচ্ছে? তাই যেখানে ছয় হয়. এবং যদি আপনার নাম আবার? 

GABE: Gabe. 

ডেভিড জে Malan: Gabe. Gabe উপায় আছে. করতে সবচেয়ে সহজ পদ্ধিতি হল জিনিস কি? এই দুটি বলছি অদলবদল ও অবিরত. তাই এখন দেখুন. যারা ক্ষুদ্রতম এর? চার. আমার সম্পর্কে ঠকাই শুধু ধরনের চলুন শুরু করা যাক. পাঁচ ক্ষুদ্রতম হতে যাচ্ছে. , তৃতীয় ধাপে যদি চান তাহলে আমি পরবর্তী খুঁজুন এগিয়ে, আমি কি কি আছে Gabe সঙ্গে এই না,? আবার অদলবদল. সুতরাং এখন, এখনও সামান্য ক্রম খুঁজে. আমি Gabe, তাই ছোট হতে পাওয়া আমি তাকে খুঁজে পপ আপনাকে বলছি ওভার সরানো. এবং কাজ. 

সুতরাং উত্তর একই. শেষ ফলাফল একই. এই দুই আলগোরিদিম যা ভাল? দ্বিতীয় এক, আমি শুনেছি. কেন? 

স্পিকার 3: এটা পদক্ষেপ [শ্রবণাতীত] n এর. 

ডেভিড জে Malan: এটা সর্বাধিক N ধাপ আছে. আকর্ষণীয়. সুতরাং এটা যদিও? সুতরাং কিভাবে আমি এটি নি ক্ষুদ্রতম উপাদান? কতগুলি পদক্ষেপ আমি নিতে হয়নি ক্ষুদ্রতম উপাদান খুঁজে? আমি সব পথ চেহারা ছিল শেষে, ডান? যে সবচেয়ে খারাপ ক্ষেত্রে, কি কারণ নিল এখানে উপর ছিল? তাই শুধু ক্ষুদ্রতম উপাদান খুঁজে পেতে আমার সম্পর্কে N ধাপ, বা N বিয়োগ 1 লাগে. কিন্তু, ঠিক আছে. সুতরাং নিল স্থির করা. , একটি মিনিট বা তাই আগে মনে রাখবেন. 

কিন্তু কিভাবে আমি পরবর্তী খুঁজে পেয়েছেন ক্ষুদ্রতম উপাদান? এটা N বিয়োগ 1, বা N বিয়োগ সত্যিই 2, এর ধাপের সংখ্যা থেকে. তাই ঠিক আছে. তাই আমি 2 বিয়োগ n হয়নি. ঠিক আছে. সুতরাং যে কিছুটা ভালো মনে. ঠিক আছে. পরবর্তী সময় কত আলোচনা নম্বর তিন খুঁজে পেতে হয়? সুতরাং N মাইনাস 4. সুতরাং এটি একটি কম কমে এর প্রতিটি পুনরাবৃত্তির উপর পইঠা. সুতরাং এই অধিকার, ভালো লাগছে না? শেষ সময় যদি এটা প্রায় N বার N ছিল এই সময় এটি N বিয়োগ 1, প্লাস N বিয়োগ এর 2, প্লাস N বিয়োগ 3, প্লাস N মাইনাস 4, বিন্দু, বিন্দু, বিন্দু. কিন্তু আপনি আপনার উচ্চ বিদ্যালয় থেকে প্রত্যাহার হলে পাঠ্যবই, একটু ঠকাই সূত্র আছে পিছে শীট, যদি আপনি সংখ্যার এই সিরিজের আপ যোগ করুন ধাপ মোট নম্বর কত আমি এখানে নিতে যে হতে যাচ্ছে? 

এই এক মত, এন বিয়োগ হয় 1, 2 দ্বারা বিভক্ত বার N,. তাই আমি টান করতে পারেন আমাকে যদি দেখতে দিন শুধু একটা মুহূর্ত জন্য এই পর্যন্ত. এবং আবার, আমি রাউন্ডইং ধরনের কিছু না সংখ্যা মাত্র, আমাদের জীবন সহজ রাখা কিন্তু আমি স্মরণ করছি, এটা যদি মত কিছু আমি তারপর, এন বিয়োগ 1 জিনিষ N বিয়োগ 2, তারপর N বিয়োগ 3, এটা প্রায় এর 2 ওভার ভালো কিছু, এবং যদি আমি এই আউট সংখ্যাবৃদ্ধি, যে আসলে N বর্গক্ষেত্র. যে খুব ভাল বোধ না. 2 ওভার N N বিয়োগ. 

কিন্তু এখানে জিনিস. কম্পিউটার বিজ্ঞান, সমস্যা যখন n যখন আকর্ষণীয় পেতে শুরু হয় বৃহত্ পায়. এবং N বৃহত্ পায়, যা এই মানগুলি সমস্ত আয়ত্ত করা যাচ্ছে অন্যদের? এটা ঠিক আছে, ছক N ধরনের? হ্যাঁ, 2 দ্বারা বিভাজক চমত্কার ভাল. কিন্তু আপনি কোটি কোটি বিষয়ে কথা বলছি, যদি তথ্য টুকরা, বা বহু ট্রিলিয়ান এর তথ্য টুকরা, ঠিক আছে, তাই আপনি দুইবার হিসাবে দ্রুত না. কিন্তু যারা সত্যিই যে বড় সংখ্যা যদি বজায় রাখে এই ফ্যাক্টর পায় কি যদি বড় এবং বড়. এবং নিশ্চয়, এটা বেশি করে তোলে এই লোক আর একটি পার্থক্য. আপনাকে বলছি ঠিক তাই, যদিও দ্বিতীয় অ্যালগরিদম, আমরা এটি ডাকবো নির্বাচন সাজানোর,, বাস্তব জগতে, একটি বিট দ্রুত সম্ভাব্য, আমি কারণ গ্রহণ কম এবং কম প্রতিটি সময় আলোচনা করা হয়েছে. 

এটা সত্যিই মৌলিকভাবে দ্রুত না. কারণ আমরা আসলে এই নিঃশেষিত হলে শেষে N বৃহৎ মূল্যবোধ, দিন, বড় যথেষ্ট N জন্য, এটা এখনও বেশ ধীর মনে যাচ্ছে. আচ্ছা, আমাকে এক নিতে যে সময়ে শেষ পাস. যে আমি কল করবে কি নির্বাচন সাজানোর. আপনাকে বলছি নিজের পুনরায় সেট করতে পারেন এক শেষ সময়? এবং এই শেষ ক্ষেত্রে, আমি যাচ্ছি কিছু উত্থাপন যাও সন্নিবেশ সাজানোর বলা হয়. সন্নিবেশ সাজানোর হচ্ছে, ধারণার দিক থেকে, একটি বিট বিভিন্ন. 

পিছনে যাওয়া এবং বদলে ক্ষুদ্রতম উপাদান নির্বাচন, আমি শুধু এই প্রতিটি মোকাবেলা করতে যাচ্ছে আমি তাদের সম্মুখীন, এবং সন্নিবেশ হিসেবে বলছি তাদের সঠিক জায়গা. তাই আমি ঠিক গ্রেস দিয়ে শুরু করতে যাচ্ছি এবং আমি সে সংখ্যা চার যে দেখুন. সংখ্যা চার কোথায় অন্তর্গত? আমি কিছু বাছাই শুরু করেন নি তাই গ্রেস অধিকার আছে থাকার পায়. আপনি পারে এবং এখন আমি দাবি করতে যাচ্ছি এই আপনার অধিকার একটি পদক্ষেপ গ্রহণ করা আমার অনুসারে সাজানো তালিকা, আমার মনে হয় unsorted অবশিষ্ট তালিকা. তাই এখন আমি, পরের এগিয়ে যাওয়া যাচ্ছে না এবং আপনার নাম কি আবার? 

Branson: Branson. 

ডেভিড জে Malan: Branson. সুতরাং Branson দুই নম্বর হল. তাই আমি আপনি নিতে যাচ্ছি একটি মুহূর্ত জন্য আউট. আর এখন আপনি যেখানে অন্তর্গত না এই অ্যারের মধ্যে? সুতরাং রেয়াতি অধিকার. তাই আবার, আমরা তৈরীর দয়ালু গ্রেস এখানে কাজ অনেক কাজ. আমরা আপনাকে কোথায় রাখা হয়? সুতরাং আমরা আপনাকে স্লাইড চলুন বামে, এবং সেখানে Branson সন্নিবেশ করুন. কিন্তু এখন আমি দাবী করে যে আপনি না করা হয়. কিন্তু বিজ্ঞপ্তি, আমি অতিরিক্ত স্থান ব্যবহার করছি না. এটা এখনও 2 উপাদান এর এখানে, এখানে ওভার 5. মোট অ্যারের আকার 7, তাই আমি আছি সমস্ত অধিকার, ঠকায় না? 

তাই এখন আমরা এখানে Gabe সঙ্গে আছে, ছয় নম্বরে, যেখানে আপনি অংশভুক্ত হয়? আপনি আবার ভাগ্যবান পেয়েছিলাম. তাই আপনি যদি সেখানে থাকার অধিকার পেতে. শুধু ডান সামান্য পদক্ষেপ গ্রহণ করা শুধু আপনি সাজানো করছি পরিষ্কার করতে. এবং এখন আমরা আবার নম্বর নিল আছে এক, আপনি কোথায় যেতে পারি? আমরা দেখতে যে শুরু করব কোথায় এবং এখন হয় যদিও প্রথম এই অ্যালগরিদম, এক নজরে, বেশ স্মার্ট মতানুযায়ী, ঘড়ি ঘটতে ওপর কি. আপনি এগিয়ে পইঠা পারে. 

আমরা কোথা থেকে নিল লাগাতে চান? তাই সম্ভবত এখানে, তাই কিভাবে আমরা সেখানে নিল পেতে পারি? এই ধাপে ধাপে করতে চলুন শুরু করা যাক. আপনি যেতে প্রয়োজন যেখানে Gabe,? হ্যাঁ, তাই, এক বড় পদক্ষেপ গ্রহণ করা বা দুটি অর্ধ ধাপগুলি ওইখানে এক ধাপ. আপনি যেতে যেখানে গ্রেস,? গুড. অন্য ধাপ তাই. এবং পরিশেষে, Branson? আরেকটি পদক্ষেপ. এবং এখন আমরা জায়গা করে নিল লাগাতে পারেন. 

সুতরাং এখন, এই যুক্তিবিজ্ঞান অবিরত. আমরা নিল নাড়াচাড়া করা হয় না যদিও ওভার, এবং ওভার, এবং উপর তাকে রাখা তিনি সবচেয়ে খারাপ ক্ষেত্রে, যায় যেখানে, আমরা সম্মুখীন হতে পারে পরবর্তী সংখ্যা পারা সংখ্যা, বলে, একটি সংখ্যা ছিল শূন্য তারপর, আমরা সব নামান চলুন এই ছেলেরা. একটি সংখ্যা, নেতিবাচক আছে ধরুন এক, তাহলে আমরা নামান আছে এই ছেলেরা সব. সুতরাং আমরা সত্যিই আলোকসম্পাতের শুধু ধরনের করছি আমরা যেমন যে কাছাকাছি সমস্যা, থেকে ব্যয় হস্তান্তর নির্বাচন প্রক্রিয়া তাই সন্নিবেশ আপনাকে বলছি ঠিক ছিল যে এই ধরনের প্রক্রিয়া, প্রায় N বিয়োগ কিছু সরাতে ধাপের সংখ্যা. এবং ধাপের যে সংখ্যা শুধুমাত্র যাচ্ছে আমি নম্বর নির্বাচন করুন যেমন বৃদ্ধি, আমি আপনাকে বলছি ঠেলাঠেলি রাখতে হলে ফিরে, এবং ফিরে, এবং ফিরে. 

তাই দু: খিত জিনিস এখন এই সব হয় আলগোরিদিম ছক n হয়. চলুন শুরু করা যাক এগিয়ে যান এবং ধন্যবাদ এই আপনি বলছি, এবং এই একটি বিট মনশ্চক্ষুতে ভিন্নভাবে. খুব ভাল কাজ করেছেন. 

[সাধুবাদ] 

ঠিক আছে. এখন পর্যন্ত আপনি যান. জন্য ধন্যবাদ - 

Branson: [শ্রবণাতীত] নম্বর রাখা. 

ডেভিড জে Malan: না, আপনি হতে পারে সেইসাথে সংখ্যা রাখা. ঠিক আছে. চমত্কারভাবে কাজ. ঠিক আছে. সুতরাং আমরা এখন থেকে সংক্ষেপ করা না করা হলে এর দেখতে দিন আরো দ্রুত, এবং আরো আকর্ষনীয় করে, ঠিক ঠিক কি ঘটেছে এখানে নিম্নরূপ. আমি এগিয়ে যেতে চলেছি এবং ফায়ারফক্স টান আপ. আমরা এই বিক্ষোভের করে দেব কোর্স এর ওয়েবসাইট. জাভা কাজ করার জন্য একটি বিট বিরক্তিকর কোন কোন ব্রাউজারে এই দিন. আপনি বাড়িতে এই সাথে খেলতে না যদি তাই হয়, আপনি ফায়ারফক্স ব্যবহার করার প্রয়োজন হতে পারে বুঝতে পারছি এটা কাজ পেতে. এবং কি আমি এই সঙ্গে কাজ করতে যাচ্ছি বিক্ষোভের নিম্নোক্ত. 

নীচে, আমি আভা আছে একটি শুরু এবং একটি সহ মেনু অপশন, বোতাম বন্ধ. উপরন্তু, একটি সরাইয়া হিসাবে, একটি আছে বলে মনে হয় এই প্রোগ্রামের মধ্যে বাগ, আপনি যদ্দ্বারা আসলে শুরু দেখতে বা বন্ধ করতে পারবে না আপনি যদি কমান্ড বা অল্টার রাখা বোতাম যদি না প্লাস এবং জুম মধ্যে, যা অদ্ভুতভাবে আপনি আরও বোতাম দেখায়. আপনি খেলা যদি তাই শুধু FYI এই বাড়িতে. এখন আমি শুধু একটা শুরু ক্লিক করুন যাচ্ছি মুহূর্ত, একটি বিলম্ব উল্লিখিত হওয়ার পরে, এখানে 200 মিলিসেকেন্ড, ঠিক মত তাই আমরা কি দেখতে পারেন. 

তাই আমি এই একটি কল্পনা যে দাবি প্রথম অ্যালগরিদম এই ছেলেরা বুদ্বুদ সাজানোর, যদ্দ্বারা কি, আমরা মানুষের জোড়া জিনিস আনা. এই কল্পনা কী অন্তর্দৃষ্টি যে বার এর উচ্চতা নম্বর মাপ প্রতিনিধিত্ব করে. লম্বা দণ্ড সুতরাং, বড় সংখ্যা. খাটো বার, ছোট সংখ্যা. আপনি লক্ষ্য এবং যদি, আমরা এর মাধ্যমে চলুন এই অ্যালগরিদম প্রথম পুনরাবৃত্তির, যাতে বড় ও ছোট সংখ্যা সোয়াপিং ছোট সংখ্যা প্রথম এবং আসে বড় সংখ্যা ডানে যায়. 

এবং যত তাড়াতাড়ি আমরা অ্যারের শেষে পেতে সাত তুলনায় আরো অনেক সংখ্যা, আমরা শুরুতে ফিরে যান যাচ্ছে. এবং এই কহা. দূরে বাম, যে সামান্য লোক যাচ্ছে পাশ থেকে swap, এবং এই প্রক্রিয়া পুনরাবৃত্তি. এখন এই কল্পনা দ্রুত পায় বিরক্তিকর, তাই আমাকে এগিয়ে যান এবং বন্ধ করা যাক এটা অনেক বিলম্ব কিছু পরিবর্তন দ্রুত ঠিক এখন জন্য একটি অনুভূতি পেতে এই অ্যালগরিদম. 

আমি কি এটা sped করেছি, যদিও এই হল কেনা, আমার প্রসেসর আপগ্রেড করার মত একটি নতুন কম্পিউটার. আমি মৌলিকভাবে পরিবর্তীত হয়নি আমার অ্যালগরিদম, কিন্তু আপনি সত্যিই আরো দেখতে পারেন পরিষ্কারভাবে মানুষের সঙ্গে আর, যে বড় সংখ্যা, শীর্ষ পর্যন্ত সাড়া জাগানো হয় এবং ছোট সংখ্যা সাড়া জাগানো হয় নিচে নীচে. এবং এখন এই জিনিস এখানে সাজানো. এবং একটি সরাইয়া হিসাবে, স্কোয়ার মধ্যে আছে, সেখানে শুধু কিছু হিসাবরক্ষণ , আপনি কত তুলনা গণনা সাহায্য বা কিভাবে অনেক অদলবদল আছে আসলে সম্পন্ন হয়েছে. 

ওয়েল, এর এক চেষ্টা করুন অন্যদের আমরা দেখেছি. আমাকে এখানে বুদ্বুদ সাজানোর উপর ক্লিক করা যাক, এবং আমার সম্পর্কে চয়ন করতে দিন, এবং এই পুরো ওয়েব পৃষ্ঠা একটু বগী. এর ঝুঁকি গ্রহণ করা যাক এবং আবার এটি চালানোর জন্য. সেখানে আমরা যেতে. তাই নির্বাচন সাজানোর করতে আসুন. আমি জানি না কেন মেনু ওইখানে প্রদর্শিত হবে. ঠিক এ এর ​​জুম চলুন শুরু করা যাক বাগ, 50 এই পরিবর্তন. আহ, আসলে কি আসুন অনেক দ্রুত যে. পাঁচ মিলিসেকেন্ড বা তাই, এবং শুরু. 

তাই এই নির্বাচন ধরণের. তাই আবার, আমরা কি চিন্তা এখানে মানুষের সাথে করেছিল. আমরা অ্যারে মাধ্যমে গিয়েছিলাম এবং নির্বাচিত আবার ক্ষুদ্রতম উপাদান, এবং আবার, এবং আবার. এখন আমি এখনও বেশ খারাপ ছিল দাবি করে যে. এটা এখনও ছক n ছিল, দিতে বা নিতে কিন্তু এটা একটি বিট, বাস্তব জগতে ছিল, দ্রুত, আমি প্রকৃতপক্ষে গ্রহণ কারণ প্রতিটি সময় পদক্ষেপগুলি সামান্য কম. কিন্তু আমরা শুধু কি কথা বলছি? এখানে হয়তো 40 বা তাই বার? আমরা 40 মিলিয়ন কথা বলা হয় না. সুতরাং এটি সম্পূর্ণই আমার সম্পর্কে পরিষ্কার না যে প্রকৃতপক্ষে একটি উল্লেখযোগ্য বৃদ্ধি ছিল. 

আমাকে এখন ফিরে যান এবং আমাদের পরিবর্তন করা যাক নির্বাচন হয়েছিল তৃতীয় অ্যালগরিদম, সন্নিবেশ সাজানোর. এবং এখন এটা সত্যিই বগী কারণ মেনু সত্যিই আছে নিচে হবে না. তাই এখন আমরা এখানে ফিরে স্ক্রল করব এবং এই অ্যালগরিদম শুরু. উচ্চ চিৎকার করা, আরম্ভ এবং বন্ধ. তাই এই এক ধরনের একটি চমত্কার প্যাটার্ন আছে এটি করার জন্য, যদ্দ্বারা আমরা আবার করছি মানুষের সন্নিবেশ, বা এই ক্ষেত্রে, বার মধ্যে তাদের যথাযথ অবস্থান. এবং এটি আগে থেকেই সম্পন্ন আমি প্রায় প্রমাণিত. কিন্তু এই এক, খুব, তত্ত্ব, এখনও ছক n করা হয়. 

সুতরাং আমরা সংক্ষেপ করা না করা হলে এর দেখতে দিন এই হিসাবে অনুসরণ করে. আমি এগিয়ে যেতে এবং মাত্র দিতে যাচ্ছি কথা বলা একটি সাধারণ পথ আমাদের সাজানোর এই জিনিস সম্পর্কে, আমাকে পরিচয় করিয়ে দিতে এখানে স্বরলিপি শুধু একটি বিট. আপনি কিছু বড় বলা দেখতে চলেছেন হে এটা আক্ষরিক কারণ একটি বড় মন্ত্রণালয় এবং এই একটি কম্পিউটার যে একটি উপায় বিজ্ঞানী বা এমনকি ব্যবহার করে একটি গণিতজ্ঞ চলমান সময় বর্ণনা কিছু অ্যালগরিদম. এটি আসলে কতগুলি পদক্ষেপ নিতে? 

এখন আমি সঙ্গে নিজেকে অস্বস্তি যাচ্ছি এখানে শুধু একটা মুহূর্ত আমার হস্তাক্ষর. কিন্তু আমাকে এগিয়ে যান এবং যে বলা যাক এই এখানে ওভার বড় হে হতে হবে. এবং আমার অন্য একটি পরিচয় করিয়ে দিতে প্রতীক, একটি রাজধানী ওমেগা. ওমেগা, বিপরীত হতে যাচ্ছে মূলত, বড় হে যেহেতু বড় মন্ত্রণালয় এর মানে, সবচেয়ে খারাপ ক্ষেত্রে, কত সময় কিছু অ্যালগরিদম মধ্যে, সময় নিতে পারে N পদ, ওমেগা যাচ্ছে কত সময় এটা প্রতাপ হতে সেরা ক্ষেত্রে গ্রহণ করা. এবং আমরা দ্বারা অর্থ কি দেখতে পাবেন শুধু একটা মুহূর্ত সেরা কেস. 

তাই কিছু সহজ শুরু করা যাক. আমার সম্পর্কে একটি রৈখিক খোঁজো দিয়ে শুরু করা যাক. তাই বাছাই না. আমরা এই রৈখিক খোঁজো ডাকবো. এবং এখন, একটু করতে এই টেবিলের খুঁজে. এবং এখন, রৈখিক খোঁজো ক্ষেত্রে, সবচেয়ে খারাপ ক্ষেত্রে, কত পদক্ষেপ এটি একটি এটি সম্পর্কে নিতে যাচ্ছে নির্বিচারে পছন্দ সংখ্যা? এবং N মোট দরজা আছে বা N মোট সংখ্যা. লক. কতগুলি পদক্ষেপ আমি করতে যাচ্ছি একটি অ্যারের মধ্যে সংখ্যা 50 এটি গ্রহণ N দরজা? এবং কেন? এটা সব হতে পারে, কারণ শেষ সম্মুখের ওভার উপায়. জেনিফার সম্মুখীন এত মত, সংখ্যা 50, তাই সব পথ ছিল সবচেয়ে খারাপ ক্ষেত্রে রৈখিক অনুসন্ধান N বড় হে, আমরা বলবো না. 

কি শ্রেষ্ঠ কেস সম্বন্ধে, আপনি সত্যিই ভাগ্যবান পেতে তাহলে কি হবে? এটা ঠিক, এক পদক্ষেপ নিতে যাচ্ছে ধাপ বা একটি ধ্রুবক সংখ্যা. সুতরাং আমরা 1 হিসাবে বর্ণনা করব. তাই এই চমত্কার ভাল. এখন আমরা কিছু কি যদি বাইনারি অনুসন্ধান চান? সবচেয়ে খারাপ তাই বাইনারি অনুসন্ধান, , মামলা গ্রহণ কত সময়? 

[ভয়েসেস INTERPOSING] 

ডেভিড জে Malan: তাই আসলে, আমি কয়েক জায়গায় এটা শুনেছি. সুতরাং এটা আসলে,, এন লগ ইন দিতে বা নিতে আমরা অর্ধেক তালিকা ভাগ কারণ আবার, এবং আবার, এবং আবার, আমরা পারবেন শেষ পর্যন্ত, এটি, মান, এটা এখানেই আছে, কিন্তু একটি ধরা আছে. আমরা আছে কি ধৃষ্টতা বাইনারি অনুসন্ধান জন্য মঞ্জুর জন্য নিতে? এটা সাজানো হবে. এটি সাজানো না, আপনি জিনিস ভাগ করতে পারেন মধ্যে আবার এবং আবার অর্ধেক, এবং আপনি বামে যেতে পারেন, এবং আপনি সঠিক যেতে পারেন, এবং আপনি বাম এবং ডান যেতে পারেন, কিন্তু আপনি উপাদান যদি এটি করা যাচ্ছে না তালিকা অনুসারে বাছাই করা হয় না, কারণ, যদি আপনি এটি মিস্ হতে পারে. আপনার অনুসন্ধানমূলক কারণ, বাম যাচ্ছে জন্য বা ডান এটা যদি ত্রুটিপূর্ণ করা যাচ্ছে না প্রকৃতপক্ষে সাজানো না. সুতরাং একটি লুকানো খরচ ধরণের আছে ভালো কিছু ব্যবহার করে. 

এখন, আমাদের শ্রেণীবিভাজন ঢোকা যাক আলগোরিদিম অনুসন্ধান করা না - উহু, আসলে এর এই ফাঁকা মধ্যে যান. সেরা ক্ষেত্রে বাইনারি অনুসন্ধান? এটা ঠিক হতে হবে যদি এটি 1 খুব অ্যারের মাঝখানে, বা ফোন বই এর মাঝখানে. এখনই বুদ্বুদ সাজানোর করতে আসুন. তাই আবার, এখন আমরা প্রবেশ করছি বিশৃঙ্খলভাবে, না অনুসন্ধান. 

সবচেয়ে খারাপ ক্ষেত্রে, কত পদক্ষেপ করেনি আমরা দাবি বুদ্বুদ সাজানোর নিতে যাচ্ছে? N ছক. তাই আমি যে আঁকা যাচ্ছি. Ooh, আমার হস্তাক্ষর এমনকি খারাপ দেখায় এটা যে বড় অভিক্ষিপ্ত যখন. ঠিক আছে. সুতরাং যে স্কয়ার্ড n এর. এবং বুদ্বুদ সাজানোর সেরা ক্ষেত্রে, কতগুলি পদক্ষেপ নিতে যাচ্ছে? 1, আমার শোনা. 

স্পিকার: 1 N. 

ডেভিড জে Malan: N, আমি শুনেছি. 

স্পিকার: 1 2. 

ডেভিড জে Malan: 2, আমি শুনতে. আমি 3 শুনতে পারি? ঠিক আছে. তাই আমি N, 2, 1 শোনা করেছি, কিন্তু বাছাই এর যাক যারা পৃথক্ অন্তত প্রথম পরামর্শ, 1. এটা, কারণ একটি খারাপ প্রবৃত্তি না ধরনের এখানে একটি প্যাটার্ন অনুসরণ করে. কিন্তু এটি শুধুমাত্র কিভাবে 1 ধাপ, লাগে যদি বিশ্বের আমি দাবি করতে পারে যে তালিকা আমি শুধুমাত্র অনুমোদিত করছি, কারণ অনুসারে সাজানো হয় 1 ধাপ, কিভাবে অনেক উপাদান গ্রহণ আমি আসলে নিশ্চিত হতে চেক করতে পারেন? ওয়েল, শুধু 1, যা N আছে মানে বিয়োগ 1 উপাদানের যে আউট হতে পারে আদেশ, এবং আমি ঠিক পরে বিশ্বাসের উপর যাচ্ছি 1 উপাদান এ খুঁজছেন যে বিষয় অনুসারে সাজানো হয়. এখানে সঠিক না 1 তাই. সুতরাং ন্যূনতমরূপে, কত আমি তাকান আছে না? 

[ভয়েসেস INTERPOSING] 

সত্যিই N বিয়োগ 1, বা,: ডেভিড জে Malan N, আমি প্রতি তাকান প্রয়োজন কারণ নিশ্চিত করুন যে উপাদান এটা যাতে বাইরে না. কিন্তু আবার, আমরা তরঙ্গ আমাদের বাছাই করব ছোট সংখ্যার এ হাত এবং N বড় পায়, তারা করছি, অনুমান যাহাই হউক না কেন নীরস. সুতরাং যে বুদ্বুদ সাজানোর. এবং এখন, এই দুই কাজ করতে দিন. তারপর নির্বাচন সাজানোর, এবং আমরা করব সন্নিবেশ সাজানোর কাজ. এবং তারপর আমরা আপনার গাট্টা হবে অনেক কিছু সঙ্গে হৃদয় ও মন জয় এই সব চেয়ে ভাল. ঠিক আছে. 

চলমান লক কি নির্বাচন সাজানোর সময়? 

স্পিকার 4: N ছক. 

ডেভিড জে Malan: R বর্গক্ষেত্র, আমি শ্রবণ করছি. কিন্তু কেন N intuitively, ছক? 

স্পিকার 4: আমরা ঠিক তা না. 

ডেভিড জে Malan: আমরা ঠিক তা না. ঠিক আছে. উত্তর ভালো. কিন্তু intuitively, কেন নির্বাচন সাজানোর N ছক? আমরা কি আছে নি আবার এবং আবার? আমরা, এর মাধ্যমে স্ক্যান রাখা ছিল আপনি ক্ষুদ্রতম, আপনি ক্ষুদ্রতম, আপনি ক্ষুদ্রতম হয়. এবং মঞ্জুর, আমরা N নিতে সক্ষম ছিল ধাপ, তারপর N তারপর বিয়োগ 1, N বিয়োগ 2. কিন্তু আপনি কি ধরনের যারা সমস্ত পর্যন্ত যোগ করতে হলে, বা আমি এখনো যোগ করেনি করেছি যে বিশ্বাসের উপর তা গ্রহণ আগাম তাদের আপ, আমরা N প্রায় পাবেন কিছু ছোট সংখ্যা বিয়োগ ছক. তাই আমি এই N ছক কল যাচ্ছে না. কিন্তু সেরা নির্বাচন সাজানোর সঙ্গে ক্ষেত্রে, এটি কতগুলি পদক্ষেপ আমার সম্পর্কে নিতে যাচ্ছে? 

স্পিকার 5: [শ্রবণাতীত] 

ডেভিড জে Malan: এটা দুর্ভাগ্যবশত এর এখনও N ছক, ডান? আমি ক্ষুদ্রতম নির্বাচন করছি কারণ উপাদান, এবং আমরা এখানে সাত জনের ছিল আমি শুধু জানি, একবার আমি খুব পেতে শেষে, আমি ক্ষুদ্রতম খুঁজে পেয়েছি নম্বর, যেখানেই তিনি বা তিনি তৈরি হতে পারে. কিন্তু কিভাবে আমি পরবর্তী এটি করবেন না ক্ষুদ্রতম সংখ্যা? আমি অন্য পাস করতে হবে. তাই সবচেয়ে ভাল ক্ষেত্রে, কি নির্বাচন সাজানোর ইনপুট? এটি ইতিমধ্যে একটি বাছাই তালিকা, এক নম্বর, এর দুই নম্বর, সংখ্যা তিন, চার নম্বর. কিন্তু আমি একটি কম্পিউটার না. আমি শুধুমাত্র এক তাকান পারেন একটি সময়ে জিনিস. একটি পদক্ষেপ নিতে আমি বাছাই করতে পারবেন না ফিরে একটি মানবিক এবং বলতে চাই, ooh, এটি সঠিক দেখাচ্ছে. 

আমি শুধুমাত্র শুদ্ধি adjudicate করতে পারেন নির্বাচন করে নির্বাচন সাজানোর ক্ষুদ্রতম সংখ্যা. কিন্তু আমি এক নম্বর প্রথম এটি এমনকি যদি, আমি অন্য কিছু না জানেন, তাহলে আমি কি না এমন সংখ্যা,, আমি আমি একটি অ্যারের হস্তান্তর করা হয়েছে করেছি জানি যে যা পিছনে দরজা বা একটি সংকলন সংখ্যা, আমি যে জানি একমাত্র উপায় ক্ষুদ্রতম ছিল? আমি এখানে সব পথ পেতে এবং বুঝতে হলে, অভিশাপ, একটি সত্যিই সবচেয়ে ছোট ছিল. 

কিন্তু কিভাবে আমি তারপর নির্ধারণ করবেন দুই পাশে ছোট হয়? একই অদক্ষতা করে আবার এবং আবার. তাই পরিশেষে, সন্নিবেশ সাজানোর সঙ্গে, কিভাবে, সবচেয়ে খারাপ ক্ষেত্রে, আমরা এটি সঞ্চালিত হবে কি বলেছেন? এটা খুবই ছক n করা হয়. এবং কিভাবে সম্পর্কে ভাল ক্ষেত্রে সঙ্গে? আমরা একটি cliffhanger যে ছেড়ে দেব. আমরা যে ফাঁকা পরবর্তী সময়ে পূরণ করব কিন্তু প্রথম আমার সম্পর্কে উত্থাপন করা যাক যে আমরা মৌলিকভাবে তুলনায় ভালো করতে এই সব, সব ঠিক? 

তাই নিজের জন্য মনে করি কি সন্নিবেশ সাজানোর হতে যাচ্ছে. ভাল, যে খুব নাটকীয় ছিল না আমি শুধুমাত্র এক কারণ যে পরিবর্তন দেখেছি. বাহ. ঠিক আছে. তাই আমরা এখানে একটি কিছুটা আছে বিভিন্ন বিক্ষোভের. আমি এখানে জুম, তাহলে আপনি যে দেখতে পাবেন বাম আমরা, বুদ্বুদ সাজান আছে আমরা নির্বাচন সাজান আছে মাঝখানে, এবং এ পর্যন্ত ঠিক আছে, আমরা কিছু আছে আমরা কোনো দিকে তাকিয়ে নি সাজান একত্রীকরণ বলা হয়. কিন্তু আমরা করেছি কি বিবেচনা আজ পর্যন্ত এখানে করছেন. জেনিফার প্রথম মঞ্চে আসেন, আমরা সংখ্যার অ্যারের মাধ্যমে গিয়েছিলাম আবার, এবং আবার, রৈখিক অনুসন্ধান সঙ্গে, এবং আমরা বড় হে, রৈখিক চলমান সময় পেয়েছেন N এর, তাই কথা বলতে. 

এখন আমরা প্রথম সপ্তাহে যখন বিবেচনা ক্লাস, আমরা বিভক্ত করা এবং জেতা ছিল যখন, এবং আমরা ফোন বই, বিচ্ছিন্নকরণ ছিল এবং জেনিফার, এবং আমরা সম্মিলিতভাবে আপনি যা ছিল leveraged যে কী অন্তর্দৃষ্টি, দ্বারা আবার এবং আবার নিজেকে পুনরাবৃত্তি একরকম দূরে নিক্ষেপ দূরে নিক্ষেপ দূরে নিক্ষেপ সমস্যা অর্ধেক, অথবা সাধারণত, অর্ধেক একটি সমস্যা বিভাজক, এবং তারপর ছোট টুকরা চিকিত্সা ধারণার দিক থেকে সমতুল্য সমস্যা অন্যান্য, আমরা একরকম করেনি মৌলিকভাবে ভাল. কিন্তু বুদবুদ সাজানোর সঙ্গে সঙ্গে নির্বাচন সাজানোর, সন্নিবেশ সাজানোর সঙ্গে, আমরা করেছি হতে পারে জেনিফার যে কোন অর্ন্তদৃষ্টি. আমরা প্রায় কাছাকাছি ঠিক ফিরে walked এবং ঘোষণা সমগ্র বার গুচ্ছ, এবং আমরা tweaked জিনিষ একটি সামান্য বিট, সোয়াপিং এই, যাতে হয়তো সন্নিবেশ বা নির্বাচন. কিন্তু দিনের শেষে, আমি অনেক করেনি বিশ্রী হাঁটা পিছে. আমরা সত্যিই লিভারেজ কিছু না জেনিফার মত স্মার্ট বিভাজক মত করেনি এবং অতিক্রমকারী. 

সুতরাং সাজানোর একত্রীকরণ, বিপরীতে দ্বারা, যা আমরা পরের সপ্তাহ পর্যন্ত দেখতে পাবেন না, এটা যাচ্ছে লিভারেজ বিভাজক দ্বারা যে কী ধারণা ইনপুট, এবং তারপর halving, এবং তারপর halving, এবং তারপর halving. এবং যে লুপ প্রতিটি পুনরাবৃত্তির উপর, বাম অর্ধেক বাছাই, এবং ডান অর্ধেক, বাম অর্ধেক বাম অর্ধেক, তারপর তারপর বাম এবং ডান অর্ধেক, বাম ডান অর্ধেক অর্ধেক, এবং ডান অর্ধেক ডান অর্ধেক. এবং আবার এবং আবার পুনরায়. 

সুতরাং আপনি দৃশ্যত এই দেখুন, কিন্তু এই করব আগামী সপ্তাহে আমাদের অ্যাওয়েট্সওয়াচমেন কি. এবং সাধারণভাবে, যখন আমরা একটু চিন্তা কোনো ধরনের সমস্যা একটু কঠিন. আমরা বাম ছক N, N করেছেন মাঝখানে ছক, এবং N ডান N লগ ইন করুন. সুতরাং আপনার আসল cliffhanger আছে. আমরা সোমবার আপনি দেখতে পাবেন. 

[সাধুবাদ]