EITC/IS/CCTF কম্পিউটেশনাল কমপ্লেসিটি থিওরি ফান্ডামেন্টালস

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

সময় হল সবচেয়ে বেশি বিবেচিত সম্পদ। যখন "জটিলতা" শব্দটি কোয়ালিফায়ার ছাড়া ব্যবহার করা হয়, তখন এটি সাধারণত সময়ের জটিলতাকে বোঝায়।

সময়ের ঐতিহ্যগত একক (সেকেন্ড, মিনিট, এবং তাই) জটিলতা তত্ত্বে নিযুক্ত করা হয় না কারণ তারা নির্বাচিত কম্পিউটার এবং প্রযুক্তির অগ্রগতির উপর খুব নির্ভরশীল। উদাহরণস্বরূপ, একটি কম্পিউটার আজ 1960 এর দশকের একটি কম্পিউটারের তুলনায় যথেষ্ট দ্রুত একটি অ্যালগরিদম কার্যকর করতে পারে, তবুও, এটি অ্যালগরিদমের অন্তর্নিহিত গুণের পরিবর্তে কম্পিউটার হার্ডওয়্যারে প্রযুক্তিগত অগ্রগতির কারণে। জটিলতা তত্ত্বের লক্ষ্য হল অ্যালগরিদমগুলির অন্তর্নিহিত সময়ের প্রয়োজন বা মৌলিক সময়ের সীমাবদ্ধতাগুলিকে পরিমাপ করা যা একটি অ্যালগরিদম যেকোনো কম্পিউটারে আরোপ করবে। গণনার সময় কতগুলি মৌলিক অপারেশন সঞ্চালিত হয় তা গণনা করে এটি সম্পন্ন করা হয়। এই পদ্ধতিগুলিকে সাধারণত পদক্ষেপ হিসাবে উল্লেখ করা হয় কারণ এগুলি একটি নির্দিষ্ট মেশিনে ধ্রুবক সময় নেয় বলে মনে করা হয় (অর্থাৎ, তারা ইনপুটের পরিমাণ দ্বারা প্রভাবিত হয় না)।

আরেকটি গুরুত্বপূর্ণ সম্পদ হল অ্যালগরিদম সম্পাদন করার জন্য প্রয়োজনীয় কম্পিউটার মেমরির পরিমাণ।

আরেকটি প্রায়শই ব্যবহৃত সম্পদ হল গাণিতিক ক্রিয়াকলাপের পরিমাণ। এই পরিস্থিতিতে, "পাটিগণিত জটিলতা" শব্দটি ব্যবহৃত হয়। সময় জটিলতা সাধারণত একটি ধ্রুবক ফ্যাক্টর দ্বারা গাণিতিক জটিলতার পণ্য হয় যদি একটি গণনার সময় ঘটে যাওয়া সংখ্যাগুলির বাইনারি উপস্থাপনার আকারের উপর একটি ঊর্ধ্ব সীমাবদ্ধতা জানা যায়।

একটি গণনার সময় ব্যবহৃত পূর্ণসংখ্যার আকার অনেক পদ্ধতির জন্য সীমাবদ্ধ নয়, এবং এটি অনুমান করা অবাস্তব যে গাণিতিক ক্রিয়াকলাপগুলির জন্য একটি নির্দিষ্ট সময়ের প্রয়োজন হয়। ফলস্বরূপ, সময়ের জটিলতা, যা বিট জটিলতা নামেও পরিচিত, পাটিগণিত জটিলতার চেয়ে উল্লেখযোগ্যভাবে বেশি হতে পারে। একটি nn পূর্ণসংখ্যা ম্যাট্রিক্সের নির্ধারক গণনার গাণিতিক অসুবিধা, উদাহরণস্বরূপ, মান কৌশলের জন্য O(n^3) (গাউসিয়ান নির্মূল)। কারণ গননার সময় সহগগুলির আকার দ্রুতগতিতে প্রসারিত হতে পারে, একই পদ্ধতির বিট জটিলতা n এ সূচকীয়। যদি এই কৌশলগুলি মাল্টি-মডুলার পাটিগণিতের সাথে একত্রে ব্যবহার করা হয়, তবে বিট জটিলতা O(n^4) এ হ্রাস করা যেতে পারে।

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

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

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

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

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

