বড় ও নোটেশন: এটা কি এবং কেন এটা গুরুত্বপূর্ণ?

এটি একটি মজার এক! বিগ ও-এর সাথে যোগাযোগ করা হল প্রথম দিকের কেরিয়ার ডেভের জন্য প্রথম মুখ-গলে যাওয়া পরিবর্তনগুলির মধ্যে একটি।

আসুন কেন তাকান.

কিন্তু প্রথম, একটি পিট স্টপ. আপনি গ্রেড স্কুল থেকে যারা একেবারে হাস্যকর শব্দ সমস্যা মনে আছে?

স্যালি মুদি দোকানে গিয়ে 37টি তরমুজ কিনেছিলেন। তার 20 ডলার ছিল। প্রতিটি তরমুজের দাম $0.70। সে যখন বাড়ি পায় তখন স্যালির কাছে কত টাকা থাকে?

আপনি কি ভাবছেন, "বিশ্বে কীভাবে স্যালি বাড়ি ফিরবে? 37টি তরমুজ দিয়ে?! তরমুজের জন্য পর্যাপ্ত জায়গা সহ একটি উবার পেতে $6.00 যথেষ্ট হবে না... স্যালি কী করছেন?!"

সিলি স্যালি।

কেউ কেউ বলছেন, এতে গাছের জন্য বন হারাচ্ছে। আমি বলি এটি অনুশীলনের সমস্যাগুলি তৈরি করার জন্য একটি ভয়ঙ্কর অলস উপায়।

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

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

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

আমার কি এখন রাস্তা পার হতে হবে? একটি গাড়ী আছে? না? ঠিক আছে, ক্রস.

বিমূর্ত মধ্যে যুক্তি যখন এটা করবেন না!

সংজ্ঞা, দ্রুত

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

O(1) - "ধ্রুবক সময়"

ইনপুট কত বড় তা বিবেচ্য নয়, সিস্টেম সবসময় একই সময়ে ফলাফল প্রদান করে।

O(log n) - "লগ টাইম"

যেহেতু সমাধান (বা অ্যালগরিদম) ইনপুটের উপর পুনরাবৃত্তি করে, প্রতিটি পুনরাবৃত্তি দ্রুততর হয়!

O(n) - "লিনিয়ার টাইম"

অ্যালগরিদম পুনরাবৃত্তি হওয়ার সাথে সাথে প্রতিটি পুনরাবৃত্তি আগের পুনরাবৃত্তির মতো একই পরিমাণ সময় নেয়।

O(n log n) - এখানে কোন অভিনব পরিভাষা নেই

দেখায় যে ধারণাগুলি একত্রিত করা যেতে পারে (হ্যাঁ)। যেহেতু আমরা পুনরাবৃত্তি করি, প্রতিটি পুনরাবৃত্তি ধীর হয়ে যায় কিন্তু মোটামুটি ধীরে ধীরে ধীরে ধীরে হয়।

O(n^2) - "n বর্গাকার"

প্রতিটি পুনরাবৃত্তির জন্য, পুনরাবৃত্তিগুলি খুব দ্রুত ধীর হয়ে যায়।

O(n!) - "n ফ্যাক্টরিয়াল"

প্রতিটি পুনরাবৃত্তির জন্য, পুনরাবৃত্তিগুলি খুব দ্রুত ধীর হয়ে যায়।

লক্ষ্য হল "n ফ্যাক্টরিয়াল" থেকে যতটা সম্ভব দূরে থাকার চেষ্টা করা এবং কনস্ট্যান্টের চেয়ে বেশি খারাপ না হওয়ার চেষ্টা করা।

যে সমস্ত বোঝার সাথে, আসুন এখন ব্যবধানটি পূরণ করার চেষ্টা করি।

কংক্রিট এবং বিমূর্ত চিন্তার মধ্যে ব্যবধান সেতু করা

বিগ হে নোটেশন বোঝা

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

উদাহরণস্বরূপ, O(n) জটিলতা সহ একটি অ্যালগরিদমের রান টাইম ইনপুটের আকারের সাথে রৈখিকভাবে বৃদ্ধি পাবে।

কংক্রিট বনাম বিমূর্ত চিন্তা

চ্যালেঞ্জ দেখা দেয় যখন ডেভেলপাররা অ্যালগরিদম সম্পর্কে যুক্তির জন্য নির্দিষ্ট ডেটা সম্পর্কে ভুল করে। শব্দগুচ্ছ যেমন, "কিন্তু এই ডেটা বাস্তব," এই বিভ্রান্তির সংকেত দিতে পারে।

প্রকৃত ডেটা সম্পর্কে যুক্তি আপনাকে শুরু করতে সাহায্য করতে পারে, বর্তমান ইনপুট থেকে সমাধানটি আলাদা করা গুরুত্বপূর্ণ।

কেন ভুল বোঝাবুঝি?

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

ব্যবহারিক পরিণতি

যখন ইনপুট 100 বা 100,000 গুণ বৃদ্ধি পায়, তখন অ্যালগরিদমের কী হবে? একটি অবিশ্বাস্যভাবে জটিল সমাধান জটিলতা একটি বড় ডেটাসেটের সাথে আলাদা হয়ে যেতে পারে।

একটি অ্যালগরিদম যা ছোট ডেটা সেটগুলির জন্য সূক্ষ্ম বলে মনে হয় তা বড়গুলির সাথে নাটকীয়ভাবে ব্যর্থ হতে পারে, যার ফলে কর্মক্ষমতা সমস্যা এবং অন্যান্য চ্যালেঞ্জ হতে পারে৷

বিমূর্ত চিন্তা করতে শেখা

সমস্যাগুলি সম্পর্কে বিমূর্তভাবে চিন্তা করার ক্ষমতা বিকাশের জন্য অনুশীলন এবং নির্দেশনা প্রয়োজন। কিছু কৌশল অন্তর্ভুক্ত:

• বিমূর্ত মডেল তৈরি করা : একটি সাধারণ উপায়ে সমস্যাগুলি উপস্থাপন করা।

• ডেটা থেকে আলাদাভাবে অ্যালগরিদম বিশ্লেষণ করা : নির্দিষ্ট ডেটা পয়েন্ট নির্বিশেষে অ্যালগরিদম কীভাবে আচরণ করে তা মূল্যায়ন করা।

• বিল্ডিং স্কেলিং দৃশ্যকল্প : বিভিন্ন আকারের ইনপুট সহ অ্যালগরিদম কীভাবে কাজ করবে তা কল্পনা করা।

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

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

জটিল সমস্যার প্রায়ই জটিল সমাধানের প্রয়োজন হয় না। (স্যালির সম্ভবত শুরু করার জন্য 37টি তরমুজের প্রয়োজন ছিল না… সে 37টি তরমুজ দিয়ে কী করবে?!)