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

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

শ্রোতা: মেরি বেথ. স্পিকার: মেরি বেথ, উপর আসা. আমাকে আপনার জন্য এখানে মাইক্রোফোন পেতে. দেখা হওয়ায় খুশী হলাম. 

শ্রোতা: চমৎকার দেখা. স্পিকার: ঠিক আছে, তাই আমি এখানে নীল বই একটি Z মাধ্যমে, এবং আমি যে সাজা করা যাচ্ছে না আমি, ছাত্র এক এবং তারা কিছুটা এলোমেলোভাবে মধ্যে আসছে তিন ঘন্টা পরীক্ষা ব্লক শেষে, তাই তারা কিছু শেষ হওয়া পর্যন্ত করছেন এই মত আধা র্যান্ডম ক্রম. এখন শুধু একটি মুহূর্ত আপনার কাজ হবে এই তারা আসলে কিভাবে be-- থেকে শেষে পরিণত বর্গ, সম্ভবত. আপনার কাজ এখন বেশ, হতে যাচ্ছে কেবল আমাদের জন্য এই নীল বই বাছাই থেকে জেড মাধ্যমে 

শ্রোতা: ওহ, এই হল চিরকালের নিতে যাচ্ছে. 

স্পিকার: আমরা পর্যবেক্ষণ করবেন আপনি এই কাজ করতে, কোন চাপ. শ্রোতা: না, কোনো চাপ বা কিছু. 

স্পিকার: এবং মজার জন্য, এর একটি টাইমার আপ করা যাক. 

শ্রোতা: তাই অনেক মজা, তাই অনেক মজা. 

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

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

শ্রোতা: হ্যাঁ. 

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

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

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

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

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

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

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

এখন বিন্দু, বিন্দু, তরঙ্গ ডট ধরনের এটি juicier বিস্তারিত কিছু এ হাত, কিন্তু এর এগিয়ে যান এবং সহজ করে. আপনি উচ্চ থেকে প্রত্যাহার করা হলে আপনি স্কুল, উন্মুক্তভাবে, অনেক ছিল ছিল গণিত বই একটু Cheat শীট প্রচ্ছদের বা আপনি দেখিয়েছেন যে ফিরে কভার মত কি সিরিজ summations শেষ পর্যন্ত এই পর্যন্ত এখনো যোগ করেনি. সাধারণ ক্ষেত্রে, আপনি একটি আছে n মত পরিবর্তনশীল, এবং প্রকৃতপক্ষে এই এক, আপনি দিকে তাকিয়ে যদি আপনার পুরানো স্কুল গণিত বই, আপনি আসলে এই যে দেখতে হবে এখানে এই যোগফল পর্যন্ত যোগ করে এন এন বার বিয়োগ 1 2 দ্বারা বিভক্ত. তাই এখন জন্য আমাকে শুধু চুক্তির শর্ত দেওয়া এই, তাই বিশ্বাসের একটি লীপ উপর সত্য, যে এই অঙ্কের কি আপ, এবং আমরা পারা একটি সাধারণ ক্ষেত্রে প্রমাণ. কিন্তু এখন এর এই প্রসারিত করা যাক. তাই এর এই গুন, তাই যে n ছক, বিয়োগ এন, 2 দ্বারা বিভক্ত. যে, সত্যিই n বর্গ বিয়োগ N 2 উপর, 2 দ্বারা বিভক্ত, তাই যে সব সুন্দর এবং আকর্ষণীয়. কিন্তু আমরা কি ঘটবে যদি এখন প্লাগ ইন একটি মান? আমি আট আছে কি না ধরুন মানুষ, কিন্তু একটি মিলিয়ন বলে. এবং একটি মিলিয়ন মাত্র কারণ এটি একটি চমত্কার বড় সংখ্যা এর মধ্যে প্লাগ এবং দেখুন সেখানে কি ঘটছে. আমি যে সূত্র মধ্যে একটি মিলিয়ন চলা তাই আমি একটি মিলিয়ন বর্গ পেতে যাচ্ছি 2 দ্বারা বিভক্ত, বিয়োগ একটি মিলিয়ন, 2 দ্বারা বিভক্ত. এখন কি যে সমান যাচ্ছে? তাই 500 কোটি, বিয়োগ 500,000. এবং আমি আসলে কি যদি যে গণিত আউট, যে মানে যে একটি মিলিয়ন বাছাই বুদ্বুদ সাজানোর সঙ্গে মানুষ আমার 499.999.500.000 নিতে পারে শেষ ধাপ বা তুলনা, আমরা শুধু extrapolating করছি. 

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

[ভিডিও প্লেব্যাক] 

-Senator, আপনি এখানে আছেন গুগল এ, এবং আমি চাই অধ্যক্ষতা মনে একটি কাজের ইন্টারভিউ হিসাবে. এখন, এটা পাওয়া কঠিন সভাপতি হিসেবে একটি কাজ, এবং আপনি এখন rigors মাধ্যমে চলুন. এটি গুগল এ একটি কাজ পেতে এছাড়াও কঠিন. আমরা প্রশ্ন আছে, এবং আমরা আমাদের প্রার্থী, প্রশ্ন, জিজ্ঞাসা এবং এই এক ল্যারি Schwimmer থেকে. What-- আপনি যদি না আমি মনে করি নিশ্চয়ই মজা, এটা ঠিক এখানে. সবচেয়ে কার্যকর উপায় কি একটি মিলিয়ন 32 বিট ইন্টিজার সাজাতে? 

-Well-- 

দুঃখিত -I'm, maybe-- 

না, না, কোন. আমি বুদ্বুদ সাজানোর মনে যেতে ভুল পথ হতে হবে. 

-Come উপর, যারা তাকে এই ডটকমকে বলেন,? আমি কম্পিউটার দেখতে না আপনার পটভূমিতে বিজ্ঞান. 

-We've সেখানে আমাদের চর পেয়েছিলাম. 

-ওকে, এর একটি বিভিন্ন জিজ্ঞাসা করা যাক ইন্টারভিউ প্রশ্ন. 

[END টি ভিডিও প্লেব্যাক] 

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

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

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

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

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

কি আমি বদলে পরিবর্তন গল্প, না বুদ্বুদ সাজানোর সম্পর্কে করা কিন্তু এই সর্বোচ্চ সীমা সম্পর্কে. আপনি একটি অ্যালগরিদম মনে করতে পারেন আমরা ইতিমধ্যে দিকে তাকিয়ে করেছি যে যার সর্বোচ্চ সীমা, সর্বোচ্চ সময় বা অপারেশন পরিমাপ, বেষ্টিত করা হয়েছে করা হবে n দ্বারা, একটি রৈখিক ফাংশন, না বাঁকা যে একটি দ্বিঘাত এক? একটি অ্যালগরিদম কি যে সবসময় কোন সময় লাগে n ধাপ, বা মত চেয়ে 2n ধাপ, বা 3N পদক্ষেপ? হ্যাঁ? 

শ্রোতা: খোঁজা একটি তালিকা বৃহত্তম সংখ্যা? 

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

তাই যদি আমি যে প্রস্তাবিত কি এই বিশ্বের আলগোরিদিম আছে যে একটি চলমান সময় আছে লগ n বড় হে দ্বারা বেষ্টিত, এন লগ ইন করুন? যেখানে আমরা আগে এই দেখা যায়? হ্যাঁ? 

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

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

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

শ্রোতা: দুটি সংখ্যার যোগ করুন. স্পিকার:, দুই নম্বর যোগ করুন 2 প্লাস 2 সম্পন্ন, 4 সমান. সুতরাং যে কাজ করতে পারে, কি কি? কিভাবে আরো বাস্তব দুনিয়া সম্পর্কে, হাঁ? 

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

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

শ্রোতা: বাবল সাজানোর? 

স্পিকার: বাবল সাজান লাগে আপনি ন্যূনতমরূপে n ধাপ, কেন? কেন হল? কেন যে শুরু আপনি আসতে হবে intuitively,, এটা আছে, এমনকি যদি ঠিক না এখনো? হ্যাঁ? 

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

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

