[সঙ্গীত বাজাচ্ছি] 

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

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

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

ALAN Estrada: উম. ডেভিড জে MALAN: আক্ষরিক অর্ধেক সমস্যা বিচ্ছিন্নকরণ. 

ALAN Estrada: ওহ. মিমি. খুব ভালো. 

ডেভিড জে MALAN: ঠিক আছে. ভাল. তোমাকে ধন্যবাদ. ALAN Estrada: খুব ভালো. ঠিক আছে. 

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

[হাস্যময়] 

ALAN Estrada: হ্যাঁ, আমি কি মনে 

ডেভিড জে MALAN: কি বিভাগে আমরা হয়? ALAN Estrada: মাফলার, তাই. 

ডেভিড জে MALAN: ঠিক আছে. কিন্তু মাইক স্মিথ যাচ্ছে মাফলার পরে হতে. So-- 

[হাস্যময়] 

ঠিক আছে. ALAN Estrada: কোথায় আমরা খুঁজছি হয়? ডেভিড জে MALAN: মাইক স্মিথ. ALAN Estrada: মাইক স্মিথ. ডেভিড জে MALAN: এখন, আমরা অস্ত্রোপচার মধ্যে আছেন. এখন, চিকিৎসক. এখন আমি 

ALAN Estrada: এর বাস্তব সাথে পাঠিয়ে দাও Let's-. রিয়াল. 

ডেভিড জে MALAN: রিয়াল. ঠিক আছে. আপনি বাস্তব প্রয়োজন তাহলে. এখন, মাইক স্মিথ যা উপায়? 

ALAN Estrada: এই ভাবে. 

ডেভিড জে MALAN: কোন পথে? ALAN Estrada: অপেক্ষা করুন. এম হচ্ছে ÑÑ সঠিক? আমরা আপনার সঙ্গে শুরু 

ডেভিড জে MALAN: হ্যাঁ. তারা বাকি করছি. আপনার অধিকার. 

ALAN Estrada: হ্যা. 

ডেভিড জে MALAN: তাই মাইক এখানে. ALAN Estrada: কি? 

[হাস্যময়] 

খারাপ উদাহরণ, বলছি. দুঃখিত. ডেভিড জে MALAN: এই শেখানো হবে আপনি আপনার চেয়ার থেকে বের ডিঙ্গান. 

ALAN Estrada: ওহ. ওহ. আমি আছি. আমি আছি. ওহ. ওহ. এই ঠিক হচ্ছে ÑÑ আমি আপনি পেয়েছেন. এখানে ডান স্মিথ? 

ডেভিড জে MALAN: স্মিথ, আপনাকে ধন্যবাদ. তাই আমি স্মিথ আপ খুঁজছেন যাব? 

ALAN Estrada: ওহ. না না না. ওহ না. এটা আমার. 

ডেভিড জে MALAN: ওহ, আপনি স্মিথ পেয়েছেন. ঠিক আছে. 

ALAN Estrada: হ্যা, আমি এখানে ডান স্মিথ পেয়েছেন. দুক্ষিত বন্ধুরা. আমি Michael-- চিন্তা আমরা মাইকেল খুঁজছেন সেটা. দুঃখিত. 

ডেভিড জে MALAN: এটা ঠিক আছে. ঠিক আছে, এখন আমরা করছি Paccini এন্ড সন্স মধ্যে. 

ALAN Estrada: Paccini ও সন্তান-সন্ততি. ডেভিড জে MALAN: শুধু আপনি এবং আমি এই ভাষায়. ঠিক আছে. আমাদের মাইক স্মিথ খুঁজে. স্মিথ. 

ALAN Estrada: স্মিথ. 

ডেভিড জে MALAN: স্মিথ. আমরা আবর্জনা জন্য R মধ্যে আছেন. ALAN Estrada: আবর্জনা. ওহ. এতে কিছুটা সময় নিতে যাচ্ছে. 

[হাস্যময়] ডেভিড জে MALAN: আহমেদ. আমরা জুতা মধ্যে আছেন. 

ALAN Estrada: এখন আমরা gonna-- করছি 

ডেভিড জে MALAN: নিস. ALAN Estrada: Which-- [হাস্যময়] ওহ, এই মহান. [হাস্যময়] 