এই কারণে, উচ্চ n-এর জন্য জটিলতার আচরণের দিকে সবচেয়ে বেশি মনোযোগ দেওয়া হয়, অর্থাৎ, n অসীমের কাছে যাওয়ার সাথে সাথে এর অ্যাসিম্পটোটিক আচরণ। ফলস্বরূপ, বৃহৎ O স্বরলিপি সাধারণত জটিলতা নির্দেশ করতে ব্যবহৃত হয়।

কম্পিউটেশনাল মডেল

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

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

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

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

এমনকি যদি এই ধরনের একটি গণনা মডেল বর্তমানে ব্যবহারযোগ্য না হয়, তবে এটির তাত্ত্বিক তাত্পর্য রয়েছে, বিশেষ করে P = NP সমস্যার সাথে, যা জিজ্ঞাসা করে যে "পলিনমিয়াল টাইম" এবং "নন-ডিটারমিনিস্টিক বহুপদী সময়" ব্যবহার করে উত্পাদিত জটিলতা শ্রেণীগুলি অন্তত উচ্চতর সীমা একই। একটি নির্ধারক কম্পিউটারে, একটি NP-অ্যালগরিদম অনুকরণ করার জন্য "সূচক সময়" প্রয়োজন। যদি একটি অনির্ধারিত পদ্ধতিতে বহুপদী সময়ে একটি কাজ সমাধান করা যায় তবে এটি NP অসুবিধা শ্রেণীর অন্তর্গত। যদি একটি সমস্যা NP-এ থাকে এবং অন্য যেকোন NP সমস্যার চেয়ে সহজ না হয়, তাহলে এটিকে NP-সম্পূর্ণ বলা হয়। ন্যাপস্যাক সমস্যা, ট্রাভেলিং সেলসম্যান সমস্যা, এবং বুলিয়ান সন্তুষ্টি সমস্যা সবই এনপি-সম্পূর্ণ কম্বিনেটরিয়াল সমস্যা। এই সমস্ত সমস্যার জন্য সবচেয়ে সুপরিচিত অ্যালগরিদমের সূচকীয় জটিলতা রয়েছে। যদি এই সমস্যাগুলির যেকোন একটি নির্ধারক মেশিনে বহুপদী সময়ে সমাধান করা যায়, তাহলে সমস্ত NP সমস্যা বহুপদী সময়েও সমাধান করা যেতে পারে এবং P = NP প্রতিষ্ঠিত হবে। 2017 সালের হিসাবে, এটি ব্যাপকভাবে অনুমান করা হয় যে P NP, যা বোঝায় যে NP সমস্যার সবচেয়ে খারাপ পরিস্থিতিগুলি সমাধান করা মৌলিকভাবে কঠিন, অর্থাৎ, আকর্ষণীয় ইনপুট দৈর্ঘ্য প্রদত্ত যেকোনো সম্ভাব্য সময়কাল (দশক) থেকে অনেক বেশি সময় নেয়।

সমান্তরাল এবং বিতরণ করা কম্পিউটিং

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

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

এইভাবে মূল জটিলতার সমস্যাটি হল অ্যালগরিদম তৈরি করা যাতে প্রসেসরের সংখ্যা অনুসারে কম্পিউটিং সময়ের পণ্যটি একটি একক প্রসেসরে একই গণনা করার জন্য প্রয়োজনীয় সময়ের যতটা সম্ভব কাছাকাছি থাকে।

কোয়ান্টাম গণনা

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

কোয়ান্টাম জটিলতা তত্ত্বটি কোয়ান্টাম কম্পিউটার দ্বারা সমাধান করা যেতে পারে এমন বিভিন্ন ধরণের সমস্যাগুলি তদন্ত করার জন্য তৈরি করা হয়েছিল। এটি পোস্ট-কোয়ান্টাম ক্রিপ্টোগ্রাফিতে ব্যবহার করা হয়, যা ক্রিপ্টোগ্রাফিক প্রোটোকল তৈরি করার প্রক্রিয়া যা কোয়ান্টাম কম্পিউটার আক্রমণের বিরুদ্ধে প্রতিরোধী।

সমস্যার জটিলতা (নিম্ন সীমানা)

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

ফলস্বরূপ, বড় ও স্বরলিপিতে প্রদত্ত যেকোন জটিলতা অ্যালগরিদম এবং সহগামী সমস্যা উভয়েরই একটি জটিলতাকে উপস্থাপন করে।

