C++ এ সময় জটিলতা বিশ্লেষণের প্রশ্ন অনুশীলন করুন

সময় জটিলতা যেকোন অ্যালগরিদম হল অ্যালগরিদম সম্পূর্ণ হতে সময় নেয়। অ্যালগরিদমের কার্যকারিতা এবং তুলনামূলক বিশ্লেষণের জন্য এটি একটি গুরুত্বপূর্ণ মেট্রিক। আমরা অ্যালগরিদমের সময় জটিলতা কমানোর প্রবণতা রাখি যা এটিকে আরও কার্যকর করে তোলে৷

উদাহরণ 1

নিম্নলিখিত কোড স্নিপেটগুলির সময় জটিলতা খুঁজুন

for(i= 0 ; i < n; i++){
   cout<< i << " " ;
   i++;
}

লুপের সর্বোচ্চ মান n আছে কিন্তু i ফর লুপে দুবার বৃদ্ধি করা হবে যার ফলে সময় অর্ধেক লাগবে। তাই সময়ের জটিলতা হল O(n/2) যা O(n) এর সমতুল্য।

উদাহরণ 2

নিম্নলিখিত কোড স্নিপেটগুলির সময় জটিলতা খুঁজুন

for(i= 0 ; i < n; i++){
   for(j = 0; j<n ;j++){
      cout<< i << " ";
   }
}

অভ্যন্তরীণ লুপ এবং বাইরের লুপ উভয়ই n বার সম্পাদন করছে। তাই i এর একক মানের জন্য, j n বার লুপ করছে, i এর n মানের জন্য, j মোট n*n =n 2 বার লুপ করবে। তাই সময়ের জটিলতা হল O(n 2).

উদাহরণ 3

নিম্নলিখিত কোড স্নিপেটগুলির সময় জটিলতা খুঁজুন

int i = n;
while(i){
   cout << i << " ";
   i = i/2;
}

এই ক্ষেত্রে, প্রতিটি পুনরাবৃত্তির পরে i এর মান তার আগের মানের অর্ধেক হয়ে যায়। তাই সিরিজটি এরকম হবে:. তাই সময়ের জটিলতা হল O(log n).

উদাহরণ 4

নিম্নলিখিত কোড স্নিপেটগুলির সময় জটিলতা খুঁজুন

if(i > j ){
   j>23 ? cout<<j : cout<<i;
}

কোডে দুটি শর্তসাপেক্ষ বিবৃতি আছে। প্রতিটি শর্তসাপেক্ষ বিবৃতির সময় জটিলতা থাকে =O(1), তাদের মধ্যে দুটির জন্য এটি O(2) যা O(1) এর সমতুল্য যা ধ্রুবক .

উদাহরণ 5

নিম্নলিখিত কোড স্নিপেটগুলির সময় জটিলতা খুঁজুন

for(i= 0; i < n; i++){
   for(j = 1; j < n; j = j*2){
      cout << i << " ";
   }
}

অভ্যন্তরীণ লুপটি নির্বাহ করছে (লগ n) বার যেখানে বাইরেরটি n বার নির্বাহ করছে। সুতরাং i-এর একক মানের জন্য, j কার্য সম্পাদন করছে (log n) বার, i-এর n মানের জন্য, j মোট n*(log n) =(n log n) বার লুপ করবে। তাই সময়ের জটিলতা হল O(n log n).