বিগ-ও নোটেশন কি?

আপনি কি কখনও ভেবে দেখেছেন যে আপনার লেখা একটি প্রোগ্রাম চালাতে এত সময় লাগল কেন? সম্ভবত আপনি জানতে চান যে আপনি আপনার কোডটি আরও দক্ষ করতে পারেন কিনা। কোড কিভাবে চালায় তা বোঝা আপনার কোডকে পরবর্তী স্তরে নিয়ে আসতে পারে। বিগ-ও নোটেশন আপনার কোডটি আসলে কতটা দক্ষ তা হিসাব করার জন্য একটি সহজ হাতিয়ার।

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

গুগলে কে আপনাকে সার্চ করে দেখতে পারেন

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

আপনি কিভাবে বিগ-ও নোটেশন গণনা করবেন

আসুন দুটি ফাংশন বিবেচনা করি যা একটি ড্রয়ারে কতগুলি মোজা রয়েছে তা গণনা করে। প্রতিটি ফাংশন মোজা জোড়া সংখ্যা গ্রহণ করে এবং পৃথক মোজা সংখ্যা প্রদান করে। কোডটি পাইথনে লেখা আছে, কিন্তু এটি প্রভাবিত করে না কিভাবে আমরা ধাপের সংখ্যা গণনা করব।

অ্যালগরিদম 1:

def sockCounter(numberOfPairs):  
 individualSocks = 0  
 for x in range(numberOfPairs):  
 individualSocks = individualSocks + 2  
 return individualSocks

অ্যালগরিদম 2:

def sockCounter(numberOfPairs):  
 return numberOfPairs * 2

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

সম্পর্কিত: প্রোগ্রামিং এর কাজ কি?

অ্যালগরিদম 1 এর অনেকগুলি ধাপ রয়েছে:

এটি পরিবর্তনশীল individualSocks কে শূন্যের মান নির্ধারণ করে।
এটি একটি ভেরিয়েবল i এর মান নির্ধারণ করে।
এটি i এর মানকে NumberOfPairs এর সাথে তুলনা করে।
এটি পৃথক সকে দুটি যোগ করে।
এটি স্বতন্ত্র শক্সের বর্ধিত মান নিজেই নির্ধারণ করে।
এটি একের পর এক বৃদ্ধি পায়।
এটি তারপর একই সংখ্যক বার (indiviualSocks - 1) এর জন্য 3 থেকে 6 ধাপের মাধ্যমে ফিরে যায়।

অ্যালগরিদমের জন্য আমাদের যে কয়টি ধাপ সম্পন্ন করতে হবে তা প্রকাশ করা যেতে পারে:

4n + 2

চারটি ধাপ আছে যা আমাদের n বার সম্পূর্ণ করতে হবে। এই ক্ষেত্রে, n numberOfPairs এর মান সমান হবে। এছাড়াও 2 টি ধাপ রয়েছে যা একবার সম্পন্ন হয়।

তুলনায়, অ্যালগরিদম 2 এর মাত্র একটি ধাপ আছে। NumberOfPairs এর মান দুই দিয়ে গুণ করা হয়। আমরা এটিকে এভাবে প্রকাশ করব:

1

যদি এটি ইতিমধ্যে স্পষ্ট না হয়, আমরা এখন সহজেই দেখতে পারি যে অ্যালগরিদম 2 বেশ কিছুটা দ্বারা আরও কার্যকর।

বিগ-ও বিশ্লেষণ

সাধারণত, যখন আপনি একটি অ্যালগরিদমের বিগ-ও স্বরলিপিতে আগ্রহী হন, আপনি সামগ্রিক দক্ষতায় বেশি আগ্রহী হন এবং ধাপের সংখ্যার সূক্ষ্ম শস্য বিশ্লেষণে কম। স্বরলিপি সহজ করার জন্য, আমরা কেবল দক্ষতার মাত্রা বলতে পারি।

উপরের উদাহরণগুলিতে, অ্যালগরিদম 2 এক হিসাবে প্রকাশ করা হবে:

O(1)

কিন্তু অ্যালগরিদম 1 সরলীকৃত হবে:

O(n)

এই দ্রুত স্ন্যাপশট আমাদের বলে যে কিভাবে অ্যালগরিদম এক এর দক্ষতা n এর মান সঙ্গে সংযুক্ত করা হয়। সংখ্যা যত বড় হবে অ্যালগরিদম তত বেশি ধাপে সম্পন্ন করতে হবে।

লিনিয়ার কোড

ছবির ক্রেডিট: নিক ফ্লেডারাস/ বিশেষ্য প্রকল্প

যেহেতু আমরা n এর মান জানি না, তাই n এর মানটি যে পরিমাণ কোড চালানোর প্রয়োজন তা প্রভাবিত করে তা চিন্তা করা আরও সহায়ক। অ্যালগরিদম 1 এ আমরা বলতে পারি যে সম্পর্কটি রৈখিক। যদি আপনি ধাপের সংখ্যা বনাম n এর মান চক্রান্ত করেন তবে আপনি একটি সরল রেখা পাবেন যা উপরে যায়।

চতুর্ভুজ কোড

