برچسب: تحقیق درباره ساختمان داده ها

تفاوت الگوريتم و برنامه در اين است كه الگوريتم حتما بايد پايان پذير باشد اما برنامه لزوما پايان پذير نيست .

سيستم عامل يك برنامه است زيرا هيچگاه پايان نمي پذيرد و در يك سيكل انتظار نيست تا برنامه بعدر وارد شود و آن را پردازش كند .

در تحليل الگوريتم ، مقدار حافظه مصرفي و زمان اجرا بسيار مهم است لذا الگوريتمي بهتر است كه سريعتر اجرا شود و حافظه كمتري را اشغال كند .

به عبارت ديگر پيچيديگي زماني و فضايي كمتري دارد.

سرعت اجرا را مرتبه اجرائي هم مي گويند .

معيار سنجش كارا آيي يك الگوريتم order يا رتبه الگوريتم است كه پيچيديگي هاي زماني و فضايي را نشان مي دهد.

رتبه برحسب سايز مساله (n) محاسبه مي شود .

اگر در حلقه ،متغير حلقه در عمل ضرب و يا تقسيم شركت كند ،مرتبه اجرايي لگاريتمي است و عددي كه ضرب و يا تقسيم مي شود مبناي الگوريتم است .

اگر متغير حلقه در عمل جمع و يا تفريق شركت كند ، تعددا تكرار دستور داخل حلقه برابر عددجمع و يا تفريق /n مي باشد .

اگر تابع بازگشتي باشد تعداد فراخواني تابع مبناي توان خواهد بود . نحوه كار روي پارامتر هاي تابع ،توان آن عدد خواهد بود.

گاهي اوقات عبارت f(n)=o(g(n)) را به صورت f(n) € o(g(n)) نيز نمايش مي دهند.

آرايه

نوعي ساختمان داده است و براي پياده سازي ساختار هاي مختلف داده اي بكار مي رود . و به صورت A[L..U] كه كران U بالا و L كران پايين مي باشد . اگر آدرس شروع اين آرايه در حافظه آدرس α باشد و هر خانه N بايت حافظه اشعال كند . 

انگاه آدرس خانه a[i] و تعداد عناصر آرايه از فرمول زير بدست مي آيد: : A[I]=α+(I-L)*N آدرس خانه و U-L+1= تعداد عناصر آرايه a كه به همين ترتيب مي توانيم براي پيمايش سطري و ستوني از آرايه با فرمول مشخص استفاده كنيم 

 اما در مورد جمع دو ماتريس ها بايد گفت كه اگر از دوحلقه تودرتو استفاده مي شود بنابر اين پيچيديگي زماني در جمع ماتريس ها برابر (o(mn است .

اگر ماتريس ها مربع باشند o(n^2) زمان اجراي آنها خواهد بود .

در ضرب دو ماتريس ، از سه حلقه تودر تو استفاده مي شود لذا o(n^3) مناسب ترين مرتبه زماني براي ماتريس هاي مربع مي باشند . در زمان حذف آرايه n عنصري مقدار متوسط جابجايي[n-1/2] مي باشد.