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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

মার্জ করে তাই, আমি কি করতে হবে? আমি যাতে উপাদান নিতে চান. সুতরাং বাম অর্ধেক এ খুঁজছেন, আমি প্রথম সংখ্যা 2 হয় দেখতে. আমি ডান অর্ধেক তাকান, আমি প্রথম সংখ্যা দেখতে তাই সম্ভবত, 1, যা সংখ্যা, আমি উপড়ে করতে চান না এবং আমার চূড়ান্ত তালিকার প্রথম করা? অবশ্যই, 1. এখন আমি যে একই প্রশ্ন জিজ্ঞাসা করতে চান. বাম অর্ধেক, আমি করেছি এখনও সংখ্যা 2 পেয়েছিলাম. ডান অর্ধেক উপর, আমি 3 নম্বর পেয়েছেন. কোনটি আমি চয়ন করতে চান? অবশ্যই, সংখ্যা 2 এবং এখন প্রার্থীদের লক্ষ্য ডান বাম, 3 4 হয়. এর, অবশ্যই, 3 চয়ন করা যাক. এখন প্রার্থীদের 4 হয় ডান বাম, 5. আমরা, অবশ্যই, 4 চয়ন. ডান বাম, 5 6. আমরা, অবশ্যই, 5 নিন. ডান বাম, 7 6. আমরা 6 নিন, এবং তারপর আমরা 7 নির্বাচন করুন, এবং তারপর আমরা 8 নিন. Voila. 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Eric Schmidt: এখন সেনেটর, আপনি, গুগল এ এখানে আছেন এবং আমি মনে করি না একটি পেশা ইন্টারভিউ হিসাবে. এখন এটা প্রেসিডেন্ট হিসেবে চাকরি পাওয়া কঠিন. প্রেসিডেন্ট ওবামার: রাইট. Eric Schmidt: আর আপনি আছেন এখন [শ্রবণাতীত] কাজ করতে যাচ্ছেন. Google- এ একটি কাজ পাওয়ার জন্য কঠিন. প্রেসিডেন্ট ওবামার: রাইট. 

Eric Schmidt: আমরা প্রশ্ন আছে, এবং আমরা আমাদের প্রার্থীদের প্রশ্ন জিজ্ঞাসা, এবং এই এক ল্যারি Schwimmer থেকে. 

প্রেসিডেন্ট ওবামার: ঠিক আছে. 

Eric Schmidt: কি? আপনাকে বলছি আমি নিশ্চয়ই মজা করছি? এটা ঠিক এখানে. সবচেয়ে কার্যকর উপায় কি হয় লক্ষ 32 বিট ইন্টিজার সাজাতে? 

প্রেসিডেন্ট ওবামার: Well-- Eric Schmidt: কখনও কখনও, হয়তো আমি দুঃখিত, maybe-- প্রেসিডেন্ট ওবামার: না, না, না, না, না, আমি কি মনে Eric Schmidt: যে এটিকে নয় প্রেসিডেন্ট ওবামার: আমি মনে করি, আমি মনে বাবল সাজান যেতে কুপথ হবে. Eric Schmidt: চলো. যিনি তাকে এই ডটকমকে? ঠিক আছে. আমি কম্পিউটার বিজ্ঞান না on-- 

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

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

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

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

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

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

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

বিশেষভাবে কোথাও এবং CS50 IDE তে, এবং এই, খুব, একটি একটি বিট হতে হবে একটি মুহূর্ত জন্য অতিসরলীকরণ, নেই, অথবা একটি সময় উপর ছিল, স্ট্যান্ডার্ড io.c নামক একটি ফাইল, কেউ মধ্যে কম্পাইল যে স্ট্যান্ডার্ড io.s বা সমমানের, কেউ তারপর সমবেত যে স্ট্যান্ডার্ড io.o মধ্যে, অথবা এটি একটি মধ্যে দেখা যাচ্ছে কিছুটা ভিন্ন ফাইল একটি ভিন্ন থাকতে পারে বিন্যাস পুরাপুরি এক্সটেনশন ফাইল, তত্ত্ব ও ধারণার, ঠিক কিন্তু সেই পদক্ষেপ কিছু ফর্ম ঘটতে ছিল. বলে, এখন যে হয়, যা আমি একটি প্রোগ্রাম লেখা করছি যখন, hello.c, শুধু বলেছেন যে, ওহে দুনিয়া, এবং আমি কারোর কোড ব্যবহার করছি একটি একদা যা ছিল printf,, মত সময়, স্ট্যান্ডার্ড io.c নামক একটি ফাইলে, তারপর একরকম আমি আমার নেওয়া আছে অবজেক্ট কোড, আমার zeros এবং বেশী, এবং যে ব্যক্তি এর অবজেক্ট কোড, বা zeros এবং বেশী, এবং একরকম তাদের একসঙ্গে লিঙ্ক যে, হ্যালো বলা এক চূড়ান্ত ফাইল আছে শূন্য সব এবং আমার প্রধান ফাংশন থেকে বেশী, এবং শূন্য সব এবং printf জন্য বেশী. 

