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

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

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

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

শব্দ sort-- মার্জ এখানে বিভক্ত এবং একত্রীকরণ. আমরা কিনা, সম্পূর্ণ অ্যারে বিভক্ত এটা ছয় উপাদানের আট উপাদান, 10,000 উপাদানের আমরা এটি বিভক্ত নিচে অর্ধেক দ্বারা অর্ধেক দ্বারা অর্ধেক দ্বারা আমরা অ্যারে অধীনে আছে পর্যন্ত এন এক উপাদান অ্যারে. এন এক উপাদান অ্যারে সংকলন. তাই আমরা এক সঙ্গে শুরু 1,000-উপাদান অ্যারের, এবং আমরা বিন্দু পেতে যেখানে আমরা 1,000 এক উপাদান অ্যারে আছে. পরে আমরা যারা সাব অ্যারে একত্রীকরণ শুরু ফিরে একসাথে সঠিক অনুক্রমে. তাই আমরা দুই এক উপাদান অ্যারে নিতে এবং দুই উপাদান অ্যারের তৈরি. আমরা দুই দুই উপাদান অ্যারে নিতে এবং একটি চার উপাদান অ্যারের তৈরি এবং তাই এবং তাই আমরা করেছি পর্যন্ত আবার এক এন উপাদান অ্যারের পুনর্নির্মিত. 

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

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

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

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

আমি ডগ লয়েড আছি, এই CS50.