ডেভিড জে MALAN: এটা ঠিক আছে. 

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

ALAN Estrada: হুম. 

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

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

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

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

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

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

শ্রোতা: ঠিক আছে, তাই আমি মধ্যবিত্ত, ভালো হয়. সি শুরু হয়. বি এল বি আগে জে, প্র 

ডেভিড জে MALAN: যে ধরুন এক দ্বিতীয় জন্য মনে. কারণ অন্যথায়, এই শুধুমাত্র হয় আপনি আমাকে, এবং জর্ডান আকর্ষণীয়. আমরা শুরু করছি. শ্রোতা: [শ্রবণাতীত]. আর ডেভিড জে MALAN: ঠিক আছে. তুমি কি করছো? 

ক্যারোলাইন: এম মন্ত্রণালয় পরে আসে 

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

ক্যারোলাইন: মন্ত্রণালয় ডেভিড জে MALAN: হে, ভালো. 

ক্যারোলাইন: ই 

ডেভিড জে MALAN: ই, এফ হ্যা. 

ক্যারোলাইন: টি, ইউ, ভি 

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

ক্যারোলাইন: জেড তলায় যাচ্ছে. 

ডেভিড জে MALAN: ঠিক আছে. ওয়াই তলায় যাচ্ছে. এখন আমরা এক্স করা যাবে 

ক্যারোলাইন: জি ডেভিড জে MALAN: জি এর বাম যাচ্ছে. এস ডান যাচ্ছে. ঠিক আছে, একটি বাম সব পথ যাচ্ছে. 

ক্যারোলাইন: এ, বি, সি, ডি 

ডেভিড জে MALAN: এখন, ভাল. আমরা একটি পেয়েছেন, বি, সি ওয়াট এর নিচে যাচ্ছি. ঠিক আছে, টি 

ক্যারোলাইন: এইচ, আমি জে ডেভিড জে MALAN: এইচ, আমি জে গুড. ক্যারোলাইন: কেন্দ্র, আমি gonna-- করছি ডেভিড জে MALAN: ঠিক আছে. সুতরাং এখন, আমরা ধরনের চলুন এই বিভিন্ন piles একত্রীকরণ. তাই একটি সি মাধ্যমে, তারপর আমি দেখতে চাই, এবং ই, এবং ফল, এবং জি, ও এইচ, এবং আই হলাম. জে, কে এবং তারপর, এই গাদা ন্যুব্জ, কিন্তু এটা ঠিক আছে. নিশ্চিত. আমরা কিছু কোণ কাটা যাবে. ঠিক আছে. এবং তারপর আমরা ওয়াট, x, y, জেড প্রয়োজন 

ক্যারোলাইন: হ্যা. 

ডেভিড জে MALAN: চমৎকার. সুতরাং একটি বড় আপনাকে ধন্যবাদ এই বাছাইয়ের জন্য ক্যারোলিন. 

[বিপুল হর্ষধ্বনি] 

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

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

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

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

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

এই one-- গণদেবতা যাচ্ছি একটি দ্রুততর এবং দ্রুততর এখন. নিচে আস. তোমার নাম কি? ট্রেভর: ট্রেভর. 

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

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

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

ট্রেভর: যে এক. 

ডেভিড জে MALAN: নং 

ট্রেভর: ঠিক আছে. এইটা. 

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

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

ট্রেভর: ঠিক আছে. 

ডেভিড জে MALAN: কি হতে যাচ্ছে আপনার এলগরিদম? 

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

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

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

-বাছাইযোগ্য সংখ্যা 50? 

-বাছাইযোগ্য সংখ্যা 50. এবং আপনি কি প্রকাশ করতে পারেন এই দরজা প্রতিটি পিছনে কেবলমাত্র একটি আঙুল দিয়ে তা স্পর্শ করে. ধুর! ছাই. 

[হাস্যময়] 

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

-ঠিক আছে. 

আপনি তা খুঁজে পেতে যদি -এবং, আপনি সিনেমা রাখতে. আপনি তা খুঁজে পেতে না থাকে, তাহলে আপনি এটি ফিরিয়ে দিতে. 

ম্যান. 

-ওহ! 

- [শ্রবণাতীত] ঠিক আছে. তাই আমি শেষ পরীক্ষা করতে যাচ্ছি ওহ there's-- কিনা তা প্রথম. 

[সাধুবাদ] 

[END টি প্লেব্যাক] ডেভিড জে MALAN: ঠিক আছে. সুতরাং স্পষ্ট দরজা শ্রেণীবিভাজন অধিক দক্ষতা বাড়ে. আর তাই, দুইবার হিসাবে দ্রুত আমি সেখানে কি বোঝানো হয়. আর তাই জে ভাগ্যবান উভয় বার পেয়েছিলাম. আর তিনি যে শেষ ভাগ্যবান বছর, আমি কিছু ব্লু রে ডিস্ক আদেশ আসলে খুঁজে দিতে. আমি এই বছর দুঃখিত নই, আমরা ট্রেভর একই আছে কি না. কিন্তু ভাল এখনও কয়েক বছর ফিরে ছিল. আর তোমাদের মধ্যে এমন কিছু এই জানতে পারে তিনি CS50 মধ্যে ছিল যখন যারা সহকর্মী, শন, সঠিক সঙ্গে চ্যালেঞ্জ ছিল একই সমস্যা, এসডি যদ্যপি আপনি তাড়াতাড়ি ফিরে দিনের মধ্যে দেখতে পাবেন. এবং আপনি শুধুমাত্র করেনি না যে পাবেন তিনি জে চেয়ে একটু বেশী সময় লাগতে ট্রেভর আর একটু লম্বা, এটা ছিল আসলে এই চমৎকার সুযোগ প্রায় সবাই তারেই ভিড় একটি লা দাম উত্সাহিত, রাইট তাকে আমরা সচেষ্ট সংখ্যা খুঁজে বের করার. চলুন শুরু করা যাক. দ্রুত কটাক্ষপাত. 

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

-ঠিক আছে. তাই এখানে, আপনার টাস্ক সন অনুসরণ করছে. আমি এইসব পিছনে লুকানো আছে দরজা সংখ্যা সাত. কিন্তু এই দরজা কিছু tucked দূরে পাশাপাশি অন্যান্য ঋণাত্মক সংখ্যা হয়. এবং আপনার লক্ষ্য মনে হয় এই সংখ্যা উপরের সারির শুধু একটি অ্যারের, বা ঠিক যেমন কাগজের টুকরা ক্রম তাদের পিছনে সংখ্যার. এবং আপনার লক্ষ্য শুধুমাত্র উপরের ব্যবহার, হয় অ্যারে এখানে, আমার সাত নম্বর খুঁজে. আর আমরা তখন তার সমালোচনায় করতে যাচ্ছি আপনি এরকম সম্পর্কে যান কিভাবে. -ঠিক আছে. , আমাদের সংখ্যা সাত দয়া-খুঁজুন. না. পাঁচ, 19, 13. 

[হাস্যময়] 

এটি একটি কৌতুক প্রশ্ন না. এক. 

[হাস্যময়] এই মুহুর্তে, আপনার স্কোর খুব নয় ভাল, তাই আপনি ভাল হিসাবে বর্তা পারে. তিনটি. 

[হাস্যময়] 

নেভিগেশন এড়িয়ে যান. সত্যি বলতে কী, আমি কিন্তু আশ্চর্য সাহায্য না করতে পারেন কি আপনি এমনকি so--, চিন্তা করছি 

[হাস্যময়] শুধু উপরের সারি, তাই আপনি তিনটি বাম পেয়েছেন. তাই আমাকে সাত খুঁজে. 

[হাস্যময়] 17. সাত. 

[সাধুবাদ] 

ঠিক আছে. 

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

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

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

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

ঠিক আছে. সুতরাং আমরা এখানে এবং এই আছে কি আরো বিশ্রী বেশী মধ্যে হয়, এই থেকে আপনি যে হাস্যরস প্রয়োজন হবে সময় শুধু একটি সামান্য বিট জন্য আমাকে. আপনি এক নম্বর হতে হইবে. তোমার নাম কি? 

Annan: আনান. 

