جزوه کاربرد کامپیوتر در حسابداری ۳
دانلود فایل
 
 
 
 
 
 
 
 
 
درج های اولیه num(T) را انجام می دهد. جزوه کاربرد کامپیوتر در حسابداری ۳
برای تجزیه و تحلیل با استفاده از روش حسابداری، ما به هر درج جدول ۳ پرداخت اختصاص می دهیم. اگرچه دلیل این امر در حال حاضر مشخص نیست، اما در جریان تحلیل مشخص خواهد شد.
فرض کنید در ابتدا جدول با اندازه (T) = m خالی است. بنابراین اولین درج‌های m نیازی به تخصیص مجدد ندارند و فقط ۱ هزینه دارند (برای درج اولیه). جزوه کاربرد کامپیوتر در حسابداری ۳
درج عنصر m + 1 مستلزم تخصیص مجدد جدول است. ایجاد جدول جدید در خط ۳ (در حال حاضر) رایگان است. حلقه در خط ۴ به m درج اولیه نیاز دارد، برای هزینه m. با احتساب درج در خط آخر، کل هزینه این عمل m + 1 است. پس از این عملیات، استخر دارای ۲m + 3 – (m + 1) = m + 2 است.
بعد، عناصر m – 1 دیگری را به جدول اضافه می کنیم. در این مرحله استخر دارای m + 2 + 2 × (m – 1) = 3m است. قرار دادن یک عنصر اضافی (یعنی عنصر ۲m + 1) می تواند هزینه ۲m + 1 و پرداخت ۳ را مشاهده کند. جزوه کاربرد کامپیوتر در حسابداری ۳ پس از این عملیات، استخر دارای ۳m + 3 – (2m + 1) = m + 2 است. که این مقدار همان مقدار پس از درج عنصر m + 1 است. در واقع، ما می توانیم نشان دهیم که این مورد برای هر تعداد تخصیص مجدد خواهد بود.
اکنون می توان روشن کرد که چرا پرداخت برای درج ۳ است. ۱ برای اولین درج عنصر پرداخت می کند، ۱ برای جابجایی عنصر دفعه بعد که جدول گسترش می یابد و ۱ برای جابجایی عنصر قدیمی در دفعه بعد هزینه می پردازد. جدول گسترش یافته است به طور شهودی، این توضیح می‌دهد که چرا سهم یک عنصر بدون در نظر گرفتن چند بار باز شدن جدول، هرگز «تمام» نمی‌شود: از آنجایی که جدول همیشه دو برابر می‌شود، جدیدترین نیمه همیشه هزینه جابجایی قدیمی‌ترین نیمه را پوشش می‌دهد. جزوه کاربرد کامپیوتر در حسابداری ۳
ما در ابتدا فرض کردیم که ایجاد جدول رایگان است. در واقعیت، ایجاد جدولی با اندازه n ممکن است به اندازه O(n) گران باشد. بیایید بگوییم که هزینه ایجاد جدول با اندازه n n است. آیا این هزینه جدید مشکلی ایجاد می کند؟ نه واقعا؛ به نظر می رسد که ما از همین روش برای نشان دادن کران O(1) مستهلک شده استفاده می کنیم. تنها کاری که باید انجام دهیم این است که پرداخت را تغییر دهیم.

پاسخ دهید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *