এ্যাসিম্প্টোটিক নোটেশানে বিভিন্ন ফাংশন

অ্যাসিম্পটোটিক চিহ্ন ব্যবহার করে কোন অ্যালগোরিদম চলার সময় $n$‍ দিয়ে প্রকাশ করা হলে, কিছু বিষয়ের দিকে লক্ষ্য রাখতে হবে।

এসো সহজ কোন কিছু দিয়ে শুরু করা যাক। ধরি যে কোন ইনপুটের জন্য একটি অ্যালগোরিদমের ধ্রুবক সময় লাগে। উদাহরণস্বরূপ, যদি ঊর্ধ্বক্রমে বিন্যস্ত কোন অ্যারে থেকে সবচেয়ে ছোট উপাদান নির্ণয় করতে হয়, এর জন্য ধ্রুবক সময় দরকার, কারণ সবচেয়ে ছোট উপাদান 0 ইন্ডেক্সে রয়েছে। যেহেতু আমরা অ্যাসিম্পটোটিক চিহ্নে $n$‍ ফাংশন ব্যবহার করতে চাই, তাই বলা যেতে পারে, এই অ্যালগোরিদমটি $\mathrm{\Theta }(n^0)$‍ সময় চলে। কেন? কারণ $n^0=1$‍ এবং অ্যালগোরিদমের চলার সময় ধ্রুবক 1 এর মধ্যেই থাকে। অনুশীলনে, $\mathrm{\Theta }(n^0)$‍ লেখা হয়না, কিন্তু; $\mathrm{\Theta }(1)$‍ লেখা হয়।

Now suppose an algorithm took $\mathrm{\Theta }({\log }_{10}n)$‍ time. You could also say that it took $\mathrm{\Theta }({\log }_{2}n)$‍ time. Whenever the base of the logarithm is a constant, it doesn't matter what base we use in asymptotic notation. Why not? Because there's a mathematical formula that says

যা $a$‍, $b$‍ এবং $n$‍ এর সকল ধনাত্মক সংখ্যার জন্য প্রযোজ্য। সুতরাং, $a$‍ এবং $b$‍ ধ্রুবক হলে, ${\log }_{a}n$‍ এবং ${\log }_{b}n$‍ এর মধ্যকার পার্থক্য হবে শুধু ${\log }_{b}a$‍ এবং এটি একটি ধ্রুবক যা আমরা অ্যাসিম্পটোটিক চিহ্নে বাদ দিতে পারি।

Therefore, we can say that the worst-case running time of binary search is $\mathrm{\Theta }({\log }_{a}n)$‍ for any positive constant $a$‍. Why? The number of guesses is at most ${\log }_{2}n+1$‍, generating and testing each guess takes constant time, and setting up and returning take constant time. However, as a matter of practice, we often write that binary search takes $\mathrm{\Theta }({\log }_{2}n)$‍ time because computer scientists like to think in powers of 2.

অ্যাসিম্পটোটিক চিহ্ন দিয়ে অ্যালগোরিদম বিশ্লেষণ করলে আমরা ফাংশনের একটি ক্রম দেখতে পাই। যদি $a$‍ এবং $b$‍ ধ্রুবক এবং $a<b$‍ হয়, তাহলে $\mathrm{\Theta }(n^a)$‍ চলার সময় $\mathrm{\Theta }(n^b)$‍ চলার সময় থেকে আরও ধীরে বৃদ্ধি পায়। উদাহরণস্বরূপ, $\mathrm{\Theta }(n)$‍ চলার সময়, যা হল $\mathrm{\Theta }(n^1)$‍, $\mathrm{\Theta }(n^2)$‍ এর চলার সময় থেকে আরও ধীরে বৃদ্ধি পায়। সূচকগুলো পূর্ণসংখ্যা হওয়ার দরকার নেই। উদাহরণস্বরূপ, $\mathrm{\Theta }(n^2)$‍ চলার সময় $\mathrm{\Theta }(n^2\sqrt{n})$‍ চলার সময় থেকে ধীরে বৃদ্ধি পায়, যা হল $\mathrm{\Theta }(n^{2.5})$‍।

The following graph compares the growth of $n$‍,$n^2$‍, and $n^{2.5}$‍:

Logarithms grow more slowly than polynomials. That is, $\mathrm{\Theta }({\log }_{2}n)$‍ grows more slowly than $\mathrm{\Theta }(n^a)$‍ for any positive constant $a$‍. But since the value of ${\log }_{2}n$‍ increases as $n$‍ increases, $\mathrm{\Theta }({\log }_{2}n)$‍ grows faster than $\mathrm{\Theta }(1)$‍.

The following graph compares the growth of $1$‍, $n$‍, and ${\log }_{2}n$‍:

Here's a list of functions in asymptotic notation that we often encounter when analyzing algorithms, ordered by slowest to fastest growing:

Note that an exponential function $a^n$‍, where $a>1$‍, grows faster than any polynomial function $n^b$‍, where $b$‍ is any constant.

The list above is not exhaustive, there are many functions with running times not listed there. You'll hopefully run into a few of those in your computer science journey.

এই বিষয়বস্তুটি Dartmouth Computer Science এর প্রফেসর Thomas Cormen এবং Devin Balkcom এর সহযোগিতায় এবং একই সাথে খান একাডেমির কম্পিউটিং শিক্ষাক্রম দলের একসাথে কাজ করার মাধ্যমে তৈরি করা হয়েছে। এই বিষয়বস্তু CC-BY-NC-SA দিয়ে লাইসেন্সকৃত।