ডেভিড জে MALAN: আনান. ডেভিড. তোমার নাম কি? 

জোসেফ ইউসুফ. 

ডেভিড জে MALAN: জোসেফ, আপনি দুই নম্বর আছে. 

Serena: সেরেনা, তিন নম্বর. স্টিফান, চার নম্বর. সিনথিয়ার: সিনথিয়া. ডেভিড জে MALAN: সিনথিয়া, পাঁচ নম্বর. [শ্রবণাতীত] ডেভিড জে MALAN: [শ্রবণাতীত]. ডেভিড, সংখ্যা ছয়. মথি: ম্যাট. ডেভিড জে MALAN: ম্যাট এর সংখ্যা সাত. এবং? 

Waverly: Waverly. 

ডেভিড জে MALAN: Waverly, সংখ্যা আট. ঠিক আছে. যদি আপনি উপস could--. আপনি যদি সব, আপনার সেখানে প্রথম চ্যালেঞ্জ, আট গান ঘোরা হয় এখানে শ্রোতা সম্মুখীন. আপনি আপনার নম্বর লাগাতে পারে তাহলে এই গান এমনভাবে দাঁড়িয়েছে তারা সাথে জোট করে বোর্ডে একই নম্বর. সুতরাং তোমরা যে মত বানাতে এই গান আপনার সংখ্যা বসিয়ে এখানে দাঁড়িয়েছে. চমৎকার পর্যন্ত. 

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

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

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

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

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

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

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

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

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

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

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

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

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

বন্ধ অধ ছাড়াই তাই মঞ্চে এই বছর, আমি সংখ্যা দখল যাচ্ছি one-- এবং আপনার নাম আবার কি ছিল? 

Annan: আনান. 

ডেভিড জে MALAN: আনান. আর আপনি আমাকে যোগদান করতে পারে তাহলে তালিকার শুরুতে, যেখানে আপনি অংশভুক্ত আপনি করা যাক. Unfortunately-- আপনার নাম কি? 

স্টিফান: স্টিফান. 

ডেভিড জে MALAN: স্টিফান ভাবেই না. স্টিফান এই solves তাই আগে সমস্যা নেই, আমরা কি করা উচিত? আমরা স্টিফান সঙ্গে আপনি কি একমত? 

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

শ্রোতা: [শ্রবণাতীত]. 

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

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

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

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

জোসেফ ইউসুফ. 

ডেভিড জে MALAN: জোসেফ? আমরা জায়গায় জোসেফ ছেড়ে যাচ্ছেন. এখন, আমি ভান করতে যাচ্ছি এই ছেলেরা ভাল are-- যে, আমি জানি যে এই দুই ইতিমধ্যেই সাজানো হয়. এর এখন মনোনিবেশ করা যাক তালিকার বাকি. ছয় বর্তমান ক্ষুদ্রতম হয়. আট বড়. চার এখন বর্তমান ক্ষুদ্রতম হয়. তিনটি এখন বর্তমান ক্ষুদ্রতম হয়. এবং এখন, তাই আমি তিনটি নির্বাচন করা যাচ্ছে না যারা আপনার নাম আবার কি হচ্ছে ÑÑ? Serena: সেরেনা. ডেভিড জে MALAN: সেরেনা, যদি আপনি পারে আপনার নম্বর এবং swap 'আপনার সঙ্গে দখল KALSANG: Kalsang. ডেভিড জে MALAN: Kalsang. ফিরে আসবে এবং আমরা আছেন ঐ দুটি অদলবদল করতে যাচ্ছেন. এবং এখন, এর স্বনির্দেশকারী উপর এই করা যাক. আমি যেতে এবং আপনাকে বলছি এটা ছেড়ে যাচ্ছি পরের ক্ষুদ্রতম উপাদান নির্বাচন করুন. দুন, Dun, Dun, Dun. চার নম্বর, আপনার কী করা উচিত? চমৎকার. এখন, আমি অন্য পাস করতে যাচ্ছি. দুন, Dun, Dun, Dun. আমি পাঁচটি পরের ক্ষুদ্রতম হয় দেখতে. এখন, আমি অন্য পাস নিতে যাচ্ছি. দুন, Dun, Dun, Dun. ছয় ক্ষুদ্রতম হয়. ভাল. সাতটি ছোট. পরিবর্তন নেই. আট ক্ষুদ্রতম হয়. কৃত. 

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

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

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

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

