ডেটা স্ট্রাকচারে অ্যারে ডাবলিং

কখনও কখনও আমরা ডায়নামিক মেমরি বরাদ্দ ব্যবহার করে অ্যারে তৈরি করি। যদি গতিশীল মেমরি বরাদ্দকরণ কৌশল ব্যবহার করে অ্যারে বরাদ্দ করা হয়, আমরা কিছু ক্রিয়াকলাপ সম্পাদন করে অ্যারের আকার দ্বিগুণ করতে পারি।

ধরুন প্রাথমিক অ্যারের আকার ছিল 5।

অ্যারে

অ্যারে দ্বিগুণ করার পরে, আকার হল −

n আকারের অ্যারের অ্যারের আকার দ্বিগুণ করতে, arr[0…n-1]। প্রথমে আমাদের আকারের একটি নতুন অ্যারে তৈরি করতে হবে বলে m। তারপর arr থেকে নতুন অ্যারেতে n উপাদান কপি করুন। অবশেষে নতুন অ্যারে নির্দেশ করতে arr-এর মান পরিবর্তন করুন।

m আকারের একটি অ্যারে তৈরি করতে, এতে θ(m) সময় লাগবে। কারণ এটি কিছু ডিফল্ট মান দিয়ে শুরু করা হবে। তারপরে পুরানো অ্যারে থেকে নতুন অ্যারেতে অনুলিপি করতে অতিরিক্ত θ(n) সময় লাগবে। কাজেই অপারেশনে θ(m + n) সময় লাগে। অ্যারে পূর্ণ হলে এই অপারেশনটি হচ্ছে৷ এবং সাধারণত m মান 2n এর মতই হয়। সুতরাং জটিলতা হল θ(2n + n) =θ(3n) θ(n) এর সমতুল্য। কিন্তু এই অপারেশন ব্যয়বহুল হিসাবে বিবেচিত হয়। যাইহোক, এই ক্রিয়াকলাপটি পরবর্তী n পুনরাবৃত্তির উপর পরিমাপ করা হয়, তারপর এটি প্রতি পুনরাবৃত্তিতে শুধুমাত্র θ(1) সময় যোগ করে। তাই আমরা বুঝতে পারি যে অ্যারের আকার ধ্রুবক ফ্যাক্টরে বৃদ্ধি করলে তা অ্যাসিম্পোটিক জটিলতাকে বিরূপভাবে প্রভাবিত করে না।