مروری بر ساختمان داده ها و الگوریتم
ساختمان داده ها یک روش سیستماتیک برای سازماندهی داده ها به منظور استفاده موثرتر از آن ها می باشد. اصطلاحات زیر اساس یک ساختمان داده هستند.
- رابط (Interface) : هر ساختمان داده یک رابط دارد که نشان دهنده مجموعه عملیات های پشتیبانی شده توسط ساختمان داده است. یک رابط فقط فهرست عملیات پشتیبانی شده، نوع پارامترهای قابل پذیرش و نوع عملیات بازگشتی را فراهم می کند.
- پیاده سازی (Implementation) : پیاده سازی نمای داخلی یک ساختمان داده و تعریف الگوریتم های مورد استفاده در عملیات های ساختمان داده را فراهم می کند.
مشخصات ساختمان داده
- درستی (Correctness) : اجرای یک ساختمان داده باید رابط (Interface) آن را به درستی پیاده سازی کند.
- پیچیدگی زمان (Time Complexity) : زمان اجرا یا زمان انجام عملیات های یک ساختمان داده باید حداقل زمان ممکن را داشته باشد.
- پیچیدگی فضایی (Space Complexity) : میزان حافظه مصرفی توسط یک عملیات ساختمان داده باید حداقل ممکن باشد.
دلیل استفاده از ساختمان داده
همان طور که برنامه پیچیده تر می شوند و با داده های عظیم کار می کنند، سه مشکل رایج نیز بوجود می آید که در زیر مشاهده می کنید:
- جستجوی داده : لیستی از یک میلیون آیتم ذخیره شده را در نظر بگیرید. اگر برنامه بخواهد یک آیتم را در بین یک میلیون آیتم پیدا کند، هر بار که عمل جستجو را انجام می دهد، باید یک میلیون آیتم را بررسی کند و این موضوع باعث کندتر شدن عمل جستجو می شود.
- سرعت پردازنده : اگرچه سرعت پردازنده ها بسیار زیاد است، اما اگر حجم داده ها به میلیارد افزایش یابد، محدود می شود.
- درخواست های چندگانه : اگر هزاران نفر از کاربران به طور همزمان در یک سرور عمل جستجو را انجام دهند، حتی سریع ترین سرور ها هم با مشکل مواجه می شوند.
ساختمان داده ها راه حلی برای مشکلات فوق است. داده ها را می توان در یک ساختمان داده ها سازماندهی کرد به طوری که تمام آیتم هایی که ممکن است جستجو شوند و آیتم هایی که ممکن نیست جستجو شوند از یک دیگر تفکیک شوند.
مورد زمان اجرا
به طور معمول سه مورد وجود دارد که برای مقایسه زمان اجرای ساختمان داده ها استفاده می شود. این سه مورد عبارت اند از:
- بدترین حالت (Worst Case) : این سناریو برای زمانی است که یک عملیات ساختمان داده خاص برای اجرا شدن، حداکثر زمان ممکن را استفاده کند. اگر زمان بدترین حالت عملیات f(n) باشد، بیشینه زمانی که برای انجام عملیات لازم است، برابر با f(n) است.
- حالت متوسط (Average Case) : این سناریو برای زمانی است که یک عملیات ساختمان داده خاص برای اجرا شدن، متوسط زمان تعیین شده را استفاده کند. اگر زمان اجرای عملیات f(n) باشد، پس زمان اجرای m عملیات برابر با mf(n) خواهد بود.
- بهترین حالت (Best Case) : این سناریو حداقل زمان اجرای عملیات یک ساختار داده را نشان می دهد.
اصطلاحات پایه
- Data: داده ها مقادیر یا مجموعه از مقادیر هستند.
- Data Itme: به یک واحد از مقادیر اشاره می کند.
- Group Items :داده هایی که به زیر آیتم ها تقسیم می شوند، Group Items نامیده می شوند.
- Elementary Items : داده هایی که نمی توانند به زیر آیتم ها تقسیم شوند، Elementary Items نامیده می شوند.
- Attribute and Entity : یک موجودیت شامل ویژگی های مشخصی است که ممکن است دارای مقادیری باشند.
- Entity Set : موجودیت هایی که ویژگی های مشابهی دارند، یک Entity Set را تشکیل می دهند.
- Field : فیلد یک واحد ابتدایی اطلاعات می باشد که نشان دهنده یک ویژگی از یک موجودیت است.
- Record : یک Record مجموعه ای از Field ها می باشد.
- File : فایل مجموعه ای از Record های موجود در یک موجودیت است.
نوشته مروری بر ساختمان داده ها و الگوریتم – آموزش ساختمان داده ها اولین بار در سورس سرا - آموزش برنامه نویسی. پدیدار شد.