জোসেফ ইউসুফ. 

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

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

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

Annan: আনান. 

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

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

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

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

[সাধুবাদ] 

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

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

কিন্তু নির্বাচন সাজানোর সঙ্গে, আমি যে প্রত্যাহার আবার এবং আবার উপাদান নির্বাচন এবং আবার, যে ক্ষুদ্রতম এর আমি জায়গায় এটি নির্বাণ করছি কিন্তু তারপর আমি নই আবার আমার পিছনে খুঁজছেন. তাই আমি এটি একটি সামান্য আরো স্পষ্ট মনে তারপর প্রথমবার যে, আমি বল সব এন বিয়োগ 1 পদক্ষেপ নিতে হবে ক্ষুদ্রতম উপাদান খুঁজে পেতে. তারপর আমি জায়গায় তাদের রাখা, এবং আমি পূর্বে এখানে ছিল যে কেহ উচ্ছেদ. 

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

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

তাই আবার, আমি শুধু ধরনের আবেদন করছি কিছু গাণিতিক কিছু নিয়ম-কানুন. কিন্তু লক্ষ্য করা এখন যে সবচেয়ে বড় শব্দটি এই অভিব্যক্তি, তাই কথা বলতে, n ছক হয়. তাই হ্যাঁ, এটা n বর্গ 2, বিয়োগ n / 2 দ্বারা বিভক্ত. 

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

সুতরাং আমরা 1 মিলিয়ন মানুষ ছিল ঠাউর মঞ্চ, বা 1 মিলিয়ন জিনিষের উপর আমরা সাজাতে চাই যে. এর একটি মিলিয়ন চলা যাক ঠিক যে ফর্মূলায় এটা মোট লাগে কতগুলি পদক্ষেপ দেখতে বলতে ব্যবহার করে একটি মিলিয়ন উপাদান বাছাই, নির্বাচন সাজানোর. 

তাই আমরা আগের মতই সূত্র আছে চাই. আমি পেতে যাতে আমি একটি মিলিয়ন চলা চাই একটি মিলিয়ন, 2 দ্বারা বিভক্ত বর্গ বিয়োগ একটি মিলিয়ন 2 দ্বারা বিভক্ত. আমি অগ্রিম যে গণিত না হলে এখানে, আমরা 500 বিলিয়ন আছে মাইনাস 500,000, যা , 499.999.500.000 আমাদের দেয় যা প্রশংসনীয় অভিশাপ বড় হয়. 

আসলে, আপনি এখন তুলনা যদি 499 বিলিয়ন, 999 মিলিয়ন, আমাদের মূল মান বিরুদ্ধে 500,000, 500 বিলিয়ন, এটা অভিশাপ বন্ধ. রাইট? এন 2 দেয় দ্বারা বিভক্ত বর্গ us-- অথবা বরং, এন 2 দ্বারা বিভক্ত বর্গ আমাদের 500 বিলিয়ন দিয়েছেন. যা প্রশংসনীয় অভিশাপ বন্ধ 499.999.500.000 করতে, বন্ধ 500,000 subtracting বলতে যা, অথবা আরো সাধারণভাবে, বন্ধ subtracting এন না সত্যিই একটি বড় চুক্তি ছক. এই তোলে n ছক সংখ্যা সত্যিই দ্রুত হত্তয়া. 

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

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

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

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

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

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

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

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

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

ওয়েল, তা প্রকৃতপক্ষে ঘটবে এই সংখ্যা হয় তাহলে কি হবে? আর আমরা উদাহরণ মাত্র কয়েক চেষ্টা করবো. কী সংখ্যা আট, প্রকৃতপক্ষে, তাহলে এখানে, এবং number-- উপস. তাই যদি, প্রকৃতপক্ষে, সংখ্যা আট, সমস্ত এখানে উপর উপায় এবং আমি সন্নিবেশ সাজানোর ব্যবহার করছি? 

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