সব সম্পর্ক রৈখিক উদাহরণের মতো সহজ নয়। কল্পনা করুন আপনার একটি 2D অ্যারে আছে এবং আপনি অ্যারেতে একটি মান অনুসন্ধান করতে চান। আপনি এই মত একটি অ্যালগরিদম তৈরি করতে পারেন:

def searchForValue(targetValue, arraySearched):  
 foundTarget = False  
 for x in arraySearched:  
 for y in x:  
 if(y == targetValue):  
 foundTarget = True  
 return foundTarget

এই উদাহরণে, ধাপের সংখ্যা অ্যারে অনুসন্ধানের অ্যারের সংখ্যা এবং প্রতিটি অ্যারের মানগুলির সংখ্যার উপর নির্ভর করে। সুতরাং, ধাপগুলির সরলীকৃত সংখ্যা হবে n * n বা n²।

অ্যান্ড্রয়েডের জন্য সেরা বিনামূল্যে লাইভ টিভি অ্যাপ

চিত্র ক্রেডিট: নিক ফ্লেডারাস/ বিশেষ্য প্রকল্প

এই সম্পর্কটি একটি চতুর্ভুজ সম্পর্ক, যার অর্থ হল আমাদের অ্যালগরিদমের ধাপের সংখ্যা n এর সাথে দ্রুত বৃদ্ধি পায়। বিগ-ও নোটনে, আপনি এটি লিখবেন:

O(n²)

সম্পর্কিত: সিএসএস ফাইলগুলি পরীক্ষা, পরিষ্কার এবং অপ্টিমাইজ করার জন্য দরকারী সরঞ্জাম

লগারিদমিক কোড

যদিও আরো অনেক সম্পর্ক আছে, শেষ যে সম্পর্কটি আমরা দেখব তা হল লগারিদমিক সম্পর্ক। আপনার মেমরি রিফ্রেশ করার জন্য, একটি সংখ্যার লগ হল একটি ভিত্তি দেওয়া একটি সংখ্যায় পৌঁছানোর জন্য প্রয়োজনীয় সূচক মান। উদাহরণ স্বরূপ:

log 2 (8) = 3

লগ তিনটি সমান কারণ যদি আমাদের বেস 2 ছিল, 8 নম্বর পেতে আমাদের 3 এর একটি এক্সপোনেন্ট মান প্রয়োজন হবে।

ছবির ক্রেডিট: নিক ফ্লেডারাস/ বিশেষ্য প্রকল্প

সুতরাং, একটি লগারিদমিক ফাংশনের সম্পর্ক একটি সূচকীয় সম্পর্কের বিপরীত। যেমন n বৃদ্ধি পায়, অ্যালগরিদম চালানোর জন্য কম নতুন পদক্ষেপের প্রয়োজন হয়।

প্রথম নজরে, এটি পাল্টা স্বজ্ঞাত বলে মনে হয়। কিভাবে একটি অ্যালগরিদম এর ধাপগুলি n এর চেয়ে ধীর হতে পারে? এর একটি ভাল উদাহরণ হল বাইনারি অনুসন্ধান। আসুন একটি অ্যালগরিদম বিবেচনা করি অনন্য মানের একটি অ্যারেতে একটি সংখ্যা অনুসন্ধান করার জন্য।

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

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

O(log(n))

বিগ-ও নোটেশনের গুরুত্ব

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

ফ্ল্যাশ ড্রাইভ থেকে উইন্ডোজ কিভাবে ইনস্টল করবেন

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

শেয়ার করুন শেয়ার করুন টুইট ইমেইল 10 সর্বাধিক প্রচলিত প্রোগ্রামিং এবং কোডিং ভুল

কোডিং ভুল অনেক সমস্যা হতে পারে। এই টিপস আপনাকে প্রোগ্রামিং ভুল এড়াতে এবং আপনার কোডকে অর্থপূর্ণ রাখতে সাহায্য করবে।

পরবর্তী পড়ুন সম্পর্কিত বিষয়

প্রোগ্রামিং
প্রোগ্রামিং

লেখক সম্পর্কে জেনিফার সিটন(21 নিবন্ধ প্রকাশিত)

জে সিটন একজন বিজ্ঞান লেখক যিনি জটিল বিষয়গুলো ভাঙতে পারদর্শী। তিনি সাসকাচোয়ান বিশ্ববিদ্যালয় থেকে পিএইচডি করেছেন; তার গবেষণা অনলাইনে শিক্ষার্থীদের ব্যস্ততা বাড়ানোর জন্য গেম-ভিত্তিক শিক্ষাকে কাজে লাগানোর দিকে মনোনিবেশ করেছে। যখন সে কাজ করছে না, তখন তুমি তাকে পড়বে, ভিডিও গেম খেলবে অথবা বাগান করবে।

জেনিফার সিটন থেকে আরো

আমাদের নিউজলেটার সদস্যতা

প্রযুক্তি টিপস, রিভিউ, ফ্রি ইবুক এবং এক্সক্লুসিভ ডিলের জন্য আমাদের নিউজলেটারে যোগ দিন!

সাবস্ক্রাইব করতে এখানে ক্লিক করুন