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

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

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

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

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

আপনি কীভাবে বিগ-ও স্বরলিপি গণনা করবেন

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

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

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

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

 def sockCounter(numberOfPairs):
return numberOfPairs * 2

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

সম্পর্কিত: প্রোগ্রামিং একটি ফাংশন কি?

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

  1. এটি ভেরিয়েবল ইন্ডিস্টকসকে শূন্যের মান নির্ধারণ করে।
  2. এটি ভেরিয়েবলের জন্য একটির মান নির্ধারণ করে।
  3. এটি i এর মানটি অফফায়ারের সংখ্যার সাথে তুলনা করে।
  4. এটি স্বতন্ত্রসকে দুটি যুক্ত করে।
  5. এটি নিজের কাছে পৃথকসোকের বর্ধিত মান নির্ধারণ করে।
  6. এটি একের পর এক বৃদ্ধি করে।
  7. এরপরে এটি একই সংখ্যার জন্য 3 থেকে 6 ধাপে ফিরে ফিরে আসে (indiviualSocks – 1)।

অ্যালগোরিদমের জন্য আমাদের যে ধাপগুলি শেষ করতে হবে তা এই হিসাবে প্রকাশ করা যেতে পারে:

 4n + 2

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

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

 1

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

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

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

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

 O(1)

তবে অ্যালগরিদম 1 এটিকে সরল করা হবে:

 O(n)

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

লিনিয়ার কোড

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

চতুর্মুখী কোড

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

 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²)

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

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

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

 log 2 (8) = 3

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

সুতরাং, লগারিদমিক ফাংশনের সম্পর্কটি হ'ল ঘনিষ্ঠ সম্পর্কের বিপরীত। N বাড়ার সাথে সাথে অ্যালগরিদমটি চালানোর জন্য কয়েকটি নতুন পদক্ষেপের প্রয়োজন।

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

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

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

 O(log(n))

বিগ-ও স্বরলিপিটির গুরুত্ব

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

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