তাই এখন আমরা একটি উপায় আছে একটি নিম্ন সীমার বর্ণনা, এবং ধ্রুব সময় সম্পর্কে কি? কি কম আছে যে একটি অ্যালগরিদম এক তার চলমান সময় বেঁধে? 1 ধাপ, 2 ধাপ, 10 ধাপ, কিন্তু ধ্রুব n এর স্বাধীন, ইনপুট আকার? হাঁ, ফিরে. 

শ্রোতা: printf? স্পিকার: কি যে? শ্রোতা: printf? স্পিকার: printf. নিশ্চিত, ঠিক আছে. সুতরাং এটি একটি পদক্ষেপ নির্দিষ্ট সংখ্যা লাগে. এবং আমি এখন যে now-- উচিত আমরা সি কোড যে বিষয়ে কথা বলছি এবং না ভূত, কিছু বলতে চাই, printf সঙ্গে, আমরা সতর্কতা অবলম্বন পেতে শুরু করা উচিত. Printf, লাগবে ইনপুট, এটি একটি স্ট্রিং, এবং স্ট্রিং টেকনিক্যালি দৈর্ঘ্য আছে. আমরা এখন বাছাই করতে চান আপনি, আপনি কিছু মনে করবেন না, টেকনিক্যালি আমরা যে printf তর্ক হতে পারে একটি পরিবর্তনশীল দৈর্ঘ্য ইনপুট নিতে, এবং নিশ্চয় এটি আরও সময় নিতে পারে সময়, এই দীর্ঘ একটি স্ট্রিং প্রিন্ট এই দীর্ঘ তুলনায়. 

তাই আমরা ঠিক কি বিবেচনা বাছাই এবং উদাহরণ অনুসন্ধান? ফোন মাইক স্মিথ সম্পর্কে কি বই, বা আরো সাধারণভাবে বাইনারি অনুসন্ধান? সেরা ক্ষেত্রে, কি ঘটতে পারে? আমি Bam, ফোন বই খুলুন এবং মাইক স্মিথ এর সংখ্যা আছে. আমি সরাসরি তাকে কল করতে পারেন. 

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

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

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

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

শ্রোতা: n ছক. স্পিকার: n স্কয়ার্ড. কেন? 

শ্রোতা: আপনি আছে [শ্রবণাতীত] সংজ্ঞায়িত. 

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

আমি নেন যেখানে সন্নিবেশ সাজানোর সম্পর্কে কি আমি দেওয়া হয়, এবং তারপর আমি তাকে plopped যারা বা তার সঠিক জায়গায়? তারপর আমি দ্বিতীয় ব্যক্তি রইল সঠিক জায়গায় তাকে বা তার plopped. তারপর পরের ব্যক্তি, plopped তাকে বা তার সঠিক জায়গায়. এই বিজ্ঞপ্তি রৈখিক, তাই কথা বলতে. আমি নই, একটি সরল রেখা আছি পিছে যাচ্ছে না, আমি সত্যিই ফিরে খুঁজছেন, কিন্তু করেছি আমি তাকে সন্নিবেশ যখন কি ঘটছে শুরুতে তার মধ্যে বা তালিকা আমরা সোমবার করেনি? কি ঘটছে? হ্যাঁ? শ্রোতা: [শ্রবণাতীত]. স্পিকার: হ্যাঁ, যে ঠিক আছে, ধরা ছিল? আপনি থেকে প্রত্যাহার করা হতে পারে আপনার সহপাঠী, তারা যদি কোনো আন্দোলনের সঙ্গে তৈরি হয়েছে তাদের ফুট, যে একটি অপারেশন ছিল. যদি তাই সেখানে তিন জনের এখানে ছিল এবং নতুন ব্যক্তি, আছে উপায় উপর belonged ভালো একটি দীর্ঘ মঞ্চে, নিশ্চিত, তিনি ঠিক সে খুব শেষ যেতে পারে. কিন্তু আমরা একটি সম্পর্কে চিন্তা করছি কম্পিউটার এবং মেমরি একটি অ্যারের, এই মানুষ যাচ্ছে উপর পরিহার আছে যে ব্যক্তি জন্য জায়গা. তাই যে এন 1 বিয়োগ shufflings, এন বিয়োগ 2 shufflings, এন বিয়োগ 3 shufflings শুধু ধরনের হয় না আমার সামনে, আমার পিছনে ঘটছে আগে হিসাবে, কিছু অর্থে. এখন একটি সরাইয়া হিসাবে, এবং আপনি অনলাইন দেখা হতে পারে আপনার সম্পর্কে খোঁচা কাছাকাছি শুরু অসুস্থ, তাই বিভিন্ন বেশী আছে তাদের আছে, কিছু অন্যদের চেয়ে ভাল. প্রকৃতপক্ষে, bogosort এক যে সন্ধান করার মজা ধরনের. Bogosort একটি সেট লাগে সংখ্যা বা কার্ড একটি ডেক বলে, এলোমেলোভাবে তাদের shuffles, এবং চেক তারা সাজানো করছি. এবং যদি না, আবার আছে. এবং যদি না, আবার আছে. যদি না হয়, আবার এটা আছে. অবিশ্বাস্যভাবে মূঢ়. 

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

