[Powered by Google Translate] Tommy: চলুন নির্বাচন সাজানোর কটাক্ষপাত, একটি অ্যালগরিদম গ্রহণ
সংখ্যার জন্য একটি তালিকা গ্রহণ এবং তাদের বাছাই.
একটি অ্যালগরিদম,, মনে রাখবেন শুধু একটি ধাপে ধাপে
একটি টাস্ক accomplishing জন্য পদ্ধতি.
নির্বাচন সাজানোর পিছনে মূল ধারনাটি বিভক্ত করা হয়
দুটি অংশ মধ্যে আমাদের তালিকা -
একটি সাজানো অংশ এবং একটি পাঁচমিশালী অংশ.
আলগোরিদিম প্রতিটি ধাপ অনুযায়ী, একজন নম্বর থেকে স্থানান্তরিত হয়
সাজানো অংশ যাও পাঁচমিশালী অবশেষে পর্যন্ত অংশ
সম্পূর্ণ তালিকা অনুসারে বাছাই করা হয়.
সুতরাং এখানে ছয়টি সংখ্যার একটি তালিকা -
23, 42, 4, 16, 8, এবং 15.
রাইট এখন সম্পূর্ণ তালিকা পাঁচমিশালী বিবেচনা করা হয়.
যদিও ইতিমধ্যে 16 মত একটি সংখ্যা তার সঠিক হতে পারে
অবস্থান, আমাদের এলগরিদম পর্যন্ত যে বুদ্ধিমান কোন উপায় আছে
সম্পূর্ণ তালিকা অনুসারে বাছাই করা হয়.
সুতরাং আমরা প্রতি নম্বর বিবেচনা করা হবে পাঁচমিশালী যাও যতক্ষণ পর্যন্ত না আমরা সাজাতে হবে
এটি নিজেদেরকে.
আমরা জানি যে আমরা তালিকা ক্রম আরোহী হতে চান.
তাই আমরা আমাদের তালিকা অনুসারে বাছাই করা অংশ বিল্ড আপ করতে চাইবেন
বামদিক থেকে ডানদিকে ক্ষুদ্রতম বৃহত্তম যাও.
কি সেটা, আমরা সর্বনিম্ন পাঁচমিশালী উপাদান খুঁজে করতে হবে
এবং সাজানো অংশ শেষে লাগাতে হবে.
যেহেতু এই তালিকা অনুসারে বাছাই করা না হয়, একমাত্র উপায় হল যে কাজের জন্য
পাঁচমিশালী অংশে প্রতিটি উপাদান তাকান, স্মরন
যা উপাদান হল সর্বনিম্ন এবং তুলনা
যে প্রতিটি উপাদান.
তাই আমরা প্রথম 23 এ সন্ধান করব.
এটি প্রথম উপাদান আমরা দেখা করেছি, যাতে আমরা স্মরণ করব
সর্বনিম্ন হিসাবে এটি.
আমরা পরবর্তী 42 তাকান করব.
42 হয় 23 থেকে বড় তাই, 23 এখনও সর্বনিম্ন.
এর পরে রয়েছে 4 যা 23 তুলনায় কম, তাই আমরা 4 স্মরণ করব
হিসাবে নতুন সর্বনিম্ন.
এর পরে রয়েছে 16, যা 4 অধিক মাপের, তাই 4
এখনও সর্বনিম্ন.
8 4 অধিক মাপের, 15 এবং 4 থেকে বড়, তাই 4 আবশ্যক
ক্ষুদ্রতম পাঁচমিশালী উপাদান.
মানুষ হিসাবে সুতরাং যদিও আমরা অবিলম্বে দেখতে পারেন যে 4
সর্বনিম্ন উপাদান, আমাদের এলগরিদম তাকান প্রয়োজন
প্রতি পাঁচমিশালী উপাদান, এমনকি পরে আমরা 4 পেয়েছি -
সর্বনিম্ন উপাদান.
তাই এখন যে আমরা সর্বনিম্ন উপাদান, 4 পাওয়া করেছি, আমরা চাইবেন
তালিকার মধ্যে সাজানো অংশ সরিয়ে নেয়া.
যেহেতু এটি প্রথম পদক্ষেপ, এর মানে আমরা এ 4 লাগাতে চান
তালিকার শুরুতে.
রাইট এখন 23 তালিকা প্রারম্ভে হয়, তাই
আসুন 4 এবং 23 অদলবদল.
তাই এখন আমাদের তালিকা ভালো দেখায়.
আমরা জানি যে 4 তার চুড়ান্ত অবস্থান হবে, কারণ এটি
উভয় ক্ষুদ্রতম প্রারম্ভে উপাদান এবং উপাদান
তালিকা.
তাই এই মানে যে আমরা আবার সরিয়ে নেয়া প্রয়োজন কখনও না.
সুতরাং আসুন যাও যাও অন্য উপাদান যোগ এই প্রক্রিয়া পুনরাবৃত্তি করা
তালিকা অনুসারে বাছাই করা অংশ.
আমরা জানি যে আমরা 4 তাকান করার প্রয়োজন হবে না, কারণ এটা
ইতিমধ্যে সাজানো.
তাই আমরা 42 এ, যা আমরা হিসাবে মনে রাখতে হবে শুরু করতে পারেন
সর্বনিম্ন উপাদান.
সুতরাং আমরা পরবর্তী 23 যা 42 এর কম সময়ে, যাতে সন্ধান করব আমরা
মনে রাখবেন 23 নতুন সর্বনিম্ন.
আমরা 16 এর পরে যা কম 23 দেখতে, তাই
16 নতুন সর্বনিম্ন.
এখন 8 যা কম 16 এ আমরা, তাই চেহারা
8 নতুন সর্বনিম্ন.
এবং পরিশেষে 8 কম 15, যাতে আমরা জানতে পারি যে একটি সর্বনিম্ন 8
পাঁচমিশালী উপাদান.
সুতরাং তার মানে আমরা 8 সাজানো যাও লিখবেন উচিত
তালিকার অংশ.
রাইট এখন 4 শুধুমাত্র সাজানো উপাদান, যাতে আমরা স্থাপন করতে চান
8 পরবর্তী যাও 4.
42 যেহেতু হয় পাঁচমিশালী অংশে প্রথম উপাদান
তালিকা, আমরা 42 এবং 8 অদলবদল করতে চাইবেন.
তাই এখন আমাদের তালিকা ভালো দেখায়.
4 এবং 8 তালিকা অনুসারে বাছাই করা অংশ চিত্রিত করা, এবং
অবশিষ্ট সংখ্যার পাঁচমিশালী প্রতিনিধিত্ব
তালিকার অংশ.
সুতরাং আসুন অন্য পুনরাবৃত্তির সঙ্গে অবিরত.
23 সঙ্গে আমরা এই সময় শুরু, যেহেতু আমরা তাকান করার প্রয়োজন হবে না
4 এবং 8 আর কারণ তারা করেছেন
ইতিমধ্যে অনুসারে সাজানো হয়েছে.
16 এর চেয়ে 23, যাতে আমরা স্মরণ করব
নতুন সর্বনিম্ন হিসাবে 16.
16 এর চেয়ে 42, কিন্তু 15 এর চেয়ে 16, তাই 15 হতে হবে
সর্বনিম্ন পাঁচমিশালী উপাদান.
তাই এখন আমরা 15 এবং 23 অদলবদল করতে চান
আমাদের এই তালিকা দিতে.
তালিকা অনুসারে বাছাই করা অংশ 4, 8 এবং 15 এর মধ্যে রয়েছে, এবং
এই উপাদান এখনও পাঁচমিশালী.
তবে তা যে পরবর্তী পাঁচমিশালী উপাদান, 16,
ইতিমধ্যে সাজানো হয়.
তবে, আমাদের এলগরিদম জন্য কোন উপায় জানেন যে 16
ইতিমধ্যেই তার সঠিক অবস্থান করে, তাই আমরা এখনও প্রয়োজন
ঠিক একই পদ্ধতি পুনরাবৃত্তি করুন.
সুতরাং আমরা যে 16 কম দেখতে 42, 16 এবং 23 কম, তাই
16 সর্বনিম্ন উপাদান হতে হবে.
এটা নিজেই সঙ্গে এই উপাদান বিনিময় করা অসম্ভব, তাই আমরা করতে পারেন
সহজভাবে এটি এই অবস্থান ছেড়ে.
সুতরাং আমরা আমাদের এলগরিদম এক আরো পাস প্রয়োজন.
42 23 হয় তার চেয়ে অনেক বেশী, তাই 23 হতে হবে
সর্বনিম্ন পাঁচমিশালী উপাদান.
একবার আমরা 23 এবং 42, swap আমরা আমাদের চূড়ান্ত সঙ্গে শেষ
অনুসারে সাজানো তালিকা -
4, 8, 15, 16, 23, 42.
আমরা জানি 42 সঠিক স্থান থেকে এটি করা আবশ্যক
শুধুমাত্র উপাদান বাকি, এবং যে নির্বাচন সাজান.
চলুন শুরু করা যাক এখন কিছু সঙ্গে আমাদের এলগরিদম ডিক্রী
pseudocode.
এক লাইন, আমরা যে আমরা মাধ্যমে গোটা প্রয়োজন দেখতে পারেন
তালিকায় প্রতিটি উপাদান.
ছাড়া গত উপাদান, 1 উপাদান
তালিকাটি ইতিমধ্যেই সাজানো হয়.
লাইন দুটি অন, আমরা পাঁচমিশালী প্রথম উপাদান বিবেচনা
তালিকার অংশ সর্বনিম্ন করা, যেমন আমরা আমাদের সঙ্গে কি
উদাহরণস্বরূপ, তাই তুলনা কিছু আছে.
লাইন তিনটি দ্বিতীয় একটি লুপ যা আমরা উপর পুনরুক্তি করা শুরু
প্রতিটি পাঁচমিশালী উপাদান.
আমরা জানি যে পরে আমি পুনরাবৃত্তিও, অনুসারে বাছাই করা অংশ
আমাদের তালিকার মধ্যে এটি তোমার প্রতিটি ধাপ থেকে উপাদান থাকতে হবে
অসুস্থ এক উপাদান.
সুতরাং প্রথম পাঁচমিশালী উপাদান তোমার প্লাস 1 স্থান হবে.
লাইন চার তারিখে, আমরা সর্বনিম্ন বর্তমান উপাদান তুলনা
উপাদান যে আমরা এতদূর দেখা করেছি.
যদি বর্তমান উপাদান হল সর্বনিম্ন চেয়ে ছোট
উপাদান তারপর, আমরা নতুন উপাদান হিসাবে বর্তমান স্মরণ
লাইন পাঁচ ন্যূনতম.
লাইন ছয় এবং সাত উপর পরিশেষে, আমরা সর্বনিম্ন অদলবদল
প্রথম পাঁচমিশালী উপাদান সঙ্গে উপাদান যার ফলে,
তালিকা অনুসারে বাছাই করা অংশ এটি যোগ করা.
একবার আমরা একটি অ্যালগরিদম আছে, একটি গুরুত্বপূর্ণ প্রশ্ন জিজ্ঞাসা
নিজেদেরকে প্রোগ্রামার হিসাবে কতদিন হয় নি যে সময় লাগবে?
আমরা প্রথম প্রশ্ন জিজ্ঞাসা করব কতদিন এটা এই জন্য সময় লাগবে
সবচেয়ে খারাপ ক্ষেত্রে আলগোরিদিম চালানোর?
রিকল আমরা এই চলমান ঘটনা বিবৃত করা
বড় হে স্বরলিপি সঙ্গে সময়.
যাতে সর্বনিম্ন পাঁচমিশালী উপাদান কিনা, আমরা
মূলত যাও যাও তালিকার প্রতিটি উপাদান ছিল তুলনা
প্রত্যেক তালিকার অন্যান্য উপাদান.
Intuitively, একটি হে n স্কয়ার্ড কার্যপ্রণালীর এই মত শোনায়.
আমাদের pseudocode এ জন্যে, আমরা একটি লুপ নেস্টেড ভিতর আছে
অন্য একটি হে ভালো লুপ, যা প্রকৃতপক্ষে শোনাচ্ছে
এর n স্কয়ার্ড অপারেশন.
তবে, মনে রাখবেন, যে আমরা দেখে যাও নি প্রয়োজন
সম্পূর্ণ তালিকা যখন সর্বনিম্ন পাঁচমিশালী উপাদান নির্ণয় করা হবে?
উদাহরণস্বরূপ আমরা একবার জানতো যে 4 সাজানো ছিল,, আমরা না
এটি আবার তার প্রয়োজন.
সুতরাং আছে এই চলমান সময় কম?
6 দ্বারা আমাদের তালিকা দেখার জন্য, আমরা পাঁচটি করা প্রয়োজন
তুলনা প্রথম উপাদান জন্য, চার জন্য তুলনা
দ্বিতীয় উপাদান, এবং তাই.
তার মানে যে পদক্ষেপগুলো মোট সংখ্যা সমষ্টি
1 থেকে 1 বিয়োগ তালিকা দৈর্ঘ্যের ইন্টিজার.
আমরা একটি সঙ্কলন সঙ্গে এই উপস্থাপন করতে পারেন.
আমরা summations ঢোকা হবে না এখানে.
কিন্তু এটি সক্রিয় আউট যে এই সঙ্কলন সমান হবে বার যাও
n বিয়োগ 2 উপর 1.
অথবা equivalently, উপর 2 বিয়োগ জন্য 2 উপর n Squared.
Asymptotic রানটাইম সম্পর্কে যখন কথা বলা, এই শব্দটি n ছক
এই শব্দটি n আয়ত্তে আনা যাচ্ছে না.
তাই নির্বাচন সাজানোর হয় স্কয়ার্ড n হে.
পুনরাহ্বান যে আমাদের উদাহরণে, এখনও নির্বাচন সাজানোর প্রয়োজন
যদি একটি চেক নম্বর যে ইতিমধ্যেই সাজানো
প্রয়োজন সরানো যাও.
যাতে এর মানে হল যে যদি আমরা একটি ইতিমধ্যে নির্বাচন সাজানোর দৌড়ে
তালিকা অনুসারে সাজানো, এটি একই পদক্ষেপ হিসাবে এটি নম্বর প্রয়োজন
একটি সম্পূর্ণ তালিকা পাঁচমিশালী যখন চলমান হবে.
তাই নির্বাচন সাজানোর একটি শ্রেষ্ঠ n স্কয়ার্ড ক্ষেত্রে কর্মক্ষমতা রয়েছে,
যা আমরা ওমেগা n স্কয়ার্ড সঙ্গে চিত্রিত করা.
এবং যে নির্বাচন সাজানোর জন্য এটি.
অনেক আলগোরিদিম আমরা করতে পারেন মাত্র এক
যাও একটি তালিকা বাছাই ব্যবহার.
আমার নাম টমি, এবং এই cs50.