এবং প্রকৃতপক্ষে, যে গত প্রক্রিয়া বলা হয়, আপনার অবজেক্ট কোড লিঙ্ক. যার আউটপুট একটি এক্সিকিউটেবল ফাইল. তাই সততা, এ প্রতিদিন, কিছুই শেষ সপ্তাহে এক থেকে পরিবর্তিত হয়েছে, যখন আমরা প্রথম প্রোগ্রাম কম্পাইল শুরু. প্রকৃতপক্ষে, এই সব হয়েছে ফণা নীচে ঘটছে, কিন্তু এখন আমরা একটি অবস্থানে আছেন যেখানে আমরা আসলে যা করতে পারেন এইসব বিভিন্ন পদক্ষেপ সরাইয়া জ্বালাতন. এবং প্রকৃতপক্ষে, শেষে দিনের, আমরা এখনও আছেন zeros এবং বেশী, সঙ্গে বাকি যা একটি মহান segue এখন আসলে সি আরেকটি ক্ষমতা, যে আমরা সম্ভবত লিভারেজ ছিল না করেছি তারিখ থেকে, bitwise অপারেটরদের হিসেবে পরিচিত. অন্য কথায়, এখন পর্যন্ত, যে কোনো সময় আমরা করেছি সি সি বা ভেরিয়েবলের মধ্যে তথ্য মোকাবেলা, আমরা ভালো কিছু ছিল করেছি অক্ষর এবং floats এবং প্লাগইন এবং longs এবং টেনিস এবং মত, কিন্তু ঐ সব অন্তত আট বিট. আমরা এখনো করতে সক্ষম হয়েছি না পৃথক বিটের নিপূণভাবে, এমনকি একজন ব্যক্তি বিট যদিও আমরা একটি 0 এবং একটি 1 প্রতিনিধিত্ব করতে পারে না. এখন এটা সি দেখা যাচ্ছে যে, আপনি পৃথক বিটের করার সুযোগ পেতে পারেন, আপনি সিনট্যাক্স জানেন তাহলে, যা দিয়ে তাদের এ পেতে. 

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

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

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

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

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

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

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

ঠিক আছে. যে সপ্তাহে তিনটি জন্য এটি. আমরা আপনার পরবর্তী সময় দেখতে হবে. এই ছিল CS50. 

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

বক্তা 1: তিনি জলখাবার ছিল একটি হট অর্থহীন ফলের টুকুরা খাওয়ার বার. তিনি তার মুখের উপর এটি সব ছিল. তিনি দাড়ি ভালো যে চকলেট পরেছে স্পিকার 2: আপনি কি করছেন? স্পিকার 3: Hmmm? কি? 

স্পিকার 2: আপনি শুধু ডাবল চোবান কি? আপনি ডবল চিপ চুবান. স্পিকার 3: মাফ করবেন. স্পিকার 2: আপনি যদি, চিপ চুবান একটি কামড় ওঠে, এবং আপনি আবার চুবান. স্পিকার 3: স্পিকার 2: যে নির্বাণ মত তাই ডিপ আপনার পুরো মুখের ডান. পরবর্তী সময় আপনি একটি চিপ নেওয়া শুধু একবার তা ডিপ, এবং এটি শেষ. 

স্পিকার 3: আপনি কি জানেন ড্যান? আপনি যদি ডিপ করতে চান যে ভাবে ডিপ. আমি ডিপ করতে চান যে ভাবে ডিপ করব.