শ্রোতা: পিটার. 

স্পিকার: কি যে? 

শ্রোতা: পিটার. স্পিকার: পিটার, ডেভিড, আপনি দেখা করতে চমৎকার. ঠিক আছে, আমরা এখানে, পিটার আছে আপনি যদি এখানে টেবিল সম্মুখের আসতে চান. এবং আপনার নাম কি? 

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

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

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

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

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

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

[সাধুবাদ] 

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

কিন্তু আমি ধরনের আমি ফোন করবো কি ব্যবহার এখানে একটি খুব পুনরাবৃত্ত পদ্ধতি, বিশেষ বিজ্ঞপ্তি লাইন 8 এবং লাইন 11. যারা একটি পুনরাবৃত্ত প্রমাণ পদ্ধতির একটা looping পদ্ধতি, যে ঠিক কারণ তারা রাজি করানো আচরণ. যারা লাইন উভয় যেতে বলে লাইন তিনটি, এবং আপনি পারেন ধরনের যে মনে আপনার একটি লুপ হচ্ছে মনের চোখ. এটা পইঠা আপ ফিরে যেতে বলছে আপনি এর তিনটি এবং পুনরাবৃত্তি, আবার, এবং আবার, এবং আবার. 

কিন্তু আমরা একটি কী ধারণা কি লিভারেজ যদি এখানে আমরা না শেষ সময় যে, এবং লাইন 8 সহজতর করা এবং লাইন 11 এবং তাদের প্রতিবেশীদের শুধু এই, হলুদ হিসাবে. এটা মৌলিকভাবে কমা না খুব pseudocode হয়, কিন্তু এটি মৌলিকভাবে পরিবর্তন আমার আলগোরিদিম প্রকৃতি. আমি কি এখন বলছে ধাপ 7, ধাপে 10, মাইক জন্য অনুসন্ধান করা হয় সঠিক একই ভাবে, কিন্তু ঠিক বাম অর্ধেক বা ডান অর্ধেক. 

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

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

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

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

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

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

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

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

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

শ্রোতা: ড্যারেন. 

স্পিকার: ড্যান. ড্যান ধাপ ধাপ এগিয়ে আছে. 

শ্রোতা: ড্যারেন. স্পিকার: ড্যারেন সম্পন্ন. আপনি ড্যারেন বা ড্যান বলে? 

শ্রোতা: ড্যারেন. 

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

শ্রোতা: লুক. 

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

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

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

শ্রোতা: আদ্রিয়ানো. 

স্পিকার: আদ্রিয়ানো. আদ্রিয়ানো এখন অনুসারে সাজানো হয়. এবং আপনার নাম কি? 

শ্রোতা: অ্যালেক্স. 

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

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

শ্রোতা: ওমর. 

স্পিকার: ওমর, কাজ, এগিয়ে. বাম অর্ধেক বাছাই করা হয়. এবং আপনার নাম কি? 

শ্রোতা: ক্রিস. 

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

শ্রোতা: মারিনা. 

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

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

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

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

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

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

শ্রোতা: এন করুন. 

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

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

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

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