তাই প্রথমবার, এটা খরচ কিছু ঠিক করা আমার এক ধাপ, তারপর এটা জিনিষ ঠিক করতে আমার দুটি ধাপে উড়ানের তালিকাটি. এটা কত যে পদক্ষেপ ফিক্স নিতে যাচ্ছে যথাস্থানে পাঁচটি করা জিনিস? তিনটি. এখন আমি আছে, কারণ এক দুই, তিন সরাতে. কতগুলি পদক্ষেপ এটা নিতে যাচ্ছে যথাস্থানে চার করা? 4 প্লাস 5 প্লাস 6, প্লাস 7. 

আর তাই এটি গাণিতিকভাবে অভিন্ন আমরা নির্বাচন সাজানোর জন্য বর্ণিত. আমরা এই সিরিজ আছে যে শুধু বৃদ্ধি হচ্ছে. 1 প্লাস 2 প্লাস 3 প্লাস 4, অথবা বিপরীতক্রমে, 7 প্লাস 6 প্লাস 5 প্লাস 4 আজকের জন্য অ্যাডস আপ এন অনুক্রম করার উদ্দেশ্যে ছক. 

তাই আমাকে খুব যে চুক্তির শর্ত দেওয়া বাবল সাজান n ছক রয়েছে. কারণ বাবল সাজান, প্রতিটি সঙ্গে সময় আমি তালিকা দিয়ে যেতে আমি প্রায় কতগুলি পদক্ষেপ গ্রহণ করছি? প্রতিটি সময় আমি আক্ষরিক সেখান থেকে সেখানে হেঁটে? প্রায় n ধাপ. কিন্তু কতবার আমি বল তালিকায় মধ্য দিয়ে যেতে হবে? 

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

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

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

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

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

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

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

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

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

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

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

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

যে ওমেগা স্বরলিপি. বড় হে, কি মানে যেহেতু উপরের আপনার চলমান সময় বেঁধে? সর্বাধিক, কত সময় কিছু সময় নিতে পারে? Omega-- দুঃখিত এই আসছে রাখে বইয়ের নাম আপ যে বিপরীত, এটি একটি নিম্ন পরিসর উপর তদ্দ্বারা সময় কিছু পরিমাণ সময় নিতে পারে. 

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

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

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

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

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

এর এক গত এক কাজ করা যাক এখানে, সন্নিবেশ সাজানোর, যা তৃতীয় অ্যালগরিদম আমরা, এবং রিকল দিকে তাকিয়ে এই এক সঙ্গে যে ঘটনাও উপাদান এটি তাদের encounters হিসেবে, কিন্তু তারপর এটা হয়তো বদল সবকিছুর উপর, রুমটা যেখানে তারা অন্তর্গত উপাদান ঢোকাতে. 

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

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

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

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

[দেয়া হল] 

যেখানে আপনি একটি ফ্রিকোয়েন্সি আবেদন করছি বার বার এর উচ্চতা উপর ভিত্তি করে. এই বুদ্বুদ ধরণের. 

[Warped দেয়া হল] 

আসছে হচ্ছে ÑÑ পরের উত্ক্রান্ত আপ পরবর্তী হচ্ছে ÑÑ নির্বাচন সাজানোর, যেখানে আবার আমরা নির্বাচন করছেন পরের ক্ষুদ্রতম উপাদান, এবং আমরা তা ক্রমবর্ধমান দেখতে পারেন বাম থেকে ডানে. 

আমাদের বিজয়ী পর্যন্ত আজ, সাজানোর মার্জ. এটা কিছু বিভাজক কিভাবে বিজ্ঞপ্তি [শ্রবণাতীত] অর্ধেক এবং আবাস মধ্যে. আমরা না আছে যা, Gnome সাজান, সম্পর্কে বললাম, এবং দৃশ্যত সৃষ্টি এবং একটি একটি বিট audally বিভিন্ন আকৃতি এবং শব্দ. পিছে যাচ্ছে, কিছু পরিষ্কার আপ. এছাড়াও heapsort খুঁজে বার এই লোক এর ওয়েবসাইটে. 

এবং যে এটি. আমরা আপনার পরবর্তী সময় দেখতে হবে. 

[Whooshing এবং সঙ্গীত]