অ্যাসিম্পটোটিক চিহ্ন ব্যবহার করে কোন অ্যালগোরিদম চলার সময় n দ্বারা প্রকাশ করা হলে, কিছু বিষয়ের দিকে লক্ষ্য রাখতে হবে।
এসো সহজ কোন কিছু দিয়ে শুরু করা যাক। ধরি যে কোন ইনপুটের জন্য একটি অ্যালগোরিদমের ধ্রুবক সময় লাগে। উদাহরণস্বরূপ, যদি ঊর্ধ্বক্রমে বিন্যস্ত কোন অ্যারে থেকে সবচেয়ে ছোট উপাদান নির্ণয় করতে হয়, এর জন্য ধ্রুবক সময় দরকার, কারণ সবচেয়ে ছোট উপাদান 0 ইন্ডেক্সে রয়েছে। যেহেতু আমরা অ্যাসিম্পটোটিক চিহ্নে n ফাংশন ব্যবহার করতে চাই, তাই বলা যেতে পারে, এই অ্যালগোরিদমটি Θ(n0) \Theta(n^0) সময় চলে। কেন? কারণ n, start superscript, 0, end superscript, equals, 1 এবং অ্যালগোরিদমের চলার সময় ধ্রুবক 1 এর মধ্যেই থাকে। অনুশীলনে, Θ(n0) \Theta(n^0) লেখা হয়না, কিন্তু; Θ(1) \Theta(1) লেখা হয়।
ধরি, একটি অ্যালগোরিদমের Θ(log10n) \Theta(\log_{10} n) সময় লাগে। আমরা এভাবেও বলতে পারি যে এটির Θ(lgn) \Theta(\lg n) সময় (যা হল, Θ(log2n) \Theta(\log_2 n) সময়) লাগে। কোন লগারিদমের ভিত্তি ধ্রুবক হলে, অ্যাসিম্পটোটিক চিহ্ন ভিত্তির উপর নির্ভর করে না। কেন নয়? কারণ একটি গাণিতিক সূত্র রয়েছে যে,
log, start subscript, a, end subscript, n, equals, start fraction, log, start subscript, b, end subscript, n, divided by, log, start subscript, b, end subscript, a, end fraction
যা a, b এবং n এর সকল ধনাত্মক সংখ্যার জন্য প্রযোজ্য। সুতরাং, a এবং b ধ্রুবক হলে, log, start subscript, a, end subscript, n এবং log, start subscript, b, end subscript, n এর মধ্যকার পার্থক্য হবে শুধু log, start subscript, b, end subscript, a এবং এটি একটি ধ্রুবক যা আমরা অ্যাসিম্পটোটিক চিহ্নে বাদ দিতে পারি।
সুতরাং, বলা যায় যে, বাইনারি সার্চের ওরস্ট-কেস হল Θ(logan) \Theta(\log_a n) যেখানে a হল যে কোন ধনাত্মক ধ্রুবক। কেন? অনুমানের সংখ্যা হল সর্বোচ্চ lgn+1 \lg n + 1 , প্রতিটি অনুমান যাচাইয়ের জন্য ধ্রুবক সময় এবং এগুলো নির্ণয় করে মান রিটার্ন করায় ধ্রুবক সময় লাগে। অনুশীলনের ক্ষেত্রে, বাইনারি সার্চের Θ(lgn) \Theta(\lg n) সময় লাগে কারণ বিজ্ঞানীরা 2 এর ঘাত অনুসারে চিন্তা করতে পছন্দ কর (এবং আমাদের ।)
অ্যাসিম্পটোটিক চিহ্ন দ্বারা অ্যালগোরিদম বিশ্লেষণ করলে আমরা ফাংশনের একটি ক্রম দেখতে পাই। যদি a এবং b ধ্রুবক এবং a, is less than, b হয়, তাহলে Θ(na) \Theta(n^a) চলার সময় Θ(nb) \Theta(n^b) চলার সময় থেকে আরও ধীরে বৃদ্ধি পায়। উদাহরণস্বরূপ, Θ(n) \Theta(n) চলার সময়, যা হল Θ(n1) \Theta(n^1) , Θ(n2) \Theta(n^2) এর চলার সময় থেকে আরও ধীরে বৃদ্ধি পায়। সূচকগুলো পূর্ণসংখ্যা হওয়ার দরকার নেই। উদাহরণস্বরূপ, Θ(n2) \Theta(n^2) চলার সময় Θ(n2n) \Theta(n^2 \sqrt{n}) চলার সময় থেকে ধীরে বৃদ্ধি পায়, যা হল Θ(n2.5) \Theta(n^{2.5})
লগারিদম বহুপদী থেকে ধীরে বৃদ্ধি পায়। অর্থাৎ, Θ(na) \Theta(n^a) থেকে Θ(lgn) \Theta(\lg n) আরও ধীরে বৃদ্ধি পায় যেখানে যে কোন ধনাত্মক ধ্রুবক হল a। কিন্তু যেহেতু n এর বৃদ্ধির সাথে সাথে lgn \lg n এর মান বৃদ্ধি পায়, Θ(1) \Theta(1) থেকে Θ(lgn) \Theta(\lg n) দ্রুত বৃদ্ধি পায়।
অ্যাসিম্পটোটিক চিহ্নে অ্যালগোরিদম বিশ্লেষণের সময় আমরা একটি ফাংশনের তালিকা দেখতে পাই, তালিকায় ফাংশনগুলো ধীর থেকে দ্রুত ক্রমে সাজানো। এই তালিকাটি শেষ নয়; আরও অনেক অ্যালগোরিদম আছে যার চলার সময় এখানে দেখা যায় না:
  1. Θ(1) \Theta(1)
  2. Θ(lgn) \Theta(\lg n)
  3. Θ(nlgn) \Theta(n \lg n)
  4. Θ(n2) \Theta(n^2)
  5. Θ(n2lgn) \Theta(n^2 \lg n)
  6. Θ(n3) \Theta(n^3)
  7. Θ(2n) \Theta(2^n)
লক্ষ্য করি, একটি সূচকীয় ফাংশন a, start superscript, n, end superscript, যেখানে a, is greater than, 1, যে কোন বহুপদী ফাংশন n, start superscript, b, end superscript থেকে দ্রুত বৃদ্ধি পায়, যেখানে b হল যে কোন ধ্রুবক।

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