[Powered by Google Translate] [অনুচ্ছেদ 3 - আরো আরামদায়ক]
[Rob Bowden - হার্ভার্ড বিশ্ববিদ্যালয়]
>> [এটি CS50. - CS50.TV]
>> তাই অদ্ভুত প্রথম প্রশ্ন worded হয়.
GDB আপনাকে একটি প্রোগ্রাম "ডিবাগ", কিন্তু, আরো ঠিক করে কি, এটা কি কোনো দিন?
আমি যে এক উত্তর, এবং আমি কি ঠিক এর প্রত্যাশিত জানি না করব,
তাই আমি তা লাইন বরাবর এটি এর কিছু অনুমান করছি আপনাকে ধাপে ধাপে
প্রোগ্রামের ভিতর দিয়ে হেটে যেতে, এটিতে যোগাযোগ করেন, পরিবর্তন ভেরিয়েবল, সব জিনিষ না -
মূলত সম্পূর্ণরূপে একটি প্রোগ্রাম সঞ্চালনের নিয়ন্ত্রণ
এবং কোনো প্রোগ্রাম সঞ্চালনের প্রদত্ত অংশ পরিদর্শন করা.
সুতরাং যারা বৈশিষ্ট্য আপনাকে জিনিষ ডিবাগ.
ঠিক আছে.
কেন বাইনারি অনুসন্ধান জন্য প্রয়োজন যে একটি অ্যারের অনুসারে বাছাই করা হবে?
কে চায় যে উত্তর?
[ছাত্রদের] কারণ এটা যদি এটি সাজানো না কোনো লাভ হয় না. >> হ্যাঁ. [হাস্য]
যদি এটি অনুসারে সাজানো নয়, তারপর এর অর্ধেক এটি বিভক্ত করা অসম্ভব
এবং বাম যাও যে সবকিছু জানতে হয় কম এবং ডান সবকিছু
একটি মধ্যম মানের তুলনায় অধিক.
সুতরাং এটি করা প্রয়োজন অনুসারে সাজানো যাও.
ঠিক আছে.
কেন হবে বর্গ হে মধ্যে বুদ্বুদ সাজান?
কেউ কি প্রথম একটি খুব দ্রুত কি বুদ্বুদ সাজানোর হয় একটি উচ্চ পর্যায়ের পরিদর্শন দিতে চান?
[ছাত্রদের] আপনি মূলত প্রতিটি উপাদান দিয়ে যান এবং আপনার প্রথম কয়েক উপাদান চেক.
যদি তারা যেখানে আপনি তাদের অদলবদল ফুরিয়েছে, তাহলে পরবর্তী কয়েক উপাদান এবং তাই চেক.
যখন আপনি শেষ পৌঁছানোর পরে, আপনি কি জানেন যে বৃহত্তম উপাদান শেষে স্থাপন করা হয়,
যাতে আপনি উপেক্ষা যে একজন আপনাকে যাচ্ছে মাধ্যমে রাখা,
এবং প্রতিটি সময় এক কম উপাদান পর্যন্ত আপনার কোন পরিবর্তন করার জন্য আপনি চেক আছে. >> হ্যাঁ.
এটা বুদ্বুদ সাজানোর বলা হয় কারণ, তাই যদি আপনি তার দিকে অ্যারের টুসকি এটি উপরে এবং নিচে, এর উল্লম্ব,
তারপর বড় মান নীচে এবং ছোট মান শীর্ষে বুদ্বুদ আপ করবে না ডুবা হবে.
এটা কিভাবে তার নাম পেয়েছেন.
এবং হ্যাঁ, আপনি ঠিক মধ্য দিয়ে যেতে হবে.
আপনি অ্যারে করে, তার বড় মান সোয়াপিং রাখা
নীচে যাও বৃহত্তম মান পেতে.
>> কেন এটা করা বর্গ হে?
প্রথম, কেউ কেন এটা করা হে বর্গ বলতে চাই না?
[ছাত্রদের] যেহেতু প্রতিটি চালানোর জন্য এটি হবে বার দেখা যায়.
আপনি শুধুমাত্র নিশ্চিত করুন যে আপনি সব উপায় সরিয়ে ফেলা বৃহত্তম উপাদান করতে পারবেন,
তাহলে হিসাবে অনেক উপাদানের জন্য যে পুনরাবৃত্তি আছে. >> হ্যাঁ.
তাই মনে রাখা কি বড় হে মানে কি বড় ওমেগা উপায়.
বড় হে ঊর্ধ্ব ধীর আসলে কিভাবে এটিকে চালাতে পারে আবদ্ধ ভালো হয়.
সুতরাং এর আউটপুট হবে বর্গ দিয়ে বলে, এটা বা অন্য এটি চালানোর জন্য সক্ষম হবে n হে না
রৈখিক সময়, কিন্তু এটা n ঘনাংকিত হে
কারণ এটি হবে ঘনাংকিত হে দ্বারা বেষ্টিত.
যদি n বর্গ হে দ্বারা বেষ্টিত এর পরে, এটি হবে ঘনাংকিত দ্বারা বেষ্টিত এর জন্যও.
সুতরাং স্কয়ার্ড n, এবং হয় চরম খারাপ ক্ষেত্রে এটা হবে স্কয়ার্ড চেয়ে আরও ভাল করতে পারে না,
যা কেন তা N বর্গ হে.
সুতরাং কিভাবে আসে আউট n ছক হতে যাও অসম্মান দেখতে গণিত,
যদি আমরা আমাদের তালিকার যে পাঁচটি জিনিস আছে, প্রথমবার সম্ভাব্য কতগুলি বিনিময়সমূহ আমরা তৈরি করতে পারে
যাতে এই পেতে? এর আসলে ঠিক করা যাক -
কত মুল্যের বিনিময়ে আমরা যাও বুদবুদ সাজানোর প্রথমবার চালানোর অ্যারের মাধ্যমে করতে যাচ্ছে?
[ছাত্রদের] হবে - 1. >> হ্যাঁ.
>> 1 - যদি 5 উপাদান আছে, আমরা যাও যাও n তৈরি করতে যাচ্ছেন.
তারপর দ্বিতীয় এক কতগুলি বিনিময়সমূহ আমরা করতে যাচ্ছি?
[ছাত্রদের] n - 2. >> হ্যাঁ.
এবং তৃতীয় করা হবে - 3, এবং তারপর সুবিধার জন্য আমি গত দুই লিখতে হবে
তারপর হিসাবে আমরা 2 বিনিময়সমূহ এবং 1 মাপের swap তৈরি করতে যাচ্ছেন.
আমি অনুমান গত এক বা ঘটতে পারে আসলে দরকার নেই.
এটা একটি swap? আমি জানি না.
সুতরাং এই হল বিনিময়সমূহ মোট পরিমাণ বা অন্তত তুলনা করতে থাকে.
এমনকি আপনি যদি না অদলবদল না, আপনি কি এখনও মান তুলনা করা প্রয়োজন.
সুতরাং n আছে - অ্যারে মাধ্যমে প্রথম রান 1 তুলনা.
আপনি যদি এইসব জিনিস নতুন করে সাজানো, আমি কি আসলে এটি ছয় জিনিস বানাতে তাই জিনিষ আপ চমত্কারভাবে গাদা,
এবং তারপর আমি কি 3, 2, করব 1.
সুতরাং শুধু এই অঙ্ক সাজানোর, আমরা কতগুলি তুলনা করতে আমরা দেখতে চাই
সমগ্র এলগরিদম.
তাই আপনি যদি আমরা নিচে এখানে এইসব বলছি আনা,
তারপর আমরা এখনও ঠিক করছি কিন্তু অনেক তুলনা সেখানে summing.
কিন্তু আমরা যদি এই যোগফল এবং আমরা এই যোগফল এবং আমরা এই যোগফল,
এটি এখনও একই সমস্যা. আমরা শুধুমাত্র সেই বিশেষ গ্রুপ যোগফল.
>> তাই এখন আমরা n এর summing 3 করছেন. এটা 3 হবে এর না.
এটা সবসময় এর যাও n / 2 n এর হবে.
তাই আমরা এখানে আছে 6 আছে এরকম.
যদি আমরা 10 জিনিস ছিল, তারপর আমরা 5 জিনিস ভিন্ন জোড়া জন্য এই দলভুক্ত করা যেত না
এবং n + n + n + n + n সঙ্গে শেষ.
তাই আপনি সর্বদা যাও n / 2 n এর করছি পেতে যাচ্ছে, তাই এই আমরা এটি স্কয়ার্ড n / 2 যাও একফোঁটা আউট করব.
তাই যদিও এটা অর্ধেক উপাদান, যা আসতে ঘটবে
কারণ সত্য যে আমরা অ্যারের উপর প্রতিটি পুনরাবৃত্তির মাধ্যমে তুলনা 1 কম
তাই যে কিভাবে আমরা 2 তরা, কিন্তু এটি এখনও n ছক.
আমরা একটি অর্দ্ধ্বেক ধ্রুবক ফ্যাক্টর না যত্ন সম্পর্কে না.
সুতরাং হে বড় উপাদান একটি ভালো অনেক গণিত এই সাজানোর করছেন মাত্র ধরনের উপর নির্ভর করে,
গাণিতিক এবং জ্যামিতিক অঙ্ক সিরিজ স্টাফ করছেন,
কিন্তু এই কোর্সে তাদের অধিকাংশই হয় চমত্কার সহজবোধ্য.
ঠিক আছে.
কেন n র ওমেগা হয় সন্নিবেশ সাজান? ওমেগা মানে কি?
[দুই ছাত্র একযোগে ভাষী - অপাচ্য] >> হ্যাঁ.
ওমেগা হিসাবে আপনি লোয়ার বাউন্ড মনে করতে পারেন.
>> সুতরাং কোন ব্যাপার কিভাবে দক্ষ আপনার সন্নিবেশ সাজানোর আলগোরিদিম হয়,
নির্বিশেষে যে তালিকা এর মধ্যে পাস, এটি সবসময় অন্তত n জিনিষ তুলনা করা হয়েছে
অথবা এটা হবে জিনিষ উপর পুনরুক্তি করা আছে.
কেন হল?
[ছাত্রদের] কারণ যদি ইতিমধ্যে তালিকা অনুসারে বাছাই করা হয়, তাহলে মাধ্যমে প্রথম পুনরাবৃত্তির
আপনি শুধুমাত্র গ্যারান্টি পারেন যে খুব প্রথম উপাদান হয় অন্তত,
এবং দ্বিতীয় পুনরাবৃত্তির শুধুমাত্র আপনি গ্যারান্টি পারেন প্রথম দুটি
কারণ আপনি যে তালিকা বাকি অনুসারে বাছাই করা হয় না. >> হ্যাঁ.
যদি আপনি একটি সম্পূর্ণ অনুসারে সাজানো তালিকা পাস অন্ততপক্ষে, আপনি সমস্ত উপাদানের যান উপর আছে
যাও যে কিছুই করা প্রয়োজন প্রায় সরানো দেখুন.
তাই ক্ষণস্থায়ী তালিকা উপর এবং বলছে ওহ, ইতিমধ্যে এই সাজানো হয়,
এটা অসম্ভব জন্য আপনি এটি সাজানো এর জানি না হওয়া পর্যন্ত আপনি প্রতিটি উপাদান চেক
যে তারা সাজানো ক্রম তা দেখুন.
তাই নিম্ন সন্নিবেশ সাজানোর উপর বাউন্ড n র ওমেগা.
কি লক চলমান একত্রীকরণ ধরণের সময়,
লক হচ্ছে আবার বড় হে?
সুতরাং এ লক দৃশ্যকল্প মধ্যে কিভাবে, একত্রীকরণ সাজানোর চালানোর জন্য?
[ছাত্রদের] N লগ n. >> হ্যাঁ.
দ্রুততম সাধারণ বাছাই আলগোরিদিম হল n log n. আপনি ভাল করতে পারবেন না.
>> বিশেষ মামলা আছে, এবং আমরা যদি সময় থাকে আজ - কিন্তু সম্ভবত আমরা won't -
আমরা এক যে আছে n log n বেশী ভালো দেখতে পারে.
কিন্তু সাধারণ ক্ষেত্রে, আপনি n log n চেয়ে আরও ভাল করতে পারে না.
এবং সাজানোর একত্রীকরণ যাও আপনি এই কোর্স যা n log n জন্য জানা উচিত হবে এরকম.
তাই আসলে আমরা যে আজ রূপায়ণকারী হবে.
এবং অবশেষে, কোন অধিক তিনটি বাক্য, কিভাবে নির্বাচন সাজানোর কাজ করে?
কিন্তু কেউ উত্তর দিতে চান, এবং আমি আপনার বাক্য গণনা করব
কারণ যদি আপনি 3 পুনরালোচনা -
কেউ কি নির্বাচন সাজানোর কথা মনে পড়ে?
নির্বাচন সাজানোর সাধারণত বেশ সহজ শুধু নাম স্মরণ থেকে যাও.
আপনি শুধুমাত্র অ্যারের উপর পুনরুক্তি করা, যাই হোক না কেন বৃহত্তম মান বা ক্ষুদ্রতম খুঁজে -
যাই হোক না কেন আপনাকে ইন বাছাই করছেন
সুতরাং আসুন আমরা বলতে থেকে ক্ষুদ্রতম সর্বশ্রেষ্ঠ যাও বাছাই করছেন.
আপনি অ্যারের উপর, যাই হোক না কেন বারবার সর্বনিম্ন উপাদান হল খুঁজছেন,
এটি নির্বাচন করুন এবং তারপর এটা প্রথমেই যা কিছু থাকে অদলবদল.
অ্যারের উপর দ্বিতীয় পাস এবং তারপরে, সর্বনিম্ন উপাদান জন্য চেহারা আবার,
এটি নির্বাচন করুন এবং তারপর দ্বিতীয় অবস্থানে কি এর সাথে বিনিময় করা.
সুতরাং আমরা অবচয় হয় এবং সর্বনিম্ন মান নির্বাচন করে
এবং অ্যারের সামনে সেগুলি সন্নিবেশিত করা অবধি সাজানো হয়.
যে প্রশ্ন?
>> এই ফর্মগুলি আপনি অবশ্যম্ভাবীরূপে পূরণ যখন আপনি pset জমা করছেন উপস্থিত আছে.
যারা মূলত, সেই সব উত্তর.
ঠিক আছে, তাই এখন সমস্যা কোডিং.
আমি ইতিমধ্যে ইমেইলে পাঠানো আউট - কেউ কি যে ইমেইল পাবেন না? ঠিক আছে.
আমি ইতিমধ্যে ইমেইলে পাঠানো স্থান যে আমরা ব্যবহার করা যাচ্ছে করেছেন,
এবং যদি আপনি আমার নামের উপর ক্লিক করুন - তাই আমি মনে করি আমি নীচে করা যাচ্ছে না
কারণ আর পিছন দিকে - কিন্তু আপনি যদি আমার নামের উপর ক্লিক করুন এবং আপনি 2 পুনর্বিবেচনা দেখতে পাবেন.
পরিবর্ধন ও পরিবর্তন তালিকা 1 ইতিমধ্যে আমি কপি করা এবং শূন্যস্থানের মধ্যে কোড আটকানো যাচ্ছে
অনুসন্ধান জিনিস জন্য আপনি প্রয়োগ আছে চলুন.
এবং পুনর্বিবেচনার 2 সাজানোর জিনিস যে আমরা যে পরে বাস্তবায়ন করা হবে.
তাহলে আপনি আমার পরিবর্তনসমূহ 1 এবং সেখান থেকে কাজ ক্লিক করতে পারেন.
এবং এখন আমরা বাইনারি অনুসন্ধান বাস্তবায়ন করতে চান.
>> কেউ কি শুধু একটি pseudocode উচ্চ পর্যায়ের ব্যাখ্যা দিতে চান
কি আমাদের অনুসন্ধান জন্য কি আছে যাচ্ছেন? হাঁ.
[ছাত্রদের] আপনি এই মাত্র অ্যারের মধ্যম এবং গ্রহণ করবে যদি আপনি যা খুঁজছেন তা দেখতে
কম যে বেশী বা যে বেশী.
এবং যদি কম, আপনি অর্ধেক যে কম যান,
এবং যদি এটা আরো, আপনি অর্ধেক যে আরো যান এবং আপনি ওটা ঠিক না হওয়া পর্যন্ত আপনি এক জিনিস পেতে.
[Bowden] হ্যাঁ.
উল্লেখ্য, ইতিমধ্যে আমাদের সংখ্যা শ্রেণীবিন্যাস অনুসারে বাছাই করা হয়,
এবং যাতে এর মানে হল যে আমরা যে সুবিধা নিতে পারে আমরা প্রথমে চেক করতে পারেন,
ঠিক আছে, আমি 50 নম্বর খুঁজছি.
তাই আমি মধ্যম মধ্যে যেতে পারেন.
মিডিল হয় যখন এটা একটা জিনিষ এমনকি নম্বর অনুধাবণ করা কষ্টকর,
কিন্তু এর যাক সেটা আমরা সবসময় মধ্যম যাও অগ্রভাগ ছাঁটিয়া দেত্তয়া করব.
তাই আমরা এখানে 8 জিনিষ আছে, তাই মধ্যম 16 হবে.
আমি 50 খুঁজছি, তাই 50 16 চেয়ে বেশী.
তাই এখন আমি মূলত এই উপাদান হিসাবে আমার অ্যারের বিবেচনা করতে পারেন.
আমি থেকে 16 বছরের সব বাতিল করতে পারেন.
এখন আমার অ্যারের শুধুমাত্র এই 4 টি উপাদান, এবং আমি আবার বলছি.
আমি তখন আবার মধ্যম খুঁজতে চান, যা 42 হবে.
42 50 তুলনায় কম, তাই আমি এই দুটি উপাদান বর্জন করা যেতে পারে.
এটা আমার অবশিষ্ট অ্যারে.
আমি আবার মধ্যম খুঁজে চলেছি.
আমি অনুমান 50 ছিল একটি খারাপ উদাহরণ কারণ আমি সবসময় নিক্ষেপ ছিল বাম জিনিষ দূরে,
কিন্তু একই পরিমাপ দ্বারা, আমি যদি কিছু খুঁজছি
এবং এটা উপাদান কম আমি বর্তমানে করছি খুঁজছেন,
তারপর আমি এই মুহূর্তে সবকিছু সরিয়ে যাচ্ছি.
তাই এখন আমরা যে বাস্তবায়ন প্রয়োজন.
উল্লেখ্য, আমরা আকার মধ্যে পাস করতে হবে.
আমরা হার্ড কোড আকার প্রয়োজন হতে পারে.
তাই আপনি যদি আমরা পেতে যে পরিত্রাণ # define -
ঠিক আছে.
কিভাবে সুন্দরভাবে আমি চিন্তা করতে পারেন কি বর্তমানে সংখ্যা অ্যারের আকার?
>> সংখ্যা অ্যারের মধ্যে কতগুলি উপাদান হল?
[ছাত্রদের] সংখ্যা, বন্ধনী,. দ্বারা?
[Bowden] যে সি মধ্যে বিদ্যমান নয়
. প্রয়োজন দ্বারা.
অ্যারেগুলির বৈশিষ্ট্য নেই, তাই কোনও অ্যারে দৈর্ঘ্যের সম্পত্তি আছে
যে দিন আপনি যদিও দীর্ঘ এটা ঘটবে হবে.
[ছাত্রদের] কত মেমরি তা দেখুন এবং কত দ্বারা বিভক্ত করা - >> হ্যাঁ.
তাই কিভাবে আমরা দেখতে পারেন কি ভাবে এটা অনেক মেমরি আছে? >> [ছাত্রদের] Sizeof. >> হ্যাঁ, sizeof.
Sizeof হয় অপারেটর যে নম্বর অ্যারের আকার ফিরে যাচ্ছে.
এবং যে যদিও অনেক পূর্ণসংখ্যা হতে যাচ্ছে বার আছে একটি পূর্ণসংখ্যা আকার
যেহেতু যে কতটা মেমরি প্রকৃতপক্ষে এটি গ্রহণ এর আপ.
সুতরাং যদি আমি একটা জিনিসে অ্যারের মধ্যে নম্বর চাই,
তারপর আমি একটা পূর্ণসংখ্যা মাপ দ্বারা বিভক্ত করা চান যাচ্ছি.
ঠিক আছে. সুতরাং যা আপনাকে মাপ সম্পর্কে এখানে পাস.
কেন আমি মাপ এ সব সম্পন্ন করতে হবে?
কেন শুধু আমি না আপ করতে পারেন এখানে int-আকার = sizeof (খড়ের গাদা) / sizeof (int)?
কেন এই কাজ করে না?
[ছাত্রদের] এটি একটি বিশ্বব্যাপী পরিবর্তনশীল এর হইনি.
[Bowden] খড়ের গাদা বিদ্যমান এবং আমরা সংখ্যায় খড়ের গাদা হিসাবে পার করছি,
এবং এই কি আসতে এর একটি foreshadowing ধরনের. হাঁ.
[ছাত্রদের] খড়ের গাদা শুধুমাত্র এটি উল্লেখ করে, তাই এটি কিভাবে বড় যে রেফারেন্স হয় আবার ফিরে আসবে.
হাঁ.
আমি বক্তৃতায় সন্দেহ হয় যে আপনি স্ট্যাকের দেখা এখনো করেছি সত্যিই, ডান?
আমরা এটা সম্পর্কে করেছি উচ্চারিত.
সুতরাং স্ট্যাকের হল যেখানে আপনার ভেরিয়েবল সব সঞ্চিত করা যাচ্ছে.
>> কোন মেমরি যা স্থানীয় ভেরিয়েবলের জন্য বরাদ্দ এর স্ট্যাকের মধ্যে যাচ্ছে,
এবং প্রতিটি ফাংশন স্ট্যাকের উপর নিজস্ব স্থান পায়, তার নিজস্ব স্ট্যাকের ফ্রেম কি বলা হচ্ছে.
সুতরাং তার প্রধান স্ট্যাকের ফ্রেম আছে, এবং এটি ভেতরে এই সংখ্যা অ্যারের বিদ্যমান যাচ্ছে,
এবং এটি আকার sizeof (সংখ্যা) করা হচ্ছে.
এটি উপাদানের আকার দ্বারা বিভক্ত সংখ্যার আকার আছে যাচ্ছে,
কিন্তু এর প্রধান যে স্ট্যাকের মধ্যে ফ্রেম সমস্ত জীবন.
যখন আমরা অনুসন্ধান কল, অনুসন্ধান নিজস্ব স্ট্যাকের ফ্রেম পায়,
নিজস্ব স্থান তার স্থানীয় ভেরিয়েবল সমস্ত সঞ্চয়.
কিন্তু এই আর্গুমেন্ট - তাই খড়ের গাদা এই সমগ্র অ্যারের একটি কপি হয় না.
আমরা অনুসন্ধান করে একটি কপি হিসাবে সমগ্র অ্যারের মধ্যে না পাশ.
এটা শুধু যে অ্যারের একটি রেফারেন্স প্রেরণ করা হয়.
সুতরাং অনুসন্ধান এই রেফারেন্স মাধ্যমে এই সংখ্যাগুলি অ্যাক্সেস করতে পারেন.
এটা এখনও এর বিষয় প্রধান স্ট্যাকের ফ্রেম এর ভিতর যে বাস অ্যাক্সেস,
কিন্তু মূলত, যখন আমরা পয়েন্টার পেতে, খুব শীঘ্রই যা করা উচিত,
এই কি পয়েন্টার হয়.
পয়েন্টার ঠিক রেফারেন্স জিনিষ, এবং আপনি জিনিষ অ্যাক্সেস পয়েন্টার ব্যবহার করতে পারেন
স্ট্যাকের ফ্রেম অন্যান্য জিনিসের 'যা.
সুতরাং যদিও নম্বর স্থানীয় প্রধান যাও, আমরা এখনও এই পয়েন্টার মাধ্যমে এটি অ্যাক্সেস করতে পারেন.
কিন্তু যেহেতু এটি একটি পয়েন্টার এবং এটি শুধু একটি রেফারেন্স,
sizeof (খড়ের গাদা) শুধু রেফারেন্স নিজেই আকার ফেরৎ.
এটা জিনিস তা নির্দেশকারী এর মাপ ফেরত দেয় না.
এটি সংখ্যার প্রকৃত মাপের ফেরত দেয় না.
তাই এই কাজ হিসাবে আমরা চাই এটা যাচ্ছে না.
>> যে প্রশ্ন?
পয়েন্টার মধ্যে উল্লেখযোগ্য ভাবে আরো রক্তিম বিষদভাবে সর্বস্বান্ত করা সপ্তাহের মধ্যে আসতে হবে.
এবং এই কারণে যে আপনি দেখুন, সবচেয়ে অনুসন্ধান জিনিষ অথবা সাজানোর জিনিস অনেক,
তারা প্রায় সব হয়ে যাও যাও অ্যারের প্রকৃত মাপের নিতে যাচ্ছে,
কারণ সি, আমরা কোন ধারণা কি অ্যারের আকার আছে.
আপনি নিজে ইন পাস প্রয়োজন
এবং আপনি নিজে সম্পূর্ণ অ্যারের মধ্যে পাস না কারণ আপনি শুধু উল্লেখ করছি মধ্যে পার করতে পারেন
এবং এটি রেফারেন্স থেকে মাপ না পেতে পারেন.
ঠিক আছে.
তাই এখন আমরা কি আগে তার ব্যাখ্যা করা হয়েছে বাস্তবায়ন করতে চান.
আপনি এটা এক মিনিটের জন্য কাজ করতে পারেন,
এবং সবকিছু ঠিকভাবে আপনি 100% কাজ পেয়ে চিন্তা করতে হবে না.
ঠিক কিভাবে আপনি কি মনে করেন এটি কাজ করা উচিত জন্য অর্ধেক pseudocode লিখুন আপ.
ঠিক আছে.
কোন সম্পূর্ণভাবে এই সঙ্গে কাজ করা এখনো প্রয়োজন.
কিন্তু কেউ আছে কি তারা এতদূর করতে স্বাচ্ছন্দ্য বোধ করেন,
কিছু ভালো আমরা একসঙ্গে কাজ করতে পারেন?
কেউ কি যাও স্বেচ্ছাসৈনিক চান? অথবা আমি এলোমেলোভাবে বাছাই করা.
এটা কোনো পরিমাপ কিন্তু কিছু কাজ আমরা একটি রাষ্ট্র মধ্যে পরিবর্তন করতে পারি দ্বারা হবে না.
[ছাত্রদের] শিওর. >> ঠিক আছে.
তাই সামান্য সংরক্ষণ আইকনে ক্লিক করে আপনি সংস্করণ সংরক্ষণ করতে পারবেন.
আপনি Ramya অধিকার,? >> [ছাত্রদের] হ্যাঁ. >> [Bowden] ঠিক আছে.
তাই এখন আমি আপনার সংস্করণ দেখতে এবং প্রত্যেকের পুনর্বিবেচনা থামা পারেন.
এবং আমরা এখানে আছে - ঠিক আছে.
সুতরাং Ramya recursive সমাধান, যা অবশ্যই একটি বৈধ সমাধান সঙ্গে গিয়েছিলাম.
দুটি উপায়ে এই সমস্যা আপনি করতে পারেন.
হয় আপনি এটি iteratively বা recursively করতে পারেন.
অধিকাংশ সমস্যার আপনি যে recursively করা সম্ভব সম্মুখীন iteratively এছাড়াও এটি করা যাবে.
সুতরাং এখানে আমরা তা সম্পন্ন recursively করেছি.
>> কিন্তু কেউ কি এটা একটি ফাংশন recursive করা মানে সংজ্ঞায়িত করতে চান?
[ছাত্রদের] আপনি যখন একটি ফাংশন আছে নিজেই কল
এবং তারপর নিজেই পর্যন্ত এটা সত্য এবং সত্য সঙ্গে আউট কল আসে. >> হ্যাঁ.
একটি recursive ফাংশন শুধুমাত্র একটি ফাংশন যা নিজেই কল.
তিনটি বড় যে একটি recursive ফাংশন আছে অবশ্যই আছে.
প্রথম স্পষ্টত হয়, এটা নিজেই কল.
দ্বিতীয়টি হল বেস কেস.
সুতরাং ফাংশন নিজেকে থামাতে কলিং কিছু সময় প্রয়োজন,
এবং যে এর জন্য কি বেস মামলা হয়.
সুতরাং এখানে আমরা জানতে পারি যে আমরা বন্ধ করা উচিত, আমরা আমাদের অনুসন্ধান ত্যাগ করা উচিত
যখন শুরু শেষ সমান - এবং আমরা উপর কি মানে যাবেন.
কিন্তু পরিশেষে, শেষ যে এর recursive ফাংশন জন্য গুরুত্বপূর্ণ:
ফাংশান একরকম বেস ক্ষেত্রে যোগাযোগ করা আবশ্যক.
যদি আপনি কিছু আপডেট আসলে করছি না হলে আপনি দ্বিতীয় recursive কল করতে চাই,
যদি আক্ষরিক শুধুমাত্র আপনার কলিং একই সঙ্গে ফাংশন আর্গুমেন্ট আবার
এবং কোন বিশ্ব ভেরিয়েবল বা কিছু পরিবর্তন আছে,
আপনি বেস পৌঁছানোর ক্ষেত্রে যে ক্ষেত্রে যে খারাপ. না, হবে
এটি একটি অসীম recursion ও একটি স্ট্যাক ওভারফ্লো হবে.
কিন্তু এখানে আমরা দেখতে যে আপডেট যেহেতু আমরা শেষ + / 2 আপডেট করার সময় আরম্ভ করা হয় ঘটছে,
আমরা যুক্তি শেষ করছি এখানে আপডেট করা, আমরা শুরু করছি যুক্তি এখানে আপডেট করা.
তাই সব recursive কল মধ্যে আমরা কিছু আপডেট করা হয়. ঠিক আছে.
আপনি কি আপনার সমাধান মাধ্যমে আমাদের পদব্রজে ভ্রমণ করতে চান? >> শিওর.
আমি SearchHelp করছি, তাই ব্যবহার করে যে প্রত্যেক সময় আমি এই ফাংশন কল করা
আমি যেখানে আমি অ্যারের খুঁজছি শুরু এবং শেষ আছে
যেখানে আমি অ্যারে খুঁজছি.
>> ধাপে ধাপে যেখানে এটি এটা মধ্যম উপাদান, যা শুরু + শেষ / 2 এর বলছে,
যে সমান আমরা কি খুঁজছেন?
এবং যদি তা হয়, তাহলে আমরা তা খুঁজে পাওয়া যায়, এবং আমি অনুমান যে recursion মাত্রা পাস আপ হয়.
এবং যদি তা সত্য না তারপর, আমরা যে কিনা চেক অ্যারের মধ্যম মান অত্যন্ত বড়,
যা ক্ষেত্রে অ্যারের বাম অর্ধেক সময়ে আমরা যাচ্ছি থেকে শুরু মধ্যম সূচক যাও দ্বারা চেহারা.
এবং অন্যথায় আমরা অর্ধেক শেষ না.
[Bowden] ঠিক আছে.
এটাতো ভালোই মনে হচ্ছে.
ঠিক আছে, তাই কয়েক জিনিষ, এবং আসলে, এটি একটি খুব উচ্চ স্তরের জিনিস
আপনি এই কোর্সের জন্য জানা প্রয়োজন, কিন্তু কখনও এটা সত্য হবে.
Recursive ফাংশন, আপনি সর্বদা শুনতে যে তারা একটি খারাপ চুক্তি
কারণ যদি আপনি recursively কল নিজেকে অনেকবার, আপনি স্ট্যাক ওভারফ্লো পেতে
যেহেতু, হিসাবে আমি আগে বলেন, প্রতি ফাংশন নিজস্ব স্ট্যাকের ফ্রেম পায়.
সুতরাং recursive ফাংশন কল প্রতিটি নিজস্ব স্ট্যাকের ফ্রেম পায়.
তাই আপনি যদি 1,000 recursive কল করতে, আপনাকে 1,000 স্ট্যাকের ফ্রেম পাবেন,
এবং দ্রুত হচ্ছে আপনি অনেকগুলি স্ট্যাকের ফ্রেম এবং জিনিষ ঠিক বিরতি হতে.
সুতরাং যে কেন recursive ফাংশন সাধারণত খারাপ.
কিন্তু লেঙ্গুড়-recursive ফাংশন একটি recursive ফাংশন চমৎকার উপসেট সেখানে বলা হয়,
এবং এই এক যেখানে কম্পাইলার যদি এই লক্ষ্য একটি উদাহরণ হতে ঘটবে
এবং এটা করা উচিত, আমি মনে করি - ঝনঝন মধ্যে যদি আপনি এটি-O2-এর পতাকা পাস
তাহলে এই লেঙ্গুড় recursive এবং বিজ্ঞপ্তি জিনিষ ভালো করতে হবে.
>> সেই একই এবং উপর আবার প্রতিটি recursive কলের জন্য স্ট্যাকের ফ্রেম পুনরায় ব্যবহার করতে হবে.
তাই যেহেতু আপনি একই স্ট্যাকের ফ্রেম ব্যবহার করছেন, আপনি চিন্তা করতে হবে না
কখনও উদ্বেল, গাদা করা এবং একই সময়ে, যেমন আপনি আগে বলেন,
যেখানে একবার ফিরে আপনি সত্য হয় তাহলে, এটি এই স্ট্যাকের ফ্রেম সব ফিরে আপ হয়েছে
এবং SearchHelp 9 ম ফিরে যাও আছে 10 কল, 8 ম ফিরে যাও আছে.
তাই যখন কার্যকারিতাই লেঙ্গুড় recursive ঘটতে করার দরকার নেই.
তাই কি করে এই ফাংশন লেঙ্গুড় recursive হয় যে বিজ্ঞপ্তি জন্য কোনো searchHelp দেওয়া কল
recursive কল যে এটি তৈরীর এর কি এটা ফেরত না.
সুতরাং SearchHelp প্রথমে কলে, হয় আমরা অবিলম্বে মিথ্যা ফিরে,
অবিলম্বে সত্য ফিরে, বা আমরা SearchHelp একটি recursive কল
যেখানে আমরা কি ফিরে সেটি কি ফিরে কল করা হয়.
এবং আমরা এই যদি আমরা int x = SearchHelp, ফিরতি x * 2 মত কিছু করেছিল না পারে,
কিছু কিছু র্যান্ডম পরিবর্তন.
>> সুতরাং এখন এই recursive কল, এই int x = SearchHelp recursive কল,
আর লেঙ্গুড় recursive কারণ এটি আসলে ফিরে আছে
ফিরে যাও পূর্ববর্তী স্ট্যাকের ফ্রেম যাতে যে ফাংশন কল পূর্ববর্তী
ফিরতি মূল্য সঙ্গে তারপর কিছু করতে পারি.
তাই এই হল, কিন্তু লেঙ্গুড় recursive না কি আমরা আগে ছিল সুন্দরভাবে হয় লেঙ্গুড় recursive. হাঁ.
[ছাত্রদের] দ্বিতীয় বেস কেস চেক করা উচিত হইনি প্রথম
কারণ যেখানে আপনি যখন পাস যুক্তি এটি এমন একটি পরিস্থিতি তৈরী হতে পারে
আপনি = সমাপ্তি আছে, কিন্তু শুরু তারা সুই মান.
প্রশ্ন কেস মধ্যে ছিল না চালানোর জন্য আমরা যেখানে শেষ হয় সুই মান পারেন
বা = শেষে শুরু উপযুক্তভাবে,, = শেষে শুরু
এবং আপনি যে বিশেষ মান চেক আসলে আছে এখনো,
তারপর শেষ + / 2 শুরু হয় ঠিক একই মান হবে.
কিন্তু ইতিমধ্যে আমরা ফিরে করেছি মিথ্যা এবং আমরা মান আসলে চেক না.
সুতরাং প্রথম কলে অন্ততপক্ষে,, যদি আকার 0 তারপর, আমরা মিথ্যা ফেরত চান.
কিন্তু যদি আকার হয় 1, তাহলে সমান শেষে শুরু যাচ্ছে না,
এবং আমরা একটি উপাদান অন্তত চেক করব.
কিন্তু আমি মনে করি আপনি ঠিক যে আমরা একটি ক্ষেত্রে শেষ পর্যন্ত যেখানে শেষ + / 2 শুরু করতে পারেন,
শুরু সমাপ্ত হচ্ছে শুরু + শেষ / 2 হিসাবে একই,
কিন্তু আমরা যে উপাদান আসলে চেক না.
>> সুতরাং আমরা যদি প্রথম চেক করা হল মধ্যম উপাদান মান আমরা খুঁজছেন,
তারপরে সঙ্গে সঙ্গে আমরা ফিরে সত্য পারেন.
অন্যথায় যদি তারা সমান, তারপরে অবিরত কোন বিন্দু আছে
যেহেতু আমরা একটি কেস যেখানে আমরা একটি একক উপাদান অ্যারের হয় আপডেট করছি না.
যদি যে একক উপাদান হল, আমরা এক খুঁজছেন না
তারপর সবকিছু ভুল. হাঁ.
[ছাত্রদের] ব্যাপার হল আকার থেকে হয় উপাদানের অ্যারের মধ্যে সংখ্যার চেয়ে আসলে বড়,
ইতিমধ্যে সেখানে একটি অফসেট - >> তাই মাপ করবে না -
[ছাত্রদের] যদি অ্যারের ছিল আকার 0 বলুন তারপর, SearchHelp 0 খড়ের গাদা আসলে পরীক্ষা করা
প্রথম কল.
অ্যারে আকার 0 আছে, তাই 0 - >> হ্যাঁ.
অন্য যে জিনিস আছে - এটা ভালো হতে পারে. মনে করা যাক.
তাই আপনি যদি অ্যারে 10 উপাদান ছিল এবং এক মধ্যম আমরা চেক যাচ্ছে সেটি সূচক 5,
তাই আমরা 5 চেক করছি, এবং এর যে মূল্য দেওয়া হয় কম বলে.
তাই আমরা সবকিছু দূরে ছুঁড়ে 5 অনওয়ার্ড থেকে করছি.
তাই শেষ + / 2 আমাদের নতুন শেষ হতে চলেছে শুরু,
তাই হ্যাঁ, এটি সবসময় অ্যারের শেষ বহুদূরে থাকতে যাচ্ছে.
যদি এটি একটি কেস যদি এটি ছিল এমনকি বা বিজোড় তারপর, আমরা বলতে চেক 4, হবে,
কিন্তু এখনও আমরা নিক্ষেপ করছি দূরে -
তাই হ্যাঁ, সবসময় শেষ অ্যারের প্রকৃত শেষ অতিক্রম করা যাচ্ছে.
আমরা উপাদানের উপর মনোযোগ নিবদ্ধ করা হয়, তাই সবসময় শেষে যে পরে এক হতে হবে.
এবং তাই যদি শুরু হবে কখনও সমান শেষ, আমরা আকার 0 শ্রেণীবিন্যাস আছে.
>> অন্যান্য জিনিস আমি চিন্তা ছিল হয় আমরা শুরু করা শুরু আপডেট: শেষ / 2,
তাই এই ক্ষেত্রে আমি যে সমস্যা হচ্ছে, যেখানে শেষ + / 2 শুরু
হল উপাদান আমরা চেক করছি.
চলুন শুরু করা যাক বলে আমরা এই 10-অ্যারের উপাদান ছিল. যাই হোক না কেন.
তাই শেষ + / 2 এই মত কিছু শুরু হতে যাচ্ছে,
এবং যদি যে মান না, বলতে আমরা আপডেট করতে চান.
মান বেশী, তাই আমরা অ্যারের এই অর্ধেক তাকান করতে চান.
তাই কিভাবে আমরা শুরু আপডেট করছি, আমরা শুরু করছি এখন এই উপাদান হতে আপডেট.
কিন্তু এই কাজ, বা অন্ততপক্ষে, আপনি শুরু না শেষ + / 2 + 1 টি করতে পারে.
[ছাত্রদের] আপনি + শেষ করা আরম্ভ করার প্রয়োজন হবে না [শ্রবণাতীত] >> হ্যাঁ.
আমরা ইতিমধ্যে এই চেক উপাদান এবং এটি এক খুঁজছেন তা আমরা জানি না.
তাই আমরা শুরু এই উপাদান হতে আপডেট করার প্রয়োজন হবে না.
আমরা শুধু এড়িয়ে যাও এই উপাদান হতে শুরু আপডেট করতে পারেন.
এবং সেখানে আগের একটি কেস, এর কথা বলা যাক, যে এই ছিল শেষ,
অতএব এই শুরু হবে, শেষ শুরু + / 2 এই হবে,
+ শেষ শুরু - হ্যাঁ, আমি মনে করি অসীম recursion যেতে পারেন.
চলুন শুরু করা যাক বলে এটি শুধু আকার 2 বা 1 আকার একটি অ্যারের একটি অ্যারে. আমি মনে করি এই কাজ করবে.
তাই বর্তমানে, শুরু হয় এবং শেষ হয় যে উপাদান তা অতিক্রম 1.
সুতরাং উপাদান যে আমরা চেক চলুন এই এক,
এবং তারপর যখন আমরা শুরু আপডেট, আমরা শুরুর 0 টি + 1/2 হতে আপডেট করছি,
যা আমাদের শেষ শুরু হচ্ছে এই উপাদান দিয়ে ফিরে যাচ্ছে.
>> সুতরাং আমরা এবং উপর আবার একই উপাদান চেক করছি.
তাই এই ক্ষেত্রে যেখানে প্রতি recursive কল আসলে কিছু আপডেট করতে হবে.
তাই আমরা শুরু + শেষ / 2 + 1 টি, বা অন্য কোন প্রয়োজন একটি কেস আছে
যেখানে আমরা আসলে শুরু আপডেট করছি না.
প্রত্যেকেরই যে দেখতে?
ঠিক আছে.
কেউ কি এই সমাধান বা কোনো মতামত আরো প্রশ্ন আছে?
ঠিক আছে. কেউ কি কোনো সমাধান যে সমস্ত আমরা তাকান পারেন পুনরাবৃত্ত করেছেন?
সব কি আমরা এটি recursively করবেন?
অথবা আমি অনুমান যদি আপনি তার খোলা থাকে, তাহলে আপনি আপনার আগের এক ওভাররাইড করা থাকতে পারে.
কি স্বয়ংক্রিয়ভাবে সংরক্ষণ করব? আমি ইতিবাচক নই.
কেউ কি পুনরাবৃত্ত করেছেন?
আমরা একসাথে এটা মাধ্যমে যদি পদব্রজে ভ্রমণ না করতে পারেন.
একই ধারণা করা হচ্ছে.
সমাধান পুনরাবৃত্ত.
আমরা মূলত একই ধারণা করতে যাচ্ছেন
যেখানে আমরা অ্যারের নতুন শেষ ট্র্যাক এবং অ্যারের নতুন শুরুর রাখতে চান
এবং না যে বহুবার.
এবং যদি আমরা কি শুরু এবং শেষের কখনো ছেদ হিসাবে করছেন অবগত থাকার,
তারপর আমরা এবং খুঁজে পান না এটা মিথ্যা আমরা ফিরে আসতে পারেন.
তাই আমি যে কিভাবে করব? যে কেউ পরামর্শ সম্পর্কে জন্য অথবা থামা কোড আছে?
[ছাত্রদের] যখন একটি লুপ কি. >> হ্যাঁ.
আপনি একটি লুপ করতে যাচ্ছি.
>> আপনি কি কোড আমি থামা পারে আছে, বা আপনি কি ছিল সুপারিশ যাচ্ছে?
[ছাত্রদের] আমি তাই মনে করি. >> সমস্ত অধিকার. এর ফলে এই জিনিষ সহজ. আপনার নাম কি ছিল?
[ছাত্রদের] লুকাস.
পরিবর্ধন ও পরিবর্তন তালিকা 1. ঠিক আছে.
নিম্ন কি আমরা আগে শুরু হয়.
আপ কি আমরা বেশ আগে বলা শেষ হয় না.
বাস্তবিক, অ্যারের মধ্যে এখন শেষ হয়. এটি একটি উপাদান আমাদের বিবেচনা করা উচিত.
তাই কম হয় 0 আপ, একটি অ্যারের আকার - 1 টি,
এবং এখন আমরা, looping এবং আমরা পরীক্ষণের হয় -
আমি অনুমান আপনি এটি ভিতর দিয়ে হেটে যেতে পারেন.
কী ছিল আপনার চিন্তার মাধ্যমে এই? আপনার কোড এর মাধ্যমে আমাদের হাঁটুন.
[ছাত্রদের] শিওর. মাঝখানে খড়ের গাদা মান তাকান এবং সুই এটি তুলনা.
তাই আপনি যদি এটা আপনার সুই তার চেয়ে অনেক বেশী, তাহলে কি করতে চান - ওহ আসলে, যে পিছন দিকে হওয়া উচিত.
আপনি ডান অর্ধেক বাতিল করতে চান যাচ্ছে, এবং করছি যাতে হাঁ, যে পথ হওয়া উচিত.
[Bowden] সুতরাং এই কম হওয়া উচিত? না যে আপনি কি বলেন? >> [ছাত্রদের] হ্যাঁ.
[Bowden] ঠিক আছে. কম.
তাই আপনি যদি কি আমরা এ খুঁজছেন তা কি আমরা চাই চেয়ে ছোট,
তারপর হাঁ, আমরা বাম অর্ধেক বাতিল করতে চান,
যার অর্থ হল আমরা সবকিছু আমরা বিবেচনাধীন আপডেট
দ্বারা পরিবর্তনশীল কম অ্যারের অধিকার.
এই ভাল দেখায়.
আমি মনে করি এটি একই বিষয় যে আমরা আগের জানিয়েছেন আছে,
যদি কম হয় যেখানে 0 এবং 1 আপ হয়, তাহলে কম + আপ / 2 পর্যন্ত একই জিনিস আবার সেট করা যাচ্ছে না.
>> এমনকি যদি সেই কেস না, এটা এখনও খুব অন্তত আরো দক্ষ
শুধু উপাদান সরিয়ে আমরা লাগছিল যা আমরা জানি ভুল.
তাই কম + আপ / 2 + 1 টি - >> [ছাত্রদের] যে অন্য উপায় হওয়া উচিত.
[Bowden] অথবা এই হওয়া উচিত - 1 এবং অন্য এক + 1 টি হওয়া উচিত.
[ছাত্রদের] এবং একটা ডবল না করে সাইন সমান. >> [Bowden] হ্যাঁ.
[ছাত্রদের] হ্যাঁ.
ঠিক আছে.
এবং অবশেষে এখন, যে আমরা এই + 1 টি আছে - 1 জিনিস,
এটা - এটা হতে পারে না - এটা কখনও সম্ভব কম মূল্য আপ তুলনায় এবং শেষ?
আমি মনে করি একমাত্র উপায় যে ঘটতে পারে - এটা কি সম্ভব? >> [ছাত্রদের] আমি জানি না.
কিন্তু যদি সেটা ছেঁটে ফেলা এবং তারপর পায় বিয়োগ যে 1 এবং তারপর - >> হ্যাঁ.
[ছাত্রদের] সম্ভবত এটা বিশৃঙ্খলার সৃষ্টি করতে হবে.
আমি মনে করি এটা ভালো কারণ শুধুমাত্র হওয়া উচিত
জন্য এটি শেষ কম তারা সমান হতে হবে, আমি মনে করি.
কিন্তু যদি তারা সমান, তাহলে আমরা দিয়ে শুরু করতে যখন লুপ কাজ করবে না
এবং আমরা ফিরে মান থাকবে. তাই আমি মনে করি আমরা এখন ভাল.
উল্লেখ্য, যে যদিও এই সমস্যা নেই recursive,
ধারণা একই ধরনের আবেদন যেখানে আমরা কিভাবে এই সহজেই নিজেই ধার দেখতে পারেন
একটি সত্য যে আমরা বেশী বেশী করছি সূচক আবার আপডেট দ্বারা recursive সমাধান,
আমরা ছোট ছোট সমস্যা তৈরি হয়, আমরা অ্যারের একটি সাবসেট উপর মনোযোগ নিবদ্ধ করে থাকেন.
[ছাত্রদের] যদি কম হয় 0 আপ হয় এবং 1, তারা উভয় 0 টি + 1/2, যা 0 যেতে হবে,
1 - এবং তারপর এক + 1 টি হবে, এক হতে হবে.
[ছাত্রদের] আমরা সমতা পরীক্ষণ?
আমাকে যদি এক মধ্যম আসলে সুই?
আমরা বর্তমানে যে করছি করছেন না? ওহ!
যদি it's -
হ্যাঁ. আমরা ঠিক না ডাউন এখানে পরীক্ষা করতে পারেন না কারণ এর দেওয়া প্রথম মধ্যম বলে -
[ছাত্রদের] এটা আসলে এর বাউন্ড দূরে নিক্ষেপ করতে চান না.
তাই আপনি যদি বাউন্ড বাতিল, আপনি এটি প্রথম বা যাই হোক না কেন চেক আছে.
আহ্. হাঁ. >> [ছাত্রদের] হ্যাঁ.
তাই এখন আমরা এক দিকে তাকিয়ে আমরা বর্তমানে অধ দূরে আছে,
যার মানে আমরা এখন যাও এছাড়াও আছে প্রয়োজন
যদি (খড়ের গাদা [(কম + আপ) / 2] == সুই) তারপর, আমরা সত্য ফিরে আসতে পারেন.
এবং কিনা আমি ঠিক রাখা বা অন্যথায় যদি, এটা আক্ষরিক অর্থ একই জিনিস
কারণ এই ফিরে সত্য হবে.
তাই আমি আর যদি করা, কিন্তু এটা কোন ব্যাপার না কিন্তু করব.
>> তাই অন্য কারো যদি এই, অন্যথায় এই, এবং এই একটি সাধারণ জিনিস আমি না
যেখানে এমনকি যদি কেস যেখানে সবকিছু এখানে ভাল,
ভালো কম আপ অধিক হতে পারে, এটা যে সত্য কিনা আমার মূল্য যুক্তি না.
তাই আপনি ভাল বলতে সময় কম কম বা তার সমান হতে পারে
বা যখন কম কম
তাই যদি তারা কখনও সমান অথবা কম যাও বর্জন করা হবে,
তারপর আমরা এই লুপ বিরতি আউট করতে পারেন.
প্রশ্ন, উদ্বেগ, মতামত?
ঠিক আছে. এই ভাল দেখায়.
এখন আমরা সাজানোর কাজ করতে চান.
আমরা যদি আমার দ্বিতীয় সংস্করণ যান, আমরা এই একই সংখ্যা দেখতে,
কিন্তু এখন তারা সাজানো ক্রম হয় না.
এবং আমরা সাজানোর n log n হে কোন এলগরিদম ব্যবহার করে বাস্তবায়ন করতে চান.
সুতরাং যা আলগোরিদিম আপনি মনে করেন আমরা এখানে বাস্তবায়ন করা উচিত? >> [ছাত্রদের] মার্জ সাজান.
[Bowden] হ্যাঁ. সাজানোর মার্জ হয় হে (n log n), যাতে আমরা কি করতে যাচ্ছেন.
এবং সমস্যার সুন্দর অনুরূপ হবে,
যেখানে সহজে এটি একটি recursive সমাধান নিজেকে ধার দেয়.
আমরা একটি সমাধান পুনরাবৃত্ত চিন্তা যদি আমরা করতে চান করতে পারেন,
কিন্তু recursion সহজ এবং এখানে আমরা recursion করা উচিত হবে.
আমি অনুমান আমরা প্রথম একত্রীকরণ সাজানোর ভিতর দিয়ে হেটে যেতে হবে,
যদিও ইতিমধ্যে সেখানে একটি একত্রীকরণ সাজানোর উপর অতীব সুন্দর ভিডিও. [হাস্য]
সুতরাং সাজান আছে একত্রীকরণ - আমি এই কাগজের এত am নাশক.
ওহ, কেবল এক বাম আছে.
সুতরাং একত্রীকরণ.
ওহ, 1, 3, 5.
ঠিক আছে.
মার্জ দুটি পৃথক অ্যারে লাগে.
পৃথকরূপে যারা দুই অ্যারে উভয় সাজানো হয়.
তাই এই অ্যারে, 1, 3, 5, সাজানো. এই অ্যারে, 0, 2, 4, সাজানো.
এখন কি করবেন একত্রীকরণ একটি অ্যারের যে নিজেই সাজানো সেগুলি একত্রিত হয়.
সুতরাং আমরা মাপ 6 শ্রেণীবিন্যাস যে এর ভিতরে এই উপাদান আছে যাচ্ছে চান
এ আদেশ অনুসারে সাজানো.
>> তাই আমরা যে এই দুটি অ্যারে সাজানো হয় সুবিধা গ্রহণ করতে পারেন
লিনিয়ার সময় করি,
রৈখিক সময় অর্থ যদি এই অ্যারে আকার হল x এবং এই আকার y,
তারপর মোট আলগোরিদিম হে (x + y) করা উচিত. ঠিক আছে.
তাই পরামর্শ.
[ছাত্রদের] আমরা বাম থেকে শুরু করা যায়নি?
সুতরাং আপনি প্রথম 0 রাখা এবং তারপর 1 এবং তারপর পাবেন এখানে আপনি 2 করেন.
এটা ভালো আপনি একটি ট্যাব যে অধিকার আছে পরিবর্তনশীল এর মত. >> [Bowden] হ্যাঁ.
এই অ্যারে উভয় যদি আমরা শুধুমাত্র leftmost উপাদান ফোকাস.
কারণ উভয় অ্যারে অনুসারে বাছাই করা হয়, আমরা জানি যে, এই উপাদান 2
হয় অ্যারের মধ্যে ক্ষুদ্রতম উপাদান.
সুতরাং তার মানে যারা 2 উপাদানের 1 আমাদের মার্জ অ্যারের মধ্যে ক্ষুদ্রতম উপাদান হতে হবে.
এটা ঠিক যে ক্ষুদ্রতম এই মুহুর্তে এই সময় এক.
সুতরাং আমরা 0, নিতে বাম এটি সন্নিবেশ কারণ 0 কম 1,
তাই 0, নিতে আমাদের প্রথম অবস্থান মধ্যে সন্নিবেশ করুন, এবং তারপর আমরা এই আপডেট
যাও এখন প্রথম উপাদান ফোকাস.
এবং এখন আমরা পুনরাবৃত্তি.
তাই এখন আমরা 2 এবং তুলনা 1. 1 টি ছোট হয়, তাই আমরা 1 সন্নিবেশ করব.
আমরা এই লোক নির্দেশ করার জন্য এই পয়েন্টার আপডেট.
এখন আমরা আবার এটা না, তাই 2. এই, এই 2, 3 তুলনা আপডেট করতে হবে.
এই আপডেটের পরে, 4 এবং 5.
সুতরাং যে একত্রীকরণ.
>> এটা স্পষ্ট যে চমত্কার এটা রৈখিক সময় যেহেতু আমরা ঠিক প্রতিটি উপাদান জুড়ে একবার যেতে হবে.
এবং যে রূপায়ণকারী একত্রীকরণ সাজানোর এই করছে যাও বৃহত্তম পদক্ষেপ.
এবং এটি যে হার্ড না.
একটি দম্পতি জিনিস সম্পর্কে চিন্তা করা হয় let এর বলতে আমরা 1, 2, 3, 4, 5, 6 মার্জ হয়েছে.
এই ক্ষেত্রে আমরা দৃশ্যকল্প যেখানে এই এক ছোট করা হয় শেষ,
তারপর আমরা এই পয়েন্টার আপডেট, এই এক ছোট হতে চলেছে, এই আপডেট,
এই ছোট কাজ, এবং এখন আপনাকে চিনতে আছে
আসলে যখন আপনি উপাদানের সঙ্গে তুলনা করেছেন আউট চালানোর জন্য.
যেহেতু ইতিমধ্যেই আমরা এই সমগ্র অ্যারে ব্যবহার,
এই অ্যারের মধ্যে সবকিছু এখন শুধু এখানে ঢোকানো হয়.
সুতরাং আমরা যদি কখনও বিন্দু যেখানে সম্পূর্ণরূপে আমাদের অ্যারে এক মার্জ করা হয় ইতিমধ্যে মধ্যে চালানো,
তারপর আমরা সব অ্যারের অন্যান্য উপাদান গ্রহণ এবং অ্যারের শেষ সেগুলি সন্নিবেশ করুন.
সুতরাং আমরা মাত্র 4, 5 সন্নিবেশ করতে পারেন, 6. ঠিক আছে.
এই কথাটিই যাও জন্য সতর্ক হওয়া.
প্রবর্তনকারী যে ধাপ 1 উচিত.
উপর ভিত্তি করে মার্জ করুন তারপর বাছাই, এটা 2 ধাপ, 2 মূর্খ পদক্ষেপ.
চলুন শুরু করা যাক ঠিক এই অ্যারে দিতে.
সুতরাং সাজানোর একত্রীকরণ, পদক্ষেপ 1 যাও recursively আংশিক অ্যারের মধ্যে বিরতি হয়.
তাই অর্ধেক মধ্যে এই অ্যারে বিভক্ত.
আমরা এখন 4, 15, 16, 50 এবং 8, 23, 42, 108 আছে.
এবং এখন আমরা এটা আবার কি এবং আমরা অর্ধ মধ্যে এই বিভক্ত.
আমি এই দিকে এটি ঠিক করব.
তাই 4, 15 এবং 16, 50.
এখানে আমরা ধরে একই জিনিস করে.
এবং এখন আমরা অর্ধেক করে সেটিকে আবার বিভক্ত.
এবং আমরা 4, 15, 16, 50 আছে.
যাতে আমাদের বেস কেস.
একবার অ্যারে আকার 1 তাহলে, বধির সঙ্গে আমরা অর্ধ মধ্যে থামাতে.
>> আমরা কি এখন এই সঙ্গে করবেন?
আমরা শেষ পর্যন্ত এই এছাড়াও 8, 23, 42, 108 এবং এ ভাঙ্গিয়া হবে.
তাই এখন যে আমরা এই সময়ে করছি এখন, পইঠা একত্রীকরণ সাজানোর দুটি ঠিক হয় তালিকা জোড়া মার্জ.
তাই আমরা এই একত্রীকরণ করতে চান. আমরা শুধু একত্রীকরণ কল.
আমরা জানি একত্রীকরণ সাজানো ক্রম এইসব ফিরে আসবে.
4, 15.
এখন আমরা এইসব একত্রীকরণ করতে চান, এবং যে অনুক্রমে সাজানো সাথে একটি তালিকা দেবে,
16, 50.
আমরা যারা একত্রীকরণ - 8, 23 এবং 42, 108 - আমি লিখতে পারি না.
সুতরাং আমরা মার্জ জোড়া একবার আছে.
এখন আমরা আবার একত্রীকরণ.
নিজেই যে এই তালিকার প্রতিটি সাজানো হয় বিজ্ঞপ্তি,
এবং তারপর আমরা শুধু এই তালিকা আকার 4 একটি তালিকা পেতে যা সাজানো হয় মার্জ করতে পারবেন
এবং এই দুটি তালিকা আকার 4 একটি তালিকা অনুসারে সাজানো হয় পেতে একত্রীকরণ.
এবং পরিশেষে, আমরা মাপ 8 এক তালিকা অনুসারে সাজানো হয় যে পেতে যারা আকার 4 দুটি তালিকা মার্জ করতে পারবেন.
যাতে এই সামগ্রিক n log n দেখতে, ইতিমধ্যেই আমরা দেখেছি যে একত্রীকরণ রৈখিক হয়,
তাই যখন আমরা এই মার্জ যাতে একত্রীকরণ সামগ্রিক খরচ মত আচরণ, করছি
এই দুটি তালিকা জন্য কারণ হয় মাত্র 2 -
বা ভাল, এটা n হে, কিন্তু n এখানে শুধুমাত্র এই উপাদান 2, তাই 2.
এবং এই 2 2 হতে পারে এবং এই 2 2 হতে হবে এবং এই 2 2 হবে,
তাই মার্জ যে আমরা যা করতে হবে সব জুড়ে, আমরা শেষ পর্যন্ত হবে না.
+ 2 + 2 + 2 2 8 লেগেছে হয়, যা হবে,
তাই এই সংকলনের মধ্যে সমন্নয় খরচ n হল.
এবং তারপর একই জিনিস এখানে.
আমরা এইসব 2 একত্রীকরণ, তাহলে এই 2, করব এবং পৃথকভাবে এই একত্রীকরণ চার অপারেশন নিতে হবে,
এই একত্রীকরণ চার অপারেশন নিতে, কিন্তু এগুলোর মধ্যে সব হবে আবার,,
আমরা শেষ পর্যন্ত মার্জ n মোট জিনিষ, এবং তাই এই পদক্ষেপ হবে লাগে.
এবং তাই প্রতিটি স্তরের n হচ্ছে মার্জ উপাদান লাগে.
>> এবং কিভাবে অনেক স্তর আছে?
প্রতিটি স্তরে, আমাদের অ্যারের আকার 2 দ্বারা বৃদ্ধি.
এখানে আমাদের অ্যারে আকার 1 হয় এখানে, তারা আকার 2 হয়ে এখানে, তারা আকার 4 হন,
এবং পরিশেষে, তারা 8 আকার হয়ে.
সুতরাং যেহেতু এটি দ্বিত্ব হয়, going to লগ অফ n এই মাত্রা একটি মোট করা আছে.
তাই সঙ্গে লগ n মাত্রা, প্রতিটি স্তর গ্রহণ n মোট অপারেশন,
আমরা একটি n log n আলগোরিদিম পেতে.
প্রশ্ন?
মানুষ ইতিমধ্যে কিভাবে এই প্রয়োগ উপর অগ্রগতি হয়েছে?
ইতিমধ্যে একটি রাষ্ট্র যেখানে যেকেউ আমি বৈঠাচালনা তাদের কোড আপ করতে পারেন?
আমি এক মিনিট সময় দিতে পারেন.
এই এক থেকে দীর্ঘতর হতে যাচ্ছে.
আমি অত্যন্ত আবৃত্তি করা সুপারিশ -
আপনি একত্রীকরণ জন্য recursion না আছে
কারণ একত্রীকরণ জন্য recursion না, আপনি বিভিন্ন আকারের একটি গুচ্ছ পাস আছে চলুন.
আপনি কিন্তু, এটা বিরক্তিকর হতে পারে.
কিন্তু নিজেকে সাজানোর জন্য recursion বেশ সহজ.
আপনি আক্ষরিক শুধু বাম অর্ধেক উপর সাজানোর, কল অধিকার অর্ধেক উপর সাজান. ঠিক আছে.
কেউ কিছু আমি এখনো থামা করতে পারেন?
অন্যথায় আমি একটি মিনিট দেব.
ঠিক আছে.
কেউ কিছু আমরা সঙ্গে কাজ করতে পারেন?
অন্যথায় আমরা এই সঙ্গে কাজ এবং তারপরে সেখান থেকে প্রসারিত.
>> আরো কেউ এই যে আমি থামা করতে পারেন?
[ছাত্রদের] হ্যাঁ. আপনি খনি থামা পারেন. >> সমস্ত অধিকার.
হ্যাঁ!
[ছাত্রদের] অবস্থার অনেক ছিল. >> ওহ, অঙ্কুর. আপনি যা করতে পারেন -
[ছাত্রদের] আমি এটি সংরক্ষণ আছে. >> হ্যাঁ.
সুতরাং আমরা একত্রীকরণ আলাদাভাবে করবেন না.
ওহ, কিন্তু এটা যে খারাপ না.
ঠিক আছে.
সুতরাং সাজানোর নিজেই ঠিক mergeSortHelp কলিং.
আমাদের ব্যাখ্যা কি mergeSortHelp আছে.
[ছাত্রদের] MergeSortHelp কাছাকাছি দুটি প্রধান ধাপ আছে,
যা অ্যারের প্রতিটি অর্ধেক এবং তারপর বাছাই দুইটাই একত্রীকরণ হয়.
[Bowden] ঠিক আছে, তাই সম্পর্কে একটি দ্বিতীয় দিন.
আমি এই মনে - >> [ছাত্রদের] আমি প্রয়োজন -
হাঁ. আমি কিছু করছি অনুপস্থিত.
একত্রীকরণ ইন, আমি বুঝতে পারি যে আমি একটি নতুন অ্যারে নির্মাণ করার প্রয়োজন
কারণ আমি স্থানে করা যেত না. >> হ্যাঁ. আপনি না করতে পারেন. ঠিক করুন.
[ছাত্রদের] তাই আমি একটি নতুন অ্যারে নির্মাণ.
আমি পুনরায় পরিবর্তন একত্রীকরণ শেষে ভুলে গেছি.
ঠিক আছে. আমরা একটি নতুন অ্যারে প্রয়োজন.
একত্রীকরণ সাজানোর মধ্যে, এই প্রায় সবসময় সত্য.
একটি ভাল অ্যালগোরিদম সময় ভিত্তিক মূল্যের পার্ট
হয় প্রায় সর্বদা আরো বিট মেমরি ব্যবহার করা প্রয়োজন.
তাই এখানে, সেটা ব্যাপার নয় আপনি কি সাজানোর একত্রীকরণ,
আপনি অবশ্যম্ভাবীরূপে কিছু অতিরিক্ত মেমরি ব্যবহার করতে হবে.
তিনি একটি নতুন অ্যারে তৈরি.
এবং তারপর আপনি বলতে শেষে আমরা শুধু আসল অ্যারের মধ্যে নতুন অ্যারে কপি করা আবশ্যক.
[ছাত্রদের] আমি তাই মনে করি, হাঁ.
আমি যদি যে রেফারেন্স বা যাহা দ্বারা গণনা শর্তাবলী কাজ জানি না -
হাঁ, এটা কাজ করবে. >> [ছাত্রদের] ঠিক আছে.
আপনি কি এই চলমান চেষ্টা? >> [ছাত্রদের] না, এখনো না. >> ঠিক আছে.
এটি চালানোর চেষ্টা করুন, এবং তারপর আমি এটা সম্পর্কে একটি দ্বিতীয় কথা বলতে পারবেন.
[ছাত্রদের] আমি সব ফাংশন এগুলির নমুনা এবং সবকিছু করার প্রয়োজন আছে যদিও,,, ঠিক?
ফাংশন এগুলির নমুনা. হ্যাঁ - ওহ, আপনি ভালো বলতে চাইছেন.
সাজান mergeSortHelp হয় কলিং.
>> তাই অর্ডার সাজানোর জন্য mergeSortHelp কল মধ্যে, হয় mergeSortHelp অবশ্যই সংজ্ঞায়িত করা হয়েছে
সাজানোর আগে বা আমরা কেবল প্রোটোটাইপ প্রয়োজন. শুধু যে কপি পেস্ট করুন.
এবং একইভাবে, mergeSortHelp একত্রীকরণ আহ্বান করা হয়,
কিন্তু এখনো একত্রীকরণ সংজ্ঞায়িত করা হয়েছে, তাই আমরা ঠিক যাক পারেন mergeSortHelp জানা
যে যে এর কি একত্রীকরণ অনুরূপ যাচ্ছে, এবং যে যে.
সুতরাং mergeSortHelp.
আমরা একটি বিষয় এখানে আছে যেখানে আমরা কোন বেস কেস আছে.
MergeSortHelp recursive হয়, যাতে কোনো recursive ফাংশন
মৌলিক ক্ষেত্রে কিছু সাজানোর যখন recursively নিজেই কলিং বন্ধ করার জন্য জানা প্রয়োজন হবে.
না কি আমাদের বেস কেস এখানে চালু করা? হাঁ.
[ছাত্রদের] যদি আকার হয় 1? >> [Bowden] হ্যাঁ.
যেমন আমরা দেখেছি অধিকার আছে, আমরা বধির অ্যারে থামানো
একবার আমরা অ্যারে আকার 1, যা অবশ্যম্ভাবীরূপে নিজেদের মধ্যে সাজানো হয় না.
তাই যদি 1 আকার সমান, আমরা জানতে পারি যে অ্যারের ইতিমধ্যেই সাজানো,
তাই আমরা ফিরে আসতে পারেন.
>> যে অকার্যকর লক্ষ্য করুন, যাতে আমরা বিশেষ কিছু না ফিরে না, আমরা ফিরে আসতে.
ঠিক আছে. যাতে আমাদের বেস কেস.
আমি অনুমান আমাদের বেস মামলা হতে যদি আমরা ঘটতে মাপ 0 শ্রেণীবিন্যাস মার্জ করা যেতে পারে,
আমরা সম্ভবত কিছু সময়ে থামাতে চান,
তাই আমরা ঠিক মাপ চেয়ে কম 2 বা কম বা সমান 1 বলতে পারেন
যাতে এই এখন কোনো অ্যারের জন্য কাজ করবে.
ঠিক আছে.
যাতে আমাদের বেস কেস.
এখন আপনি কি একত্রীকরণ মাধ্যমে আমাদের পদব্রজে ভ্রমণ করতে চান?
কি সব ক্ষেত্রে এই কথা বলছেন কি?
এখানে আপ, আমরা একই ধারণা করছি, -
[ছাত্রদের] আমি প্রয়োজন সব mergeSortHelp কল সঙ্গে আকার পার করা হবে.
আমি একটি অতিরিক্ত প্রাথমিক হিসাবে যোগ আকার এবং এটা এখানেই আছে, মাপ / 2 এর মত না.
[Bowden] ওহ, আকার / 2, আকার / 2. >> [ছাত্রদের] হ্যাঁ, তেমনি উপরের ফাংশন হিসাবে ভাল.
[Bowden] এখানে? >> [ছাত্রদের] শুধু আকার. >> [Bowden] ওহ. ফাইলের আকার, আয়তন? >> [ছাত্রদের] হ্যাঁ.
[Bowden] ঠিক আছে.
আমাকে একটি দ্বিতীয় জন্য মনে করি.
আমরা কি কোনো সমস্যা পাতিত?
আমরা সর্বদা 0 হিসাবে বাম চিকিত্সা. >> [ছাত্রদের] নং
খুব ভুল. দুঃখিত. এটা শুরু করা উচিত. হাঁ.
[Bowden] ঠিক আছে. আমি যে ভাল.
এবং শেষ. ঠিক আছে.
তাই এখন আপনি একত্রীকরণ মাধ্যমে আমাদের পদব্রজে ভ্রমণ করতে চান? >> [ছাত্রদের] ঠিক আছে.
আমি এই নতুন অ্যারে মাধ্যমে শুধু হাঁটা যে আমি তৈরি করেছি.
এর আকার হয় অ্যারের অংশ আকার যে আমরা করতে চান সাজানো যাও
এবং উপাদান যে আমি নতুন অ্যারে পদক্ষেপ রাখা উচিত খুঁজে চেষ্টা.
সুতরাং যা করার জন্য প্রথমে, আমি যদি অ্যারের বাম অর্ধেক কোন উপাদান আছে চলতে চেকআউট করছি,
এবং যদি না হয়, তাহলে আপনি অন্য যে অবস্থা, যা শুধু বলে যাও নামা
ঠিক আছে, এটি ডান অ্যারের মধ্যে, হতে পারে এবং আমরা newArray বর্তমান সূচক মধ্যে রেখে দেব আবশ্যক.
>> অন্যথায় এবং তারপর, আমি যদি এ অ্যারে ডানদিকে সমাপ্ত না চেকআউট করছি,
সেক্ষেত্রেও আমি বাম রাখা.
আসলে প্রয়োজন নাও হতে পারে. আমি নিশ্চিত না.
কিন্তু যাইহোক, অন্য দুটি চেক দুটি যা বাম বা ডানদিকে ছোট.
প্রতিটি ক্ষেত্রে এবং এছাড়াও, আমি যেটা প্লেসহোল্ডার আমি বাড়ায় বৃদ্ধিশীল করছি.
[Bowden] ঠিক আছে.
যে দেখতেও ভাল.
কেউ কি মতামত বা উদ্বেগ বা প্রশ্ন থাকে?
তাই চার ক্ষেত্রে যে আমরা শুধু অস্তিত্ব আছে জিনিস আনা - বা এটি পাঁচটি মত দেখাচ্ছে -
কিন্তু আমরা কি বাম অ্যারের জিনিস আমরা মার্জ করার রান আউট করেনি বিবেচনা আছে,
সঠিক কিনা সে ব্যাপারে আমরা অ্যারে যাও মার্জ করার রান আউট করেনি -
আমি কিছুই নির্দেশ করে না.
তাই কিনা বাম অ্যারের জিনিষ চালানোর করেনি আউট বা ডান অ্যারের জিনিস রান আউট করেনি.
সেগুলো হল দুটি মামলা.
আমরা কিনা বাম আর ডান জিনিস কম মামুলি ক্ষেত্রে প্রয়োজন.
তারপর আমরা বাম বস্তু নির্বাচন করার ব্যাপারে.
সেগুলো হল ক্ষেত্রে.
সুতরাং এই অধিকার ছিল, যাতে যে.
এরে বাকি. এটি 1, 2, 3. ঠিক আছে. তাই হ্যাঁ, যারা হয় চারটি জিনিস আমরা করতে চাইতে পারেন.
এবং আমরা একটি সমাধান পুনরাবৃত্ত পুনরাবৃত্তি করা হবে না.
আমি না করার পরামর্শ দিচ্ছি -
সাজানোর মার্জ একটি ফাংশন যা উভয় recursive লেঙ্গুড় না একটি উদাহরণ,
এটা লেঙ্গুড় recursive করা সহজ নয়,
কিন্তু এটা পুনরাবৃত্ত করা খুব সহজ না.
এটি খুবই সহজ.
একত্রীকরণ সাজানোর এই বাস্তবায়ন,
কোন ব্যাপার আপনি কি করবেন একত্রীকরণ,, আপনি একত্রীকরণ নির্মাণ করতে যাচ্ছেন.
>> তাই মার্জ সাজানোর একত্রীকরণ উপরে নির্মিত recursively শুধুমাত্র এই তিনটি লাইন.
Iteratively, এটা আরো বিরক্তিকর এবং আরো কঠিন সম্পর্কে চিন্তা করা.
কিন্তু যে এটি লেঙ্গুড় mergeSortHelp থেকে recursive না বিজ্ঞপ্তি - যখন এটি নিজেই কল -
এটি এখনও এই recursive কল আয় পরে কিছু করার প্রয়োজন.
তাই এই স্ট্যাকের ফ্রেম এমনকি এই কলিং পরে বিদ্যমান অবিরত আবশ্যক.
এবং তারপর যখন আপনি এই কল, স্ট্যাকের ফ্রেম অস্তিত্ব বজায় আবশ্যক
কারণ পরে কল, আমরা এখনও একত্রীকরণ প্রয়োজন.
এবং এটা এই লেঙ্গুড় recursive করা nontrivial.
প্রশ্ন?
ঠিক আছে.
তাই ফিরে গিয়ে বাছাই - উহু, দুটি জিনিস আমি দেখাতে চান তা আছে. ঠিক আছে.
সাজানোর ফিরে যাওয়া, আমরা এই দ্রুত করব.
বা অনুসন্ধান. সাজান? সাজান. হাঁ.
ধরণের সূত্রপাত ফিরে যাওয়া.
আমরা একটি অ্যালগরিদম যে কোনো প্রকারের অ্যারের অ্যালগোরিদম ব্যবহার করে তৈরি করতে চান
মধ্যে n হে.
তাই কিভাবে এটি সম্ভব? কেউ কি কোনো সাজান আছে -
আমি আগে hinted -
যদি আমরা সম্পর্কে করছি থেকে n log n n হে উন্নত যাও,
আমরা আমাদের এলগরিদম সময়-এ উন্নত করা,
যার মানে কি আমরা যাও যাও যাও যে জন্য সাইন আপ করতে করতে যাচ্ছে?
স্পেস [ছাত্রদের]. >> হ্যাঁ. আমরা আরো স্থান ব্যবহার করা হবে চলুন.
এমনকি শুধুমাত্র আরও জায়গা, এটা ব্যাখ্যা মূলকভাবে আরো স্থান.
তাই আমি মনে করি আলগোরিদিম এই ধরনের কিছু ছদ্ম, ছদ্ম polynom -
ছদ্ম - আমি মনে রাখতে সক্ষম না. ছদ্ম কিছু.
কিন্তু এর কারণ আমরা এত জায়গা ব্যবহার করতে হবে
যে এই সাধনযোগ্য কিন্তু না বাস্তবসম্মত.
>> এবং কিভাবে আমরা এই অর্জন না?
আমরা যদি এই অর্জন আমরা গ্যারান্টি পারেন যে কোনো অ্যারের মধ্যে বিশেষ উপাদান
হল নীচের একটি নির্দিষ্ট মাপ.
সুতরাং এর দেওয়া ঠিক যে সাইজ 200,
একটি অ্যারের মধ্যে কোনো উপাদান নীচে আকার 200.
এবং এই আসলে খুবই বাস্তবসম্মত.
আপনি একটি অ্যারের যে আপনি এটা জানেন সবকিছুই খুব সহজে থাকতে পারে
কিছু সংখ্যার চেয়ে কম হবে.
যদি আপনি কিছু একেবারে বৃহদায়তন ভেক্টর বা কিছু আছে যাচ্ছে
কিন্তু আপনি কি জানেন সবকিছু 0 এবং 5 এর মধ্যে হতে যাচ্ছে,
তারপর এটি দ্রুত এই কাজ করা হচ্ছে.
এবং উপাদানের কোনো বাঁধাই 5,
এই বাউন্ড, তাই যে কতটা মেমরি ব্যবহার করা হবে আপনি চলুন.
সুতরাং বাউন্ড হয় 200.
তত্ত্ব ইন সবসময়ই একটি বাউন্ড থেকে শুধুমাত্র একটি পূর্ণসংখ্যা যাও 4 বিলিয়ন পর্যন্ত হতে পারে,
কিন্তু যে তারপর আমরা স্থান ব্যবহার করা চাই যেহেতু এর অবাস্তব
4 বিলিয়ন ক্রম. সুতরাং এটা অবাস্তব.
কিন্তু এখানে আমরা আমাদের বাউন্ড বলবো হল 200.
n হে এটা করাতে কৌতুক হয় আমরা অন্য অ্যারে বলা আকারের সংখ্যা আবদ্ধ করা.
তাই আসলে, এই জন্য একটি শর্টকাট - আসলে আমি যদি এই ঝনঝন শব্দ আছে না.
কিন্তু জিসিসি কমপক্ষে ২ সালে - I'm জাহিরকারী ঝনঝন খুব আছে -
এই মাত্র সমগ্র অ্যারের 0 সেঃ হতে আরম্ভ হবে.
সুতরাং আমি যদি তা করতে না চান, তাহলে আমি আলাদাভাবে জন্য কিছু করতে পারে (int i = 0;
তোমার <আবদ্ধ; i + +) এবং সংখ্যা [i] = 0;
তাই এখন 0 সবকিছু সক্রিয়া করা হয়.
আমি আমার অ্যারের উপর বারবার,
এবং আমি কি করছি আমি প্রতিটি সংখ্যা বেড়ে চলেছে করছি - এর নিচে এখানে যাওয়া যাক.
আমরা 4, 15, 16, 50, 8, 23, 42, 108 আছে.
আমি কি গণনা করা হয় যারা উপাদান প্রতিটি ঘটনার সংখ্যা.
যাক প্রকৃতপক্ষে এখানে কিছু পুনরাবৃত্তি সঙ্গে যুক্ত করার একটি দম্পতি আরো.
তাই মান আমরা এখানে আছে, যে মান যাও অ্যারে হতে [i] যাচ্ছে.
সুতরাং Val 4 বা 8 যাই হোক না কেন বা হতে পারে.
এবং এখন আমি যে মান যত আমি দেখা করেছি গণনা করছি,
তাই সংখ্যা [Val] +;
পরে এই জন্য এটা করা হয়, এই সংখ্যা এবং 0001 এর মত চেহারা হবে.
চলুন শুরু করা যাক সংখ্যা না [Val] - + 1 টি আবদ্ধ.
>> এখন যে শুধু সত্য যে আমরা 0 থেকে শুরু করছেন জন্য অ্যাকাউন্ট যাও.
তাই আপনি যদি যাও আমাদের 200 বৃহত্তম সংখ্যা হতে হবে,
তারপর 0 থেকে 200 201 জিনিষ হয়.
সংখ্যা, তাই এটি 00001 ভালো কারণ আমরা এক আছে 4 সন্ধান করব.
তারপর আমরা যেখানে আমরা গণনা ঃ 0001 এর 8 ম সূচীর একটি 1 দিন হবে.
আমরা গণনা ঃ 23 তারিখের মধ্যে একটি সূচক 2 থাকবে.
আমরা গণনা ঃ এর মধ্যে একটি 42nd সূচক 2 থাকবে.
সুতরাং আমরা গণনা ঃ ব্যবহার করতে পারেন.
সুতরাং num_of_item = সংখ্যা [i].
এবং তাই যদি হয় num_of_item 2 যে, মানে আমরা তোমার মধ্যে 2 নম্বর প্রবেশ করাতে চান
আমাদের মধ্যে সাজানো অ্যারে.
তাই আমরা কতদূর আমরা অ্যারের মধ্যে হয় ট্র্যাক রাখা প্রয়োজন.
সুতরাং সূচক = 0.
এরে - আমি শুধু এটা লিখুন করব.
কাউন্ট -
অ্যারে [সূচক +] = আমি;
এটা কি আমি চাই? আমার মনে হয় আমি কি করতে চান.
হ্যাঁ, এই চেহারা ভালো. ঠিক আছে.
যাতে সবাই বুঝতে না কি আমার সংখ্যা অ্যারের উদ্দেশ্য হল?
এই সব সংখ্যার প্রতিটি ঘটনার সংখ্যা গণনা করা হয়.
তারপর আমি যে সংখ্যা অ্যারের iterating উপর am,
সংখ্যা এবং অ্যারের মধ্যে ith অবস্থান
হয় আমি এর সংখ্যা যে আমার সাজানো অ্যারের মধ্যে প্রদর্শিত হওয়া উচিত.
এটা কেন 4 সংখ্যা 1 হতে যাচ্ছে
এবং 8 সংখ্যা 1 হবে, 23 সংখ্যা 2 হবে.
সুতরাং যে কিভাবে তাদের অনেক আমি আমার সাজানো অ্যারের মধ্যে সন্নিবেশ করতে চান.
তারপর শুধু আমি না যে.
আমি num_of_item am ঢোকাতে আমার সাজানো অ্যারের মধ্যে এর.
>> প্রশ্ন?
তাই আবার, এই রৈখিক সময় যেহেতু আমরা ঠিক এই মাধ্যমে iterating একবার,
কিন্তু এটা কি এছাড়াও এই সংখ্যার জন্য এরকম মধ্যে রৈখিক,
এবং তাই এটি প্রচন্ডভাবে কি আপনার বাউন্ড হয় উপর নির্ভর করে.
200 একটি বাউন্ড মাধ্যমে, যে যে খারাপ না.
যদি আপনার বাউন্ড 10,000 হবে তারপর, যে কিছুটা খারাপ,
কিন্তু যদি আপনার বাউন্ড যাও 4 বিলিয়ন হবে, হবে যে সম্পূর্ণ অবাস্তব
এবং এই অ্যারে মাপ 4 বিলিয়ন ডলার, যা অবাস্তব করা আছে যাচ্ছে.
সুতরাং যে যে. প্রশ্ন?
[শ্রবণাতীত ছাত্র প্রতিক্রিয়া] >> ঠিক আছে.
আমি অন্য একটি জিনিস বুঝতে যখন আমরা মাধ্যমে চালু হয়েছিল.
আমি মনে করি সমস্যা লুকাস এবং সম্ভবত এর প্রতি একক এক আমরা পাচ্ছি তাদের মধ্যে ছিল.
আমি পুরোপুরি ভুলে গেছি.
আমি শুধু মন্তব্য করতে চেয়েছিলেন যে যখন আপনি সূচকগুলি মত বিষয়গুলিতে, কারবারী করছি
আপনি কি সত্যিই এই দেখুন না যখন আপনি লুপের জন্য একটি লিখিত করছেন,
কিন্তু টেকনিক্যালি, যখনই আপনি এই সূচকগুলি সঙ্গে লেনদেন করছেন,
আপনি প্রায় কাছাকাছি সবসময় স্বাক্ষরবিহীন পূর্ণসংখ্যার মোকাবেলা করা উচিত.
এই জন্য কারণ যখন আপনি সাইন পূর্ণসংখ্যার সঙ্গে লেনদেন করছেন,
তাই আপনি যদি 2 সাইন ইন্টিজার আছে এবং আপনি তাদের একসঙ্গে যোগ করুন
এবং তারা শেষ পর্যন্ত খুব বড়, তাহলে আপনি একটি ঋণাত্মক সংখ্যা দিয়ে শেষ.
সুতরাং যে কি পূর্ণসংখ্যা ওভারফ্লো হয়.
>> যদি আমি 2 বিলিয়ন এবং 1 বিলিয়ন যোগ করুন, আমি নেতিবাচক 1 বিলিয়ন শেষ.
এটা কিভাবে পূর্ণসংখ্যার কম্পিউটারে কাজ.
তাই ব্যবহার করে সমস্যা -
এটা জরিমানা ছাড়া যদি কম যাও 2 বিলিয়ন হতে ঘটবে এবং পর্যন্ত 1 বিলিয়ন হতে হবে,
তারপর এই নেতিবাচক 1 বিলিয়ন হবে এবং তারপর আমরা বিভক্ত করা যাচ্ছে করছেন যে দ্বারা 2
এবং নেতিবাচক 500 মিলিয়ন সঙ্গে শেষ.
সুতরাং এই মাত্র একটা বিষয় যদি আপনি এরকম একটি অ্যারের মাধ্যমে অনুসন্ধান করা হবে
এর জিনিষ বিলিয়ান.
কিন্তু যদি কম + আপ ওভারফ্লো যাও ঘটবে তারপর, যে এর একটি সমস্যা.
যত শীঘ্র আমরা তাদের স্বাক্ষরবিহীন তারপর, 2 বিলিয়ন প্লাস 1 বিলিয়ন 3 বিলিয়ন.
3 বিলিয়ন 2 দ্বারা বিভক্ত করা হয় 1.5 বিলিয়ন.
তাই যত তাড়াতাড়ি হিসাবে তারা স্বাক্ষরবিহীন, সবকিছু নিখুঁত হয়.
এবং যাতে এছাড়াও একটি সমস্যা যখন আপনি loops জন্য করছি আপনার লেখা,
এবং প্রকৃতপক্ষে, সম্ভবত এটি স্বয়ংক্রিয়ভাবে এটি আছে.
এটা আসলে আপনি ঠিক সময়ে চিত্কার করা.
তাই আপনি যদি এই সংখ্যা অত্যন্ত শুধুমাত্র পূর্ণসংখ্যা মান করা বড় কিন্তু এটি একটি অস্বাক্ষরিত পূর্ণসংখ্যা মধ্যে মাপসই করা হবে,
এটি আপনাকে চিত্কার করা, যাতে কেন সত্যিই আপনি চালানোর সমস্যা করে না.
আপনি যে একটি সূচক নেতিবাচক হবে না দেখতে পারেন,
এবং যখন আপনি একটি অ্যারের উপর iterating করছি,
আপনি প্রায় সবসময় বলতে স্বাক্ষরবিহীন int তোমার পারেন, কিন্তু আপনি কি সত্যিই আছে না.
জিনিষ প্রশংসনীয় অনেক ভাল কাজ করতে যাচ্ছি.
ঠিক আছে. [দিচ্ছে] এখন কয়টা বাজে?
শেষ জিনিস আমি দেখাতে চেয়েছিলেন - এবং আমি ঠিক তা সত্যিই দ্রুত করব.
আপনি কি জানেন কিভাবে # আমরা যাতে আমরা # 5 বা কিছু MAX হিসাবে সংজ্ঞায়িত করা যাবে না সংজ্ঞায়িত?
চলুন শুরু করা যাক MAX না. # 200 আবদ্ধ হিসাবে নির্ধারণ করুন. আমরা আগে কি.
যে একটি ধ্রুবক, যা শুধুমাত্র কপি করা হবে এবং আটকানো যাও সংজ্ঞায়িত
যেখানেই আমরা আবদ্ধ লিখুন ঘটেছে.
>> সুতরাং আমরা আসলে # সঙ্গে আরো সংজ্ঞায়িত করতে পারেন.
আমরা # কর্ম নির্ধারণ করতে পারবেন.
ঐগুলি ফাংশন সত্যিই, না কিন্তু আমরা তাদের ফাংশন কল করব.
একটি উদাহরণ MAX-(x, y) ভালো কিছু হতে হবে (?: X x <y y) হিসাবে সংজ্ঞায়িত করা হয়. ঠিক আছে.
সুতরাং আপনি তিন অপারেটর বাক্য গঠন করতে ব্যবহৃত হবে,
কিন্তু হল x y কম? Y পর্যন্ত ফিরুন অন্যথায়, x এর প্রত্যাবর্তন.
সুতরাং আপনি আপনার এই একটি পৃথক ফাংশন করতে পারেন দেখতে পারেন,
এবং ফাংশন মত bool MAX-2 আর্গুমেন্ট প্রদর্শিত হতে পারে, এই প্রত্যাবর্তন.
এটা হল সবচেয়ে সাধারণ বেশী আমি দেখতে ভালো কাজ করেছেন একজন. আমরা তাদের কল ম্যাক্রো.
এটি একটি ম্যাক্রো.
এই মাত্র এটা জন্য সিনট্যাক্স.
আপনি যাই হোক না কেন আপনি চান একটা ম্যাক্রো লিখতে পারেন.
আপনি প্রায়শই printfs এবং স্টাফ ডিবাগ জন্য ম্যাক্রো দেখতে.
Printf একটি টাইপ সুতরাং, সি বিশেষ ধ্রুবকের মত LINE আন্ডারস্কোর আন্ডারস্কোর আছে,
2 আন্ডারস্কোর LINE আন্ডারস্কোর,
এবং এর সেখানে আমি মনে করি 2 আন্ডারস্কোর FUNC. এটা হতে পারে. যে ভালো কিছু.
সেগুলো ফাংশনের নাম দিয়ে প্রতিস্থাপিত হবে
লাইন বা যে আপনি ভ্রমণরত সংখ্যা.
প্রায়শ, আপনি ডিবাগিং printfs যে ডাউন এখানে আমি তারপর লিখতে পারেন লিখুন
ডিবাগ করতে এবং এটি লাইন নম্বর এবং ফাংশন যে আমি দর্শন ঘটতে মুদ্রণ করা
এটা যে ডিবাগ বিবৃতি সম্মুখীন হয়েছে.
আপনি এবং অন্যান্য জিনিসের মুদ্রণ করতে পারেন.
তাই এক জিনিস আপনার জন্য ঘড়ি আউট উচিত হয় আমি যদি # DOUBLE_MAX সংজ্ঞায়িত ঘটতে
হিসাবে 2 * y এবং 2 ভালো কিছু * x.
সুতরাং কারনের জন্য, আপনি অনেক যে কি ঘটবে.
সুতরাং এটি একটি ম্যাক্রো করা.
এই প্রকৃতপক্ষে ভাঙা.
আমি DOUBLE_MAX (3, 6) মত করে একে ডাকতে হবে.
ফিরে কি করা উচিত?
[ছাত্রদের] 12.
হ্যাঁ, 12 ফিরে, করা উচিত এবং 12 ফিরিয়ে দেওয়া হয়.
3 x এর জন্য প্রতিস্থাপিত পরার, 6 y জন্য, প্রতিস্থাপিত এবং আমরা 2 * 6, যা 12 ফেরত দিতে হয়.
এখন কি এই সম্পর্কে? কি করা উচিত ফিরে?
[ছাত্রদের] 14. >> মূলত, 14.
সমস্যাটি হল এই যে হ্যাশ কিভাবে কাজ সংজ্ঞায়িত করে, এটি একটি হুবহু কপি এবং পেস্ট স্মরণ
প্রায় কাছাকাছি সবকিছু, তাই কি এই হিসাবে ব্যাখ্যা করা যাচ্ছে না
1 টি প্লাস 6, 2 বার 1 যোগ 6, 2 বার 3 তুলনায় কম 3.
>> তাই এই কারণে আপনি প্রায় সবসময় বন্ধনীর মধ্যে সবকিছু মোড়ানো.
কোন পরিবর্তনশীল আপনি বন্ধনীর মধ্যে প্রায় সবসময় মোড়ানো.
যেসব ক্ষেত্রে আপনি না আছে, যেমন আমি জানি যে আমি এখানে যা করার প্রয়োজন নেই
কারণ কম বেশ সবসময় ঠিক অনেক কাজ হচ্ছে,
যদিও এমনকি সত্য নাও হতে পারে.
যদি কিছু DOUBLE_MAX (1 == 2) মত হাস্যকর হয়,
তারপর যে যাও 3 কম 1 র পরিবর্তে পাওয়া যাচ্ছে সমান সমান 2,
এবং তারপর, তাই এটি 1 থেকে 3 তুলনায় কম যাচ্ছে না, কিন্তু এর যে সমান 2,
যা কি না আমরা চাই.
তাই যাতে কোনো অপারেটর প্রাধান্য সমস্যা এড়ানোর জন্য,
এব w বন্ধনী ববহার সর্বদা মোড়ানো.
ঠিক আছে. এবং যে এটি, 5:30.
আপনি যদি pset কোনো প্রশ্ন থাকে, আমাদের জানা.
এটা মজা হতে পারে, এবং হ্যাকার সংস্করণ এছাড়াও অনেক বেশি বাস্তবসম্মত উচিত
গত বছরের তুলনায় এর হ্যাকার সংস্করণ, তাই আমরা আশা করি যে আপনি অনেক চেষ্টা করে দেখুন.
সর্বশেষ বছরের ছিল খুব অপ্রতিরোধ্য.
>> [CS50.TV]