অন্যদিকে, সমস্যা জটিলতার জন্য অতুচ্ছ নিম্ন সীমানা অর্জন করা প্রায়শই কঠিন, এবং এটি করার জন্য কয়েকটি কৌশল রয়েছে।

বেশিরভাগ সমস্যা সমাধানের জন্য, সমস্ত ইনপুট ডেটা পড়তে হবে, যা ডেটার মাত্রার সমানুপাতিক সময় নেয়। ফলস্বরূপ, এই ধরনের সমস্যাগুলির অন্তত রৈখিক জটিলতা থাকে, বা বড় ওমেগা স্বরলিপিতে, Ω(n) এর জটিলতা থাকে।

কিছু সমস্যা, যেমন কম্পিউটার বীজগণিত এবং গণনামূলক বীজগণিত জ্যামিতির, খুব বড় সমাধান রয়েছে। কারণ আউটপুট লিখতে হবে, জটিলতা আউটপুটের সর্বাধিক আকার দ্বারা সীমাবদ্ধ।

একটি সাজানোর অ্যালগরিদমের জন্য প্রয়োজনীয় তুলনার সংখ্যার Ω(nlogn) এর একটি অরৈখিক নিম্ন সীমা রয়েছে। ফলস্বরূপ, সেরা সাজানোর অ্যালগরিদমগুলি সবচেয়ে কার্যকর কারণ তাদের জটিলতা হল O(nlogn)৷ আসলে এন আছে! n জিনিসগুলিকে সংগঠিত করার উপায়গুলি এই নিম্ন সীমার দিকে নিয়ে যায়। কারণ প্রতিটি তুলনা n-এর এই সংগ্রহকে ভাগ করে! অর্ডার দুটি টুকরো করে, সমস্ত অর্ডার আলাদা করার জন্য N তুলনার সংখ্যা অবশ্যই 2N > n! হতে হবে, স্টার্লিং এর সূত্র দ্বারা O(nlogn) বোঝায়।

একটি সমস্যাকে অন্য সমস্যায় হ্রাস করা কম জটিলতা সীমাবদ্ধতা পাওয়ার জন্য একটি সাধারণ কৌশল।

অ্যালগরিদম উন্নয়ন

একটি অ্যালগরিদমের জটিলতা মূল্যায়ন করা ডিজাইন প্রক্রিয়ার একটি গুরুত্বপূর্ণ উপাদান কারণ এটি প্রত্যাশিত কর্মক্ষমতা সম্পর্কে দরকারী তথ্য প্রদান করে।

এটি একটি ঘন ঘন ভুল বোঝাবুঝি যে, মুরের আইনের ফলে, যা আধুনিক কম্পিউটার শক্তির সূচকীয় বৃদ্ধির পূর্বাভাস দেয়, অ্যালগরিদমের জটিলতার মূল্যায়ন কম প্রাসঙ্গিক হয়ে উঠবে। এটি ভুল কারণ বর্ধিত শক্তি বিপুল পরিমাণ ডেটা (বড় ডেটা) প্রক্রিয়াকরণের অনুমতি দেয়। উদাহরণ স্বরূপ, যেকোন অ্যালগরিদম এক সেকেন্ডেরও কম সময়ে ভালোভাবে কাজ করবে যখন বর্ণানুক্রমিকভাবে কয়েকশত এন্ট্রির তালিকা বাছাই করা হবে, যেমন একটি বইয়ের গ্রন্থপঞ্জি। অন্যদিকে, এক মিলিয়ন এন্ট্রির জন্য (উদাহরণস্বরূপ, একটি বড় শহরের ফোন নম্বর), যে মৌলিক অ্যালগরিদমগুলির জন্য O(n2) তুলনার প্রয়োজন হয় তাদের একটি ট্রিলিয়ন তুলনা করতে হবে, যা 10 গতিতে তিন ঘন্টা সময় নেবে। প্রতি সেকেন্ডে মিলিয়ন তুলনা। Quicksort এবং মার্জ সর্ট, অন্যদিকে, শুধুমাত্র nlogn তুলনার প্রয়োজন হয় (পূর্বের জন্য গড়-কেস জটিলতা হিসাবে, পরেরটির জন্য সবচেয়ে খারাপ-কেস জটিলতা হিসাবে)। এটি n = 30,000,000 এর জন্য প্রায় 1,000,000 তুলনা তৈরি করে, যা প্রতি সেকেন্ডে 3 মিলিয়ন তুলনাতে মাত্র 10 সেকেন্ড সময় নেয়।

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