[Powered by Google Translate] আপনি সম্ভবত করেছি শুনে জনের একটি দ্রুত বা দক্ষ এলগরিদম সম্পর্কে কথা বলা
আপনার জন্য বিশেষ টাস্ক নির্বাহ,
কি ঠিক কিন্তু এটি একটি অ্যালগরিদম দ্রুত বা দক্ষ জন্য মানে?
ওয়েল, এটা রিয়েল টাইমে একটি পরিমাপ বিষয়ে কথা বলছি না,
ভালো যাও বা মিনিট.
এর কারণ হল কম্পিউটার হার্ডওয়্যার
সফ্টওয়্যার এবং অত্যন্ত তারতম্য.
আমার প্রোগ্রাম এগুলি তুলনায় ধীর চালানো হতে পারে,
কারণ আমি একটি পুরোনো কম্পিউটারে এটি হবে চলমান,
বা কারণ আমি এরকম একটি অনলাইন ভিডিও গেম খেলার করা
একই সময়ে, যা সব আমার মেমরি নুড়ি হয়,
অথবা আমি বিভিন্ন সফটওয়্যার এর মাধ্যমে আমার প্রোগ্রাম হতে পারে চলমান
যা মেশিনের সাথে যোগাযোগ পৃথক একটি নিম্ন পর্যায়ে.
এটা আপেল এবং কমলা তুলনা করার মত.
শুধু কারণ আমার ধীর গতির কম্পিউটার এখন আর লাগে
তুলনায় পুলিশের একটি answer দিতে ফিরে
কিন্তু আপনি আরো দক্ষ এলগরিদম আছে না মানে.
>> সুতরাং, আমরা যেহেতু সরাসরি প্রোগ্রামের সাথে তুলনা করতে পারেন না runtimes
সেকেন্ডের মধ্যে অথবা মিনিট,
কিভাবে আমরা বিভিন্ন 2 আলগোরিদিম তুলনা
নির্বিশেষে তাদের হার্ডওয়্যার অথবা সফ্টওয়্যার পরিবেশ?
একটি আলগোরিদিমিক দক্ষতা পরিমাপ আরো অভিন্ন ভাবে তৈরি,
কম্পিউটার বিজ্ঞানীরা এবং mathematicians চিন্তিত আছে
একটি প্রোগ্রাম asymptotic জটিলতা পরিমাপের জন্য ধারণা
এবং একটি স্বরলিপি বলা 'বিগ Ohnotation'
এই জন্য বর্ণনা.
প্রথাগত সংজ্ঞা হয় যে একটা ফাংশন f (x)
গ্রাম অর্ডার (x) উপর সঞ্চালিত হয়
যদি কিছু বিদ্যমান? (x) মূল্য আছে, x এর ₀ এবং
কিছু ধ্রুবক, সি, যার জন্য
চ (x) কম বা সমান
যে ধ্রুব বার g (x)
জন্য সমস্ত x x ₀ তার চেয়ে অনেক বেশী.
>> কিন্তু প্রথাগত সংজ্ঞা দ্বারা কাঁচুমাচু না দূরে করা হবে.
কি আসলে এই কম তাত্ত্বিক পদ মানে?
হ্যাঁ, এটি মূলত বিশ্লেষণ এর একটি উপায়
কিভাবে দ্রুত একটি প্রোগ্রাম এর রানটাইম asymptotically বৃদ্ধি.
অর্থাৎ, আপনার ইনপুট হিসাবে মাপ অনন্ত প্রতি বাড়ে,
বলুন, আপনি মাপ 10 শ্রেণীবিন্যাস তুলনায় আয়তন 1000 শ্রেণীবিন্যাস বাছাই করছেন.
কিভাবে আপনার প্রোগ্রামের রানটাইম না বাড়া?
উদাহরণস্বরূপ, অক্ষরের সংখ্যা বেড়ে চলেছে কল্পনা
একটি স্ট্রিং সহজ উপায়
দ্বারা সম্পূর্ণ পংক্তি মাধ্যমে হাঁটা
চিঠি-দ্বারা অক্ষর এবং প্রতিটি অক্ষরের জন্য একটি পাল্টা যাও 1 যোগ.
এই অ্যালগরিদম রৈখিক সময় চালানোর জন্য বলা হয়
সঙ্গে অক্ষরের সংখ্যা সম্মান,
'এন' পংক্তিতে.
সংক্ষেপে, এটা হে (ঢ) রান.
কেন এই?
ওয়েল, এই পদ্ধতির ব্যবহার, সময় প্রয়োজন
সমগ্র স্ট্রিং তর্ক করা
সমানুপাতিক হয় অক্ষরের সংখ্যা যাও.
একটি 20-পংক্তির মধ্যে অক্ষর সংখ্যা বেড়ে চলেছে
দুইবার হিসাবে দীর্ঘ নিতে হিসাবে এটি প্রদর্শন করা হবে
একটি 10-পংক্তির মধ্যে অক্ষর গণনা,
কারণ আপনি সব অক্ষর তাকান আছে
এবং প্রতিটি অক্ষর সময় তাকান একই পরিমাণ সময় লাগে.
হিসাবে আপনি অক্ষরের সংখ্যা, বৃদ্ধি
রানটাইম ইনপুট দ্বারা linearly বৃদ্ধি হবে.
>> এখন, যদি আপনি যে রৈখিক সময় সিদ্ধান্ত কল্পনা,
হে (ঢ), শুধু আপনার জন্য যথেষ্ট দ্রুত ছিল না?
হতে পারে আপনি বিপুল পংক্তি সংরক্ষণ করছেন,
এবং আপনি অতিরিক্ত সময় লাগবে সামর্থ নেই
তাদের দ্বারা এক এক গণনা অক্ষরের সব তর্ক.
সুতরাং, আপনি নতুন কিছু চেষ্টা সিদ্ধান্ত নেন.
যদি আপনি ইতিমধ্যে অক্ষরের সংখ্যা সঞ্চয় ঘটতে পারে
স্ট্রিং মধ্যে, একটি পরিবর্তনশীল নামক মধ্যে, বলে 'Len,'
আগে থেকেই মধ্যে প্রোগ্রাম,
আগে এমনকি আপনি আপনার স্ট্রিং খুবই প্রথম অক্ষরটি সঞ্চিত?
তারপর সব, আপনি এখন যাও স্ট্রিং দ্বারা খুঁজে বের করতে চাই,
চেক কি ভেরিয়েবলের মান হল.
আপনি স্ট্রিং এ নিজেই সব তাকান আছে না,
এবং Len মত একটি ভেরিয়েবলের মান অ্যাক্সেস বিবেচনা করা হয়
একটি asymptotically ধ্রুবক সময় অপারেশন,
অথবা O (1).
কেন এই? ভাল, মনে রাখবেন কি asymptotic জটিলতা মানে.
কিভাবে আকার হিসাবে রানটাইম পরিবর্তন
আপনার উত্তরগুলি বৃদ্ধি?
>> বলুন আপনি অক্ষরের একটি বড় পংক্তি সংখ্যা পেতে চেষ্টা করছিলেন.
হ্যাঁ, এটি কিভাবে বড় পংক্তিটি করা কোন ব্যাপার না,
এমনকি একটি মিলিয়ন অক্ষর দীর্ঘ,
সমস্ত আপনি এই পদ্ধতির সঙ্গে স্ট্রিং এর দৈর্ঘ্য খুঁজে করতে চাই,
যাও পরিবর্তনশীল Len মান পড়তে আউট হল,
যা ইতিমধ্যে আপনি তৈরি করেছেন.
ইনপুট দ্বারা, যে, আপনি স্ট্রিং খোঁজার চেষ্টা করছেন তার দ্বারা,
কিন্তু কিভাবে দ্রুত আপনার সমস্ত প্রোগ্রাম রান এ প্রভাব ফেলে না.
আপনার প্রোগ্রাম এই ভাগে এক পংক্তি চালানো সমানভাবে দ্রুত করবে
এবং হাজার হাজার-পংক্তি,
এবং যে কেন এই প্রোগ্রাম করা হবে ধ্রুবক সময় চলমান হিসাবে বলা
সঙ্গে ইনপুট আকার সম্মান.
>> অবশ্যই একটি অসুবিধা আছে.
আপনি আপনার কম্পিউটারে অতিরিক্ত মেমরি স্পেস ব্যয়
পরিবর্তনশীল সংরক্ষণ
এবং অতিরিক্ত সময় এটি প্রদর্শিত হবে
যাও পরিবর্তনশীল প্রকৃত সংগ্রহস্থল না,
কিন্তু এখনও বিন্দু ঘোরা,
কীভাবে আপনার দীর্ঘ স্ট্রিং ছিল
কিন্তু এ সমস্ত স্ট্রিং দৈর্ঘ্যের উপর নির্ভর করে না.
সুতরাং, এটা হে (1) বা ধ্রুবক সময় রান.
অবশ্যই এই চাওয়ার কথা বলছেন না
যে আপনার কোড পদক্ষেপ 1 রান,
কিন্তু কোন ব্যাপার কতগুলি পদক্ষেপ এটা,
যদি ইনপুট মাপ সঙ্গে পরিবর্তন হয় না,
এটি এখনও asymptotically ধ্রুবক যা আমরা আউটপুট (1) হিসাবে চিত্রিত করা.
>> আপনি সম্ভবত আপনি অনুমান করতে পারেন,
বিভিন্ন বড় হে runtimes যাও সঙ্গে আলগোরিদিম পরিমাপ আছে.
হে (ঢ) ² আলগোরিদিম হল আউটপুট (ঢ) আলগোরিদিম তুলনায় asymptotically মন্থর.
অর্থাৎ, হিসাবে উপাদানের সংখ্যা (ঢ) বৃদ্ধি হয়,
ঘটনাক্রমে হে (ঢ) ² আলগোরিদিম আরো সময় লাগবে
তুলনায় হে (ঢ) আলগোরিদিম চালানোর.
এই হে (ঢ) আলগোরিদিম সর্বদা দ্রুত চালানোর মানে এই নয়
তুলনায় হে (ঢ) ² আলগোরিদিম, এমনকি একই পরিবেশ,
একই হার্ডওয়্যারের.
হয়তো ছোট জন্য ইনপুট মাপ,
হে (ঢ) ² আলগোরিদিম আসলে কাজ দ্রুত হতে পারে,
কিন্তু, অবশেষে ইনপুট আকার হিসাবে, বৃদ্ধি
প্রতি অনন্ত, হে (ঢ) ² এর এলগরিদম এর রানটাইম
হে (ঢ) আলগোরিদিম রানটাইম অবশেষে গ্রাস করবে.
ঠিক মত কোনো দ্বিঘাত গাণিতিক ফাংশন
কোন লিনিয়ার ফাংশন অবশেষে নাগাল ধরা হবে,
কোন ব্যাপার একটি মাথার কত রৈখিক ফাংশন শুরু সঙ্গে শুরু হয় বন্ধ.
আপনি যদি তথ্য বিশাল পরিমাণ সঙ্গে কাজ করছি,
আলগোরিদিম হে যে চালানোর (ঢ) সত্যিই ² এর সময় শেষ পর্যন্ত গতি আপনার প্রোগ্রাম বন্ধ করে করতে পারেন,
কিন্তু ইনপুট জন্য ছোট আকারের,
আপনি সম্ভবত এমনকি লক্ষ্য করবেন.
>> অন্য asymptotic জটিলতা হয়,
লগারিদমিক সময়, হে (log n).
একটি অ্যালগরিদম যে এই দ্রুত সঞ্চালিত একটি উদাহরণ
হয় ক্লাসিক বাইনারি অনুসন্ধান অ্যালগোরিদম,
জন্য একটি উপাদানের ইতিমধ্যে-অনুসারে সাজানো তালিকা একটি উপাদান খুঁজে পেতে.
>> যদি আপনি কি বাইনারি অনুসন্ধান আছে না,
আমি এটা আপনার জন্য সত্যিই দ্রুত ব্যাখ্যা করব.
চলুন শুরু করা যাক আপনি বলতে নম্বর 3 খুঁজছেন
পূর্ণসংখ্যার মধ্যে এই অ্যারে.
এটা অ্যারের মধ্যম উপাদান এ দেখায়
জিজ্ঞেস করে, "কি উপাদান আমি চাই চেয়ে বড়, সমান, যাও বা এই কম?"
এটি যদি সমান, তারপর মহান. আপনি উপাদান পাওয়া গেছে, এবং আপনি সম্পন্ন করেছেন.
এটি যদি বেশী থাকে, তাহলে আপনি জানেন উপাদান
অ্যারের ডান পাশ করা হয়েছে,
এবং শুধুমাত্র আপনি যে ভবিষ্যতে এ প্রত্যাশা করতে পারেন,
এবং যদি এটা ছোট তারপর, আপনি কি জানেন এটি বাম দিকে করা আছে.
এই প্রক্রিয়া পুনরাবৃত্তি করা হয় তাহলে ছোট আকারের সঙ্গে অ্যারে
পর্যন্ত সঠিক উপাদান পাওয়া যায়.
>> এই ক্ষমতাশালী আলগোরিদিম অর্ধেক প্রতিটি অপারেশন সঙ্গে অ্যারের আকার মধ্যেও.
সুতরাং, একটি আকার 8 সাজানো অ্যারের মধ্যে একটি উপাদান খুঁজে,
সর্বাধিক (₂ 8 লগ ইন),
এইসব কাজকর্ম বা 3,
মধ্যম উপাদান পরীক্ষণের পরে, অর্ধেক অ্যারের কাটা প্রয়োজন হবে,
যেহেতু আকার 16 শ্রেণীবিন্যাস লাগে (₂ 16 লগ ইন),
বা 4 অপারেশন.
যে মাত্র 1 দ্বিগুণ আকার অ্যারের জন্য আরো অপারেশন.
অ্যারের আকার দ্বিত্ব
এই কোড দ্বারা শুধুমাত্র 1 চাঙ্গড় রানটাইম বাড়ে.
আবার, মধ্যম উপাদান তালিকা পরীক্ষণ, তারপর বিদারক.
সুতরাং, এটি লগারিদমিক সময় কাজ করতে এর বলেন,
হে (log n).
কিন্তু, আপনি বলার অপেক্ষা করুন,
কিন্তু উপর নির্ভর করে না যেখানে এই উপাদান আপনি যা খুঁজছেন তা তালিকার মধ্যে হয়?
যদি আপনি প্রথম উপাদান তাকান সঠিক হতে হয়?
তারপর, এটা শুধুমাত্র 1 অপারেশন লাগে,
কোন ব্যাপার কিভাবে বড় তালিকা.
>> ওহ, এটা কেন কম্পিউটার বিজ্ঞানীরা আরো পদ আছে
জন্য asymptotic জটিলতা যা সর্বোত্তম ক্ষেত্রে প্রতিফলিত
এবং worst-ক্ষেত্রে একটি আলগোরিদিম পারফরমেন্স.
আরো সঠিকভাবে, উচ্চ এবং নিম্ন কোট
উপর রানটাইম.
বাইনারি অনুসন্ধান জন্য সেরা ক্ষেত্রে, আমাদের উপাদান হল
মধ্যম অধিকার আছে,
এবং আপনি ধ্রুবক সময়ের মধ্যে তা পেতে,
কোন ব্যাপার কিভাবে বড় অ্যারের বিশ্রাম হয়.
এই চিহ্ন ব্যবহার করা হয় Ω জন্য.
সুতরাং, এই অ্যালগরিদম Ω (1) চালানোর জন্য বলা হয়.
সেরা ক্ষেত্রে, এটা উপাদান দ্রুত খুঁজে বের করে,
কোন ব্যাপার কিভাবে অ্যারে বড় হয়,
কিন্তু খারাপ কেস,
এটি বিভক্ত চেক সঞ্চালন (লগ ঢ) আছে
অ্যারের মধ্যে ডান উপাদান খুঁজে পেতে.
সবচেয়ে-ক্ষেত্রে উপরের কোট বড় "O" কে আপনি কি জানেন যে ইতিমধ্যে সঙ্গে উল্লেখ করা হয়.
সুতরাং, এটা হে (log n), কিন্তু Ω (1).
>> একটি রৈখিক অনুসন্ধান, এর বিপরীতে,
যা আপনি অ্যারের প্রতিটি উপাদান ভিতর দিয়ে হেটে যেতে
এক আপনি খুঁজে পান,
সেরা Ω (1) এ.
আবার, প্রথম উপাদান চান.
সুতরাং, এটি কিভাবে বড় অ্যারে হয় না ব্যাপার.
সবচেয়ে খারাপ ক্ষেত্রে, এটা অ্যারের মধ্যে শেষ উপাদান.
সুতরাং, আপনি সমস্ত অ্যারের মধ্যে n উপাদানের মাধ্যমে সেটা খুঁজে পেতে হেঁটে যাওয়ার আছে,
যদি আপনি একটি 3 খুঁজছেন কথা আমার ভালো লাগে.
সুতরাং, এটা হে (ঢ) সময় রান
কারণ এটা আনুপাতিক অ্যারের মধ্যে উপাদান সংখ্যা.
>> আরও একটি চিহ্ন ব্যবহার করা হয় Θ.
এটি ব্যবহৃত আলগোরিদিম যেখানে ভাল এবং খারাপ ক্ষেত্রে বর্ণনা করা যেতে পারে
একই.
এটি স্ট্রিং দৈর্ঘ্য আলগোরিদিম সম্পর্কে আমরা কথা বললাম তার আগে ক্ষেত্রে.
মানে, যদি আমরা একটি পরিবর্তনশীল মধ্যে এটি পূর্বে সংরক্ষণ
আমরা পংক্তিটি সংরক্ষণ করে এবং তা পরবর্তী সময় ধ্রুবক অ্যাক্সেস.
কোন ব্যাপার কি নম্বর
আমরা যে ভেরিয়েবলের মধ্যে সংরক্ষণ করছি, আমরা তা পর্যবেক্ষণ করতে হবে.
সেরা ক্ষেত্রে, আমরা এটি তাকান
এবং স্ট্রিং এর দৈর্ঘ্য খুঁজে.
সুতরাং Ω (1) বা সেরা-ক্ষেত্রে সময় ধ্রুবক.
লক হয়,
আমরা এটি তাকান এবং string এর দ্বারা খুঁজে.
সুতরাং, হে (1) বা খারাপ ক্ষেত্রে সময় ধ্রুবক.
ভাল এবং খারাপ কেস ক্ষেত্রে যেহেতু সুতরাং, একই,
এই বলেন Θ (1) সময় চালানোর জন্য করা যেতে পারে.
>> সংক্ষেপে বলা যায়, আমরা কোড দক্ষতা সম্পর্কে কারণ ভাল উপায় আছে
ছাড়া বাস্তব সময় তারা চালানোর নিতে সম্পর্কে কিছু বুদ্ধিমান,
যা বাইরে অনেক কারণের দ্বারা প্রভাবিত হয়,
সহ বিভিন্ন হার্ডওয়্যার, সফ্টওয়্যার,
অথবা আপনার কোড সুনির্দিষ্ট.
এছাড়াও, আমাদের কি ঘটবে সম্পর্কে ভাল কারণ করতে পারবেন
যখন ইনপুট বৃদ্ধির মাপ.
>> আপনি যদি আউটপুট (ঢ) ² আলগোরিদিম মধ্যে চালাচ্ছেন,
বা তার থেকেও খারাপ, একটি আউটপুট (2 ⁿ) এলগরিদম,
দ্রুততম ক্রমবর্ধমান ধরন,
আপনি কি সত্যিই ধীর গতি লক্ষ্য করা শুরু করব
যখন আপনি শুরু তথ্য বড় পরিমাণে কাজ.
>> এটা asymptotic জটিলতা. ধন